License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2016.11
URN: urn:nbn:de:0030-drops-64274
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6427/
Angluin, Dana ;
Boker, Udi ;
Fisman, Dana
Families of DFAs as Acceptors of omega-Regular Languages
Abstract
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 Buchi and coBuchi automata to FDFAs and of FDFAs to nondeterministic Buchi 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.
BibTeX - Entry
@InProceedings{angluin_et_al:LIPIcs:2016:6427,
author = {Dana Angluin and Udi Boker and Dana Fisman},
title = {{Families of DFAs as Acceptors of omega-Regular Languages}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {11:1--11:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-016-3},
ISSN = {1868-8969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6427},
URN = {urn:nbn:de:0030-drops-64274},
doi = {10.4230/LIPIcs.MFCS.2016.11},
annote = {Keywords: finite automata, omega regular languages}
}
|
Keywords: |
|
finite automata, omega regular languages |
|
Collection: |
|
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
19.08.2016 |
