Constructing Deterministic Parity Automata from Positive and Negative Examples
TheoretiCS · 2024
DOI: 10.46298/theoretics.24.17 ↗Kurz gefasst
Fachartikel in der Zeitschrift TheoretiCS, 2024. Verfasst von León Bohn und 1 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref).
Abstract (Originalsprache)
We present a polynomial time algorithm that constructs a deterministic parity automaton (DPA) from a given set of positive and negative ultimately periodic example words. We show that this algorithm is complete for the class of $\omega$-regular languages, that is, it can learn a DPA for each regular $\omega$-language. For use in the algorithm, we give a definition of a DPA, that we call the precise DPA of a language, and show that it can be constructed from the syntactic family of right congruences for that language (introduced by Maler and Staiger in 1997). Depending on the structure of the language, the precise DPA can be of exponential size compared to a minimal DPA, but it can also be a minimal DPA. The upper bound that we obtain on the number of examples required for our algorithm to find a DPA for $L$ is therefore exponential in the size of a minimal DPA, in general. However we identify two parameters of regular $\omega$-languages such that fixing these parameters makes the bound polynomial.
Zitieren
APA
Bohn, L., & Löding, C. (2024). Constructing Deterministic Parity Automata from Positive and Negative Examples. TheoretiCS. https://doi.org/10.46298/theoretics.24.17
Vancouver
Bohn L, Löding C. Constructing Deterministic Parity Automata from Positive and Negative Examples. TheoretiCS. 2024. doi:10.46298/theoretics.24.17
BibTeX
@article{Bohn2024,
author = {Bohn, León and Löding, Christof},
title = {Constructing Deterministic Parity Automata from Positive and Negative Examples},
journal = {TheoretiCS},
year = {2024},
doi = {10.46298/theoretics.24.17}
}
EUVIMED