Families of DFAs as Acceptors of $\omega$-Regular Languages
Families of DFAs (FDFAs) provide an alternative formalism for recognizing $\omega$-regular languages. The motivation for introducing them was a desired correlation between the automaton states and right congruence relations, in a manner similar to the Myhill-Nerode theorem for regular languages. Thi...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2018-02-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/2624/pdf |
| _version_ | 1797268621332840448 |
|---|---|
| author | Dana Angluin Udi Boker Dana Fisman |
| author_facet | Dana Angluin Udi Boker Dana Fisman |
| author_sort | Dana Angluin |
| collection | DOAJ |
| description | Families of DFAs (FDFAs) provide an alternative formalism for recognizing
$\omega$-regular languages. The motivation for introducing them was a desired
correlation between the automaton states and right congruence relations, in a
manner similar to the Myhill-Nerode theorem for regular languages. This
correlation is beneficial for learning algorithms, and indeed it was recently
shown that $\omega$-regular languages can be learned from membership and
equivalence queries, using FDFAs as the acceptors.
In this paper, we look into the question of how suitable FDFAs are for
defining omega-regular languages. Specifically, we look into the complexity of
performing Boolean operations, such as complementation and intersection, on
FDFAs, the complexity of solving decision problems, such as emptiness and
language containment, and the succinctness of FDFAs compared to standard
deterministic and nondeterministic $\omega$-automata.
We show that FDFAs enjoy the benefits of deterministic automata with respect
to Boolean operations and decision problems. Namely, they can all be performed
in nondeterministic logarithmic space. We provide polynomial translations of
deterministic B\"uchi and co-B\"uchi automata to FDFAs and of FDFAs to
nondeterministic B\"uchi automata (NBAs). We show that translation of an NBA to
an FDFA may involve an exponential blowup. Last, we show that FDFAs are more
succinct than deterministic parity automata (DPAs) in the sense that
translating a DPA to an FDFA can always be done with only a polynomial
increase, yet the other direction involves an inevitable exponential blowup in
the worst case. |
| first_indexed | 2024-04-25T01:35:23Z |
| format | Article |
| id | doaj.art-4a0c4736a6aa4775814223e4d5fc47a1 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:35:23Z |
| publishDate | 2018-02-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-4a0c4736a6aa4775814223e4d5fc47a12024-03-08T09:53:24ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742018-02-01Volume 14, Issue 110.23638/LMCS-14(1:15)20182624Families of DFAs as Acceptors of $\omega$-Regular LanguagesDana AngluinUdi BokerDana FismanFamilies of DFAs (FDFAs) provide an alternative formalism for recognizing $\omega$-regular languages. The motivation for introducing them was a desired correlation between the automaton states and right congruence relations, in a manner similar to the Myhill-Nerode theorem for regular languages. This correlation is beneficial for learning algorithms, and indeed it was recently shown that $\omega$-regular languages can be learned from membership and equivalence queries, using FDFAs as the acceptors. In this paper, we look into the question of how suitable FDFAs are for defining omega-regular languages. Specifically, we look into the complexity of performing Boolean operations, such as complementation and intersection, on FDFAs, the complexity of solving decision problems, such as emptiness and language containment, and the succinctness of FDFAs compared to standard deterministic and nondeterministic $\omega$-automata. We show that FDFAs enjoy the benefits of deterministic automata with respect to Boolean operations and decision problems. Namely, they can all be performed in nondeterministic logarithmic space. We provide polynomial translations of deterministic B\"uchi and co-B\"uchi automata to FDFAs and of FDFAs to nondeterministic B\"uchi automata (NBAs). We show that translation of an NBA to an FDFA may involve an exponential blowup. Last, we show that FDFAs are more succinct than deterministic parity automata (DPAs) in the sense that translating a DPA to an FDFA can always be done with only a polynomial increase, yet the other direction involves an inevitable exponential blowup in the worst case.https://lmcs.episciences.org/2624/pdfcomputer science - formal languages and automata theoryf.1.1d.2.4 |
| spellingShingle | Dana Angluin Udi Boker Dana Fisman Families of DFAs as Acceptors of $\omega$-Regular Languages Logical Methods in Computer Science computer science - formal languages and automata theory f.1.1 d.2.4 |
| title | Families of DFAs as Acceptors of $\omega$-Regular Languages |
| title_full | Families of DFAs as Acceptors of $\omega$-Regular Languages |
| title_fullStr | Families of DFAs as Acceptors of $\omega$-Regular Languages |
| title_full_unstemmed | Families of DFAs as Acceptors of $\omega$-Regular Languages |
| title_short | Families of DFAs as Acceptors of $\omega$-Regular Languages |
| title_sort | families of dfas as acceptors of omega regular languages |
| topic | computer science - formal languages and automata theory f.1.1 d.2.4 |
| url | https://lmcs.episciences.org/2624/pdf |
| work_keys_str_mv | AT danaangluin familiesofdfasasacceptorsofomegaregularlanguages AT udiboker familiesofdfasasacceptorsofomegaregularlanguages AT danafisman familiesofdfasasacceptorsofomegaregularlanguages |