LIPIcs.FSTTCS.2019.50.pdf
- Filesize: 0.5 MB
- 14 pages
Document
Degrees of Ambiguity of Büchi Tree Automata
Authors
Alexander Rabinovich 
,
-
Part of:
Volume:
39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-12-04
File
Document Identifiers
Author Details
Cite As Get BibTex
Alexander Rabinovich and Doron Tiferet. Degrees of Ambiguity of Büchi Tree Automata. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.FSTTCS.2019.50
Abstract
An automaton is unambiguous if for every input it has at most one accepting computation. An automaton is finitely (respectively, countably) ambiguous if for every input it has at most finitely (respectively, countably) many accepting computations. An automaton is boundedly ambiguous if there is k in N, such that for every input it has at most k accepting computations. We consider nondeterministic Büchi automata (NBA) over infinite trees and prove that it is decidable in polynomial time, whether an automaton is unambiguous, boundedly ambiguous, finitely ambiguous, or countably ambiguous.
Subject Classification
ACM Subject Classification
- Theory of computation → Automata over infinite objects
Keywords
- automata on infinite trees
- ambiguous automata
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- André Arnold. Rational omega-Languages are Non-Ambiguous. Theor. Comput. Sci., 26:221-223, September 1983. URL: https://doi.org/10.1016/0304-3975(83)90086-5.
-
Vince Bárány, Łukasz Kaiser, and Alex Rabinovich. Expressing cardinality quantifiers in monadic second-order logic over trees. Fundamenta Informaticae, 100(1-4):1-17, 2010.
-
Arnaud Carayol, Christof Löding, Damian Niwinski, and Igor Walukiewicz. Choice functions and well-orderings over the infinite binary tree. Open Mathematics, 8(4):662-682, 2010.
-
Thomas Colcombet. Unambiguity in automata theory. In International Workshop on Descriptional Complexity of Formal Systems, pages 3-18. Springer, 2015.
-
Yo-Sub Han, Arto Salomaa, and Kai Salomaa. Ambiguity, nondeterminism and state complexity of finite automata. Acta Cybernetica, 23(1):141-157, 2017.
-
Ernst Leiss. Succinct representation of regular languages by Boolean automata. Theoretical computer science, 13(3):323-330, 1981.
-
Hing Leung. Descriptional complexity of NFA of different ambiguity. International Journal of Foundations of Computer Science, 16(05):975-984, 2005.
- Christof Löding and Anton Pirogov. On Finitely Ambiguous Büchi Automata. In Developments in Language Theory - 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings, pages 503-515, 2018. URL: https://doi.org/10.1007/978-3-319-98654-8_41.
-
Dominique Perrin and Jean-Éric Pin. Infinite words: automata, semigroups, logic and games, volume 141. Academic Press, 2004.
-
Alexander Rabinovich. Complementation of Finitely Ambiguous Büchi Automata. In International Conference on Developments in Language Theory, pages 541-552. Springer, 2018.
-
Alexander Rabinovich and Doron Tiferet. Degree of Ambiguity for Tree Automata and Tree Languages, forthcoming.
-
Helmut Seidl. On the finite degree of ambiguity of finite tree automata. Acta Informatica, 26(6):527-542, 1989.
-
Wolfgang Thomas. Automata on infinite objects. In Formal Models and Semantics, pages 133-191. Elsevier, 1990.
-
Andreas Weber and Helmut Seidl. On the degree of ambiguity of finite automata. Theoretical Computer Science, 88(2):325-349, 1991.