The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
复制标题
非确定性莫斯托夫斯基层次结构和距离奇偶自动机
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Christof Löding
中科院分区：
文献类型：
--
作者：
Thomas Colcombet;Christof Löding
给定Rabin树语言和自然数i，j，如果语言被使用优先级{i，i+ 1，.，j}。i，j-可行性在Rabin-tree语言上引入了一个层次结构，称为Mostowski层次结构。
本文证明了判定语言是否i，j-可行的问题可归结为距离奇偶自动机的一致普适性问题。距离奇偶自动机形成了一种新的自动机模型，扩展了Kirsten在他的星高问题的可判定性证明中引入的嵌套距离沙漠自动机和无限树上的奇偶自动机。距离奇偶自动机，而不是接受一种语言，附加到每棵树的成本，在1.一致普适性问题在于确定该成本函数是否由有限值限定。
Given a Rabin tree-language and natural numbers i,j, the language is said to be i,j-feasible if it is accepted by a parity automaton using priorities {i,i+ 1,...,j}. The i,j-feasibility induces a hierarchy over the Rabin-tree languages called the Mostowski hierarchy.
In this paper we prove that the problem of deciding if a language is i,j-feasible is reducible to the uniform universality problem for distance-parity automata. Distance-parity automata form a new model of automata extending both the nested distance desert automata introduced by Kirsten in his proof of decidability of the star-height problem, and parity automata over infinite trees. Distance-parity automata, instead of accepting a language, attach to each tree a cost in i¾?+ 1. The uniform universality problem consists in determining if this cost function is bounded by a finite value.