×

On infinite terms having a decidable monadic theory. (English) Zbl 1014.68077

Diks, Krzysztof (ed.) et al., Mathematical foundations of computer science 2002. 27th symposium, MFCS 2002, Warsaw, Poland, August 26-30, 2002. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2420, 165-176 (2002).
Summary: 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, Niwinski 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.
For the entire collection see [Zbl 0997.00033].

MSC:

68Q42 Grammars and rewriting systems
03B25 Decidability of theories and sets of sentences
PDFBibTeX XMLCite
Full Text: Link