Uncountable automatic classes and learning
In this paper the authors consider uncountable classes recognizable by \(\omega \)-automata and investigate suitable learning paradigms for them. In particular, the counterparts of explanatory, vacillatory and behaviourally correct learning are introduced for this setting. Here the learner reads in parallel the data of a text for a language \(L\) from the class plus an \(\omega \)-index \(\alpha \) and outputs a sequence of \(\omega \)-automata such that all but finitely many of these \(\omega \)-automata accept the index \(\alpha \) if and only if \(\alpha \) is an index for \(L\). It is shown that any class is behaviourally correct learnable if and only if it satisfies Angluin's tell-tale condition. On the one hand, every class satisfying Angluin's tell-tale condition is vacillatorily learnable in every indexing; on the other hand, there is a fixed class such that the level of the class in the hierarchy of vacillatory learning depends on the indexing of the class chosen. The authors also consider a notion of blind learning. They show that a class is blind explanatorily (vacillatorily) learnable if and only if it satisfies Angluin's tell-tale condition and is countable. For behaviourally correct learning, there is no difference between the blind and non-blind version. This work establishes a bridge between the theory of \(\omega \)-automata and inductive inference (learning theory).
- Automata theory and its applications
- Cardinality and counting quantifiers on omega-automatic structures
- Finite presentations of infinite structures: Automata and interpretations
- scientific article; zbMATH DE number 5605134 (Why is no real title available?)
- scientific article; zbMATH DE number 3237829 (Why is no real title available?)
- Inductive inference of formal languages from positive data
- Language identification in the limit
- Learnability of automatic classes
- The Büchi Complementation Saga
- The Power of Vacillation in Language Learning
- Weak Second‐Order Arithmetic and Finite Automata
This page was built for publication: Uncountable automatic classes and learning
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2431428)
