一句话：证明正则无限树语言在歧义度上形成严格层级，从k歧义到有限、可数、不可数歧义逐级分离。
论文研究自动机接受计算的歧义度，即每个输入最多有多少个接受计算。已知在有限词上正则语言可由确定自动机接受，在有限树上可由无歧义自动机接受，在ω词上可由无歧义Büchi自动机及确定奇偶自动机接受，但在无限树上 Carayol 等人已证明存在歧义语言。本文进一步刻画无限树上的正则语言歧义层级，证明对每个 k > 1，存在 k-歧义但非 (k-1)-歧义的语言；同时存在有限歧义但非有界歧义、可数歧义但非有限歧义、不可数歧义但非可数歧义的正则语言。结果给出了无限树正则语言在歧义度上的严格分离谱系，表明其歧义行为比有限词、有限树和ω词更为复杂。
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\"uchi 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.
@article{paperbot1283,
title = {Ambiguity Hierarchy of Regular Infinite Tree Languages},
author = {Alexander Rabinovich and Doron Tiferet},
journal = {Logical Methods in Computer Science},
volume = {Volume 17, Issue 3},
year = {2021},
doi = {10.46298/lmcs-17(3:18)2021}
}