論文

査読有り
2010年2月

Mind change complexity of inferring unbounded unions of restricted pattern languages from positive data

THEORETICAL COMPUTER SCIENCE
  • Matthew de Brecht
  • ,
  • Akihiro Yamamoto

411
7-9
開始ページ
976
終了ページ
985
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1016/j.tcs.2009.11.004
出版者・発行元
ELSEVIER SCIENCE BV

This paper shows that the mind change complexity of inferring from positive data the class of unbounded unions of languages of regular patterns with constant segment length bound is of the form omega(omega alpha) + beta, assuming that the patterns are defined over a finite alphabet containing at least two elements. Here alpha or beta and are natural numbers, and we give tight bounds on their values based on the length of the constant segments and the size of the alphabet of the pattern languages. This is, to the authors' knowledge, the first time a natural class of languages has been shown to be inferable with mind change complexity above omega(omega). The proof uses the notion of closure operators on a class of languages, and also uses the order type of well-partial-orderings to obtain a mind change bound. The inference algorithm presented can be easily applied to a wide range of classes of languages. Finally, we show an interesting connection between proof theory and mind change complexity. (C) 2009 Elsevier B.V. All rights reserved.

Web of Science ® 被引用回数 : 6

リンク情報
DOI
https://doi.org/10.1016/j.tcs.2009.11.004
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000274886700004&DestApp=WOS_CPL
ID情報
  • DOI : 10.1016/j.tcs.2009.11.004
  • ISSN : 0304-3975
  • Web of Science ID : WOS:000274886700004

エクスポート
BibTeX RIS