Polynomial Identification of $$\omega $$-Automata
| Autor: | Dana Fisman, Yaara Shoval, Dana Angluin |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
High Energy Physics::Phenomenology
02 engineering and technology Congruence relation Computer Science::Digital Libraries Omega Automaton Combinatorics 020204 information systems 0202 electrical engineering electronic engineering information engineering Computer Science::Programming Languages Computer Science::Symbolic Computation 020201 artificial intelligence & image processing Parity (mathematics) Time complexity Mathematics |
| Zdroj: | Tools and Algorithms for the Construction and Analysis of Systems ISBN: 9783030452360 TACAS (2) |
| DOI: | 10.1007/978-3-030-45237-7_20 |
| Popis: | We study identification in the limit using polynomial time and data for models of $$\omega $$-automata. On the negative side we show that non-deterministic $$\omega $$-automata (of types Büchi, coBüchi, Parity or Muller) can not be polynomially learned in the limit. On the positive side we show that the $$\omega $$-language classes $$\mathbb {IB}$$, $$\mathbb {IC}$$, $$\mathbb {IP}$$, and $$\mathbb {IM}$$ that are defined by deterministic Büchi, coBüchi, parity, and Muller acceptors that are isomorphic to their right-congruence automata (that is, the right congruences of languages in these classes are fully informative) are identifiable in the limit using polynomial time and data. We further show that for these classes a characteristic sample can be constructed in polynomial time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|