2026-07-24T21:21:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12749 2024-03-06T10:50:44Z ddc:004 open_access

Ambiguity Hierarchy of Regular Infinite Tree Languages Rabinovich, Alexander Tiferet, Doron automata on infinite trees ambiguous automata monadic second-order logic An automaton is unambiguous if for every input it has at most one accepting computation. An automaton is k-ambiguous (for k > 0) if for every input it has at most k accepting computations. An automaton is boundedly ambiguous if there is k ∈ ℕ, such that for every input it has at most k accepting computations. An automaton is finitely (respectively, countably) ambiguous if for every input it has at most finitely (respectively, countably) many accepting computations. The degree of ambiguity of a regular language is defined in a natural way. A language is k-ambiguous (respectively, boundedly, finitely, countably ambiguous) if it is accepted by a k-ambiguous (respectively, boundedly, finitely, countably ambiguous) automaton. Over finite words every regular language is accepted by a deterministic automaton. Over finite trees every regular language is accepted by an unambiguous automaton. Over ω-words every regular language is accepted by an unambiguous Büchi automaton [Arnold, 1983] and by a deterministic parity automaton. Over infinite trees there are ambiguous languages [Carayol et al., 2010]. We show that over infinite trees there is a hierarchy of degrees of ambiguity: For every k > 1 there are k-ambiguous languages which are not k-1 ambiguous; there are finitely (respectively countably, uncountably) ambiguous languages which are not boundedly (respectively finitely, countably) ambiguous. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Rabinovich and Doron Tiferet 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.80 urn:nbn:de:0030-drops-127495 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.80 eng https://creativecommons.org/licenses/by/3.0/legalcode