License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2021.20
URN: urn:nbn:de:0030-drops-144607
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14460/
Bohn, León ;
Löding, Christof
Constructing Deterministic ω-Automata from Examples by an Extension of the RPNI Algorithm
Abstract
The RPNI algorithm (Oncina, Garcia 1992) constructs deterministic finite automata from finite sets of negative and positive example words. We propose and analyze an extension of this algorithm to deterministic ω-automata with different types of acceptance conditions. In order to obtain this generalization of RPNI, we develop algorithms for the standard acceptance conditions of ω-automata that check for a given set of example words and a deterministic transition system, whether these example words can be accepted in the transition system with a corresponding acceptance condition. Based on these algorithms, we can define the extension of RPNI to infinite words. We prove that it can learn all deterministic ω-automata with an informative right congruence in the limit with polynomial time and data. We also show that the algorithm, while it can learn some automata that do not have an informative right congruence, cannot learn deterministic ω-automata for all regular ω-languages in the limit. Finally, we also prove that active learning with membership and equivalence queries is not easier for automata with an informative right congruence than for general deterministic ω-automata.
BibTeX - Entry
@InProceedings{bohn_et_al:LIPIcs.MFCS.2021.20,
author = {Bohn, Le\'{o}n and L\"{o}ding, Christof},
title = {{Constructing Deterministic \omega-Automata from Examples by an Extension of the RPNI Algorithm}},
booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
pages = {20:1--20:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-201-3},
ISSN = {1868-8969},
year = {2021},
volume = {202},
editor = {Bonchi, Filippo and Puglisi, Simon J.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14460},
URN = {urn:nbn:de:0030-drops-144607},
doi = {10.4230/LIPIcs.MFCS.2021.20},
annote = {Keywords: deterministic omega-automata, learning from examples, learning in the limit, constructing acceptance conditions, active learning}
}
|
Keywords: |
|
deterministic omega-automata, learning from examples, learning in the limit, constructing acceptance conditions, active learning |
|
Collection: |
|
46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
18.08.2021 |
