@inproceedings{07e85feb033e4fd69dc0d7e5c95da42f,
title = "Ordinal mind change complexity of language identification",
abstract = "The approach of ordinal mind change complexity, introduced by Freivalds and Smith, uses constructive ordinals to bound the number of mind changes made by a learning machine. This approach provides a measure of the extent to which a learning machine has to keep revising its estimate of the number of mind changes it will make before converging to a correct hypothesis for languages in the class being learned. Recently, this measure, which also suggests the difficulty of learning a class of languages, has been used to analyze the learnability of rich classes of languages. Jain and Sharma have shown that the ordinal mind change complexity for identification from positive data of languages formed by unions of up to n pattern languages is ω n. They have also shown that this bound is essential. Similar results were also established for classes definable by length-bounded elementary formal systems with up to n clauses. These later results translate to learnability of certain classes of logic programs. The present paper further investigates the utility of ordinal mind change complexity. It is shown that if identification is to take place from both positive and negative data, then the ordinal mind change complexity of the class of languages formed by unions of up to n+1 pattern languages is only ω{\texttimes}o n(where {\texttimes}o represents ordinal multiplication). This result nicely extends an observation of Lange and Zeugmann that pattern languages can be identified from both positive and negative data with 0 mind changes. Existence of an ordinal mind change bound for a class of learnable languages can be seen as an indication of its learning {\textquotedblleft}tractability.{\textquotedblright} Conditions are investigated under which a class has an ordinal mind change bound for identification from positive data. It is shown that an indexed family of computable languages has an ordinal mind change bound if it has finite elasticity and can be identified by a conservative machine. It is also shown that the requirement of conservative identification can be sacrificed for the purely topological requirement of M-finite thickness. Interaction between identification by monotonic strategies and existence of ordinal mind change bound is also investigated.",
author = "Andris Ambainis and Sanjay Jain and Arun Sharma",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1997.; 3rd European Conference on Computational Learning Theory, EuroCOLT 1997 ; Conference date: 17-03-1997 Through 19-03-1997",
year = "1997",
doi = "10.1007/3-540-62685-9\_25",
language = "English",
isbn = "3540626859",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "301--315",
editor = "Shai Ben-David",
booktitle = "Computational Learning Theory - 3rd European Conference, EuroCOLT 1997, Proceedings",
address = "Germany",
}