6533b838fe1ef96bd12a4fab

RESEARCH PRODUCT

Ordinal mind change complexity of language identification

subject

description

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.