A Hierarchy of Automatic ω-Words having a Decidable MSO Theory
Mathematische Grundlagen der Informatik, RWTH Aachen, Aachen, Germany; firstname.lastname@example.org
We investigate automatic presentations of ω-words. Starting points of our study are the works of Rigo and Maes, Caucal, and Carton and Thomas concerning lexicographic presentation, MSO-interpretability in algebraic trees, and the decidability of the MSO theory of morphic words. Refining their techniques we observe that the lexicographic presentation of a (morphic) word is in a certain sense canonical. We then generalize our techniques to a hierarchy of classes of ω-words enjoying the above mentioned definability and decidability properties. We introduce k-lexicographic presentations, and morphisms of level k stacks and show that these are inter-translatable, thus giving rise to the same classes of k-lexicographic or level k morphic words. We prove that these presentations are also canonical, which implies decidability of the MSO theory of every k-lexicographic word as well as closure of these classes under MSO-definable recolorings, e.g. closure under deterministic sequential mappings. The classes of k-lexicographic words are shown to constitute an infinite hierarchy.
Mathematics Subject Classification: 03D05 / 68Q42 / 68Q45 / 68R15
Key words: Morphic words / monadic second-order logic / automatic structures / automatic sequences.
© EDP Sciences, 2008