2026-08-17T14:20:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11612 2024-03-06T10:48:26Z ddc:004 open_access

Degrees of Ambiguity of Büchi Tree Automata Rabinovich, Alexander Tiferet, Doron automata on infinite trees ambiguous automata 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Rabinovich and Doron Tiferet 2019 Is Part Of LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2019.50 urn:nbn:de:0030-drops-116122 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.50 eng https://creativecommons.org/licenses/by/3.0/legalcode