On Infinite Terms Having a Decidable Monadic Theory
On Infinite Terms Having a Decidable Monadic Theory
复制标题
在无限项上具有可判定的一元理论
DOI：
10.1007/3-540-45687-2_13
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
D. Caucal
中科院分区：
文献类型：
--
作者：
D. Caucal
我们研究了一个变换的条款，包括应用逆确定性的合理映射，然后展开。从正则项迭代这些变换给出了具有可判定一元理论的项族的层次结构。特别地，在第2层的族包含Carton和托马斯研究的形态无限词。我们表明，这个层次结构相吻合的层次结构考虑Knapik，Niwi？ski和Urzyczyn：高阶安全方案的解的项族。我们还表明，这一层次结构与Damm定义的层次结构相吻合，最近被认为是由Courcelle和Knapik：家庭的条款获得迭代应用的一阶替换的一组定期条款。最后，使用二阶替换产生相同的项。
We study a transformation on terms consisting of applying an inverse deterministic rational mapping followed by an unfolding. Iterating these transformations from the regular terms gives a hierarchy of families of terms having a decidable monadic theory. In particular, the family at level 2 contains the morphic infinite words investigated by Carton and Thomas. We show that this hierarchy coincides with the hierarchy considered by Knapik, Niwi?ski and Urzyczyn: the families of terms that are solutions of higher order safe schemes. We also show that this hierarchy coincides with the hierarchy defined by Damm, and recently considered by Courcelle and Knapik: the families of terms obtained by iterating applications of first order substitutions to the set of regular terms. Finally, using second order substitutions yields the same terms.