Alexander Rabinovich ; Doron Tiferet - Ambiguity Hierarchy of Regular Infinite Tree Languages

lmcs:6766 - Logical Methods in Computer Science, August 13, 2021, Volume 17, Issue 3 - https://doi.org/10.46298/lmcs-17(3:18)2021
Ambiguity Hierarchy of Regular Infinite Tree Languages

Authors: Alexander Rabinovich ; Doron Tiferet

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 it is k-ambiguous for some $k \in \mathbb{N}$. 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 $\omega$-words every regular language is accepted by an unambiguous B├╝chi automaton and by a deterministic parity automaton. Over infinite trees Carayol et al. showed that there are ambiguous languages. We show that over infinite trees there is a hierarchy of degrees of ambiguity: For every k > 1 there are k-ambiguous languages that are not k - 1 ambiguous; and there are finitely (respectively countably, uncountably) ambiguous languages that are not boundedly (respectively finitely, countably) ambiguous.


Volume: Volume 17, Issue 3
Published on: August 13, 2021
Accepted on: May 29, 2021
Submitted on: September 8, 2020
Keywords: Computer Science - Logic in Computer Science,Computer Science - Computation and Language,03B70, 68Q45,F.4.3


Share

Consultation statistics

This page has been seen 141 times.
This article's PDF has been downloaded 66 times.