论文标题
概率BüchiAutomata中的歧义，无力和规律性
Ambiguity, Weakness, and Regularity in Probabilistic Büchi Automata
论文作者
论文摘要
概率的Büchi自动机是PFA对无限单词的自然概括，但仅仅是最近才研究的，而且许多有趣的问题仍然开放。众所周知，PBA通常接受一类超越普通语言的语言。在这项工作中，我们扩展了已知的限制性PBA类别，这些类别仍然是规则的，强烈依赖于有关经典欧米茄Automata中歧义的概念。此外，我们研究了尚未考虑的弱PBA的自然级别的表达性，并且还表明，弱PBA的规律性问题是不可确定的。
Probabilistic Büchi automata are a natural generalization of PFA to infinite words, but have been studied in-depth only rather recently and many interesting questions are still open. PBA are known to accept, in general, a class of languages that goes beyond the regular languages. In this work we extend the known classes of restricted PBA which are still regular, strongly relying on notions concerning ambiguity in classical omega-automata. Furthermore, we investigate the expressivity of the not yet considered but natural class of weak PBA, and we also show that the regularity problem for weak PBA is undecidable.
