Feb, 2010
Mind change complexity of inferring unbounded unions of restricted pattern languages from positive data
THEORETICAL COMPUTER SCIENCE
- ,
- Volume
- 411
- Number
- 7-9
- First page
- 976
- Last page
- 985
- Language
- English
- Publishing type
- Research paper (scientific journal)
- DOI
- 10.1016/j.tcs.2009.11.004
- Publisher
- 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.
- Link information
- ID information
-
- DOI : 10.1016/j.tcs.2009.11.004
- ISSN : 0304-3975
- Web of Science ID : WOS:000274886700004