Abstract
An automaton is unambiguous if for every input it has at most one acceptingcomputation. An automaton is k-ambiguous (for k>0) if for every input it has atmost k accepting computations. An automaton is boundedly ambiguous if there isk, such that for every input it has at most k accepting computations. Anautomaton is finitely (respectively, countably) ambiguous if for every input ithas at most finitely (respectively, countably) many accepting computations. The degree of ambiguity of a regular language is defined in a natural way. Alanguage is k-ambiguous (respectively, boundedly, finitely, countablyambiguous) if it is accepted by a k-ambiguous (respectively, boundedly,finitely, countably ambiguous) automaton. Over finite words, every regularlanguage is accepted by a deterministic automaton. Over finite trees, everyregular language is accepted by an unambiguous automaton. Over $\omega$-wordsevery regular language is accepted by an unambiguous B\"uchi automaton and by adeterministic parity automaton. Over infinite trees, Carayol et al. showed thatthere are ambiguous languages. We show that over infinite trees there is a hierarchy of degrees ofambiguity: For every k>1 there are k-ambiguous languages which are not k-1ambiguous; and there are finitely (respectively countably, uncountably)ambiguous languages which are not boundedly (respectively finitely, countably)ambiguous.