Rabinovich, Alexander ;
Tiferet, Doron
Ambiguity Hierarchy of Regular Infinite Tree Languages
Abstract
An automaton is unambiguous if for every input it has at most one accepting computation. An automaton is kambiguous (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 kambiguous (respectively, boundedly, finitely, countably ambiguous) if it is accepted by a kambiguous (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 kambiguous languages which are not k1 ambiguous; there are finitely (respectively countably, uncountably) ambiguous languages which are not boundedly (respectively finitely, countably) ambiguous.
BibTeX  Entry
@InProceedings{rabinovich_et_al:LIPIcs:2020:12749,
author = {Alexander Rabinovich and Doron Tiferet},
title = {{Ambiguity Hierarchy of Regular Infinite Tree Languages}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {80:180:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771597},
ISSN = {18688969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12749},
URN = {urn:nbn:de:0030drops127495},
doi = {10.4230/LIPIcs.MFCS.2020.80},
annote = {Keywords: automata on infinite trees, ambiguous automata, monadic secondorder logic}
}
18.08.2020
Keywords: 

automata on infinite trees, ambiguous automata, monadic secondorder logic 
Seminar: 

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Issue date: 

2020 
Date of publication: 

18.08.2020 