Document Open Access Logo

On the (In)Succinctness of Muller Automata

Author Udi Boker

PDF
Thumbnail PDF

File

LIPIcs.CSL.2017.12.pdf
  • Filesize: 0.5 MB
  • 16 pages

Document Identifiers

Author Details

Udi Boker

Cite As Get BibTex

Udi Boker. On the (In)Succinctness of Muller Automata. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.CSL.2017.12

Abstract

There are several types of finite automata on infinite words, differing in their acceptance conditions. As each type has its own advantages, there is an extensive research on the size blowup involved in translating one automaton type to another.

Of special interest is the Muller type, providing the most detailed acceptance condition. It turns out that there is inconsistency and incompleteness in the literature results regarding the translations to and from Muller automata. Considering the automaton size, some results take into account, in addition to the number of states, the alphabet length and the number of transitions while ignoring the length of the acceptance condition, whereas other results consider the length of the acceptance condition while ignoring the two other parameters.

We establish a full picture of the translations to and from Muller automata, enhancing known results and adding new ones. Overall, Muller automata can be considered less succinct than parity, Rabin, and Streett automata: translating nondeterministic Muller automata to the other nondeterministic types involves a polynomial size blowup, while the other way round is exponential; translating between the deterministic versions is exponential in both directions; and translating nondeterministic automata of all types to deterministic Muller automata is doubly exponential, as opposed to a single exponent in the translations to the other deterministic types.

Subject Classification

Keywords
  • Automata
  • Omega-regular languages
  • Determinization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. D. Angluin, U. Boker, and D. Fisman. Families of DFAs as acceptors of omega-regular languages. In Proc. of MFCS, pages 11:1-11:14, 2016. Google Scholar
  2. U. Boker and O. Kupferman. Translating to co-Büchi made tight, unified, and useful. ACM Trans. Comput. Log., 13(4):29:1-29:26, 2012. Google Scholar
  3. U. Boker, O. Kupferman, and A. Rosenberg. Alternation removal in Büchi automata. In Proc. of ICALP, volume 6199, pages 76-87, 2010. Google Scholar
  4. J. R. Büchi. On a decision method in restricted second order arithmetic. In Proc. Int. Congress on Logic, Method, and Philosophy of Science. 1960, pages 1-12. Stanford University Press, 1962. Google Scholar
  5. T. Colcombet and K. Zdanowski. A tight lower bound for determinization of transition labeled Büchi automata. In Proc. of ICALP, pages 151-162, 2009. Google Scholar
  6. Y. Gurevich and L. Harrington. Trees, automata, and games. In Proc. 14th ACM Symp. on Theory of Computing, pages 60-65. ACM Press, 1982. Google Scholar
  7. O. Kupferman and N. Piterman. Lower bounds on witnesses for nonemptiness of universal co-Büchi automata. In Proc. of FoSSaCS, volume 5504 of LNCS, pages 182-196. Springer, 2009. Google Scholar
  8. O. Kupferman and M. Y. Vardi. Weak alternating automata are not that weak. ACM Transactions on Computational Logic, 2(2):408-429, 2001. Google Scholar
  9. C. Löding. Optimal bounds for the transformation of omega-automata. In Proc. of FSTTCS, volume 1738 of LNCS, pages 97-109, 1999. Google Scholar
  10. R. McNaughton. Testing and generating infinite sequences by a finite automaton. Information and Control, 9:521-530, 1966. Google Scholar
  11. M. Michel. Complementation is more difficult with automata on infinite words. CNET, Paris, 1988. Google Scholar
  12. S. Miyano and T. Hayashi. Alternating finite automata on ω-words. Theoretical Computer Science, 32:321-330, 1984. Google Scholar
  13. A. W. Mostowski. Regular expressions for infinite trees and a standard form of automata. In Computation Theory, volume 208 of LNCS, pages 157-168. Springer, 1984. Google Scholar
  14. D. E. Muller. Infinite sequences and finite machines. In Proc. 4th IEEE Symp. on Switching Circuit Theory and Logical design, pages 3-16, 1963. Google Scholar
  15. N. Piterman. From nondeterministic Büchi and Streett automata to deterministic parity automata. Logical Methods in Computer Science, 3(3):5, 2007. Google Scholar
  16. M. O. Rabin. Decidability of second order theories and automata on infinite trees. Transaction of the AMS, 141:1-35, 1969. Google Scholar
  17. S. Safra. Complexity of automata on infinite objects. PhD thesis, Weizmann Institute of Science, 1989. Google Scholar
  18. S. Safra. Exponential determinization for ω-automata with strong-fairness acceptance condition. In Proc. 24th ACM Symp. on Theory of Computing, 1992. Google Scholar
  19. S. Schewe. Büchi complementation made tight. In Proc. 26th Symp. on Theoretical Aspects of Computer Science, volume 3 of LIPIcs, pages 661-672. Schloss Dagstuhl, 2009. Google Scholar
  20. S. Schewe and T. Varghese. Determinising parity automata. In Proc. of MFCS, pages 486-498, 2014. Google Scholar
  21. R. S. Streett. Propositional dynamic logic of looping and converse. Information and Control, 54:121-141, 1982. Google Scholar
  22. Q. Yan. Lower bounds for complementation of omega-automata via the full automata technique. Logical Methods in Computer Science, 4(1), 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact