论文标题
通过量度理论的歧义
Ambiguity through the lens of measure theory
论文作者
论文摘要
在本文中，我们在Büchi自动机的有限词的歧义与同一自动机的无限单词的歧义之间建立了牢固的联系。该链接基于度量理论。更确切地说，我们表明这样的自动机是明确的，因为没有有限的单词标签两个以相同的起始状态和相同的结尾状态运行，并且仅在每个状态时，只有每个状态，从该状态开始的两个运行序列的无限序列标记了两个运行。用于定义这些可忽略的集合的度量，即零度量的集合，可以是由加权自动机计算的任何度量，该量度与Büchi自动机兼容。后一种条件非常自然：该度量必须将重量放在圆柱体[W]上，其中W是Büchi自动机中某些运行的标签。
In this paper, we establish a strong link between the ambiguity for finite words of a Büchi automaton and the ambiguity for infinite words of the same automaton. This link is based on measure theory. More precisely, we show that such an automaton is unambiguous, in the sense that no finite word labels two runs with the same starting state and the same ending state if and only if for each state, the set of infinite sequences labelling two runs starting from that state has measure zero. The measure used to define these negligible sets, that is sets of measure zero, can be any measure computed by a weighted automaton which is compatible with the Büchi automaton. This latter condition is very natural: the measure must put weight on cylinders [w] where w is the label of some run in the Büchi automaton.
