Paper Info
Title
Mind change complexity of inferring unbounded unions of pattern languages from positive data
Abstract
This paper gives a proof that the class of unbounded unions of languages of regular patterns with constant segment length bound is inferable from positive data with mind change bound between ωω and . We give a very tight bound on the mind change complexity 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 ωω. 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.
Year
DOI
Venue
2006
10.1007/11894841_13
ALT
Keywords
Field
DocType
pattern language,closure operator,inference algorithm,constant segment,mind change complexity,unbounded union,mind change,interesting connection,natural class,order type,constant segment length,positive data,proof theory,partial order
Discrete mathematics,Computer science,Abstract family of languages,Natural class,Proof theory,Natural language,Operator (computer programming),Order type,Regular language,Computational complexity theory
Conference
Volume
ISSN
ISBN
4264
0302-9743
3-540-46649-5
Citations 
PageRank 
References 
6
0.65
16
Authors
2
Name
Order
Citations
PageRank
de brecht112810.77
Akihiro Yamamoto213526.84