2026-07-24T03:16:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13470 2024-03-06T10:52:09Z ddc:004 open_access

Degrees of Ambiguity for Parity Tree Automata Rabinovich, Alexander Tiferet, Doron automata on infinite trees degree of ambiguity omega word automata parity 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 ∈ ℕ, such that for every input it has at most k accepting computations. We consider Parity Tree Automata (PTA) and prove that the problem whether a PTA is not unambiguous (respectively, is not boundedly ambiguous, not finitely ambiguous) is co-NP complete, and the problem whether a PTA is not countably ambiguous is co-NP hard. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Rabinovich and Doron Tiferet 2021 Is Part Of LIPIcs, Volume 183, 29th EACSL Annual Conference on Computer Science Logic (CSL 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2021.36 urn:nbn:de:0030-drops-134709 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2021.36 eng https://creativecommons.org/licenses/by/3.0/legalcode