Learning regular omega languages (Q329611)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Learning regular omega languages |
scientific article |
Statements
Learning regular omega languages (English)
0 references
21 October 2016
0 references
The paper investigates three algorithms for learning an unknown regular set of infinite words using membership and equivalence queries. These algorithms use different canonical representations of regular \(\omega\)-languages. The representations are based on families of deterministic finite automata (dfa) accepting sets of infinite words: 1. a dfa representation used by \textit{A. Farzan} et al. [Lect. Notes Comput. Sci. 4963, 2--17 (2008; Zbl 1134.68406)] which is based on the \(L_{\$}\)-representation introduced by \textit{H. Calbrix} et al. [C. R. Acad. Sci., Paris, Sér. I 318, No. 5, 493--497 (1994; Zbl 0917.20053)]; 2. the syntactic FORC, introduced by \textit{O. Maler} and \textit{L. Staiger} [Theor. Comput. Sci. 183, No. 1, 93--112 (1997; Zbl 0911.68145)]; and 3. a new representation. It is shown that the second and third can be exponentially smaller than the first, and the third is at most as large as the second.
0 references
active learning
0 references
language inference
0 references
infinitary languages
0 references
membership queries
0 references
equivalence queries
0 references
Büchi automaton
0 references
0 references