论文标题
常规无限树语言的歧义层次结构
Ambiguity Hierarchy of Regular Infinite Tree Languages
论文作者
论文摘要
如果每个输入最多都接受计算，则自动机是明确的。自动机是k-ammagigul（对于k> 0），如果对于每个输入，则最多都有K接受计算。如果自动机对\ Mathbb {n} $的某些$ k \ ab-ambigul，则有限。如果每个输入最多（分别）（分别）许多接受计算，则自动机是有限的（分别，计数）的。 普通语言的歧义程度是自然而然的。如果语言被K漫不经意的（分别，有限，有限，有限，模棱两可的）自动机接受，则语言是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 $ω$-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.
