Document RAIRO-Theor. Inf. Appl. 42, 417-450 (2008)
DOI: 10.1051/ita:2008008
A Hierarchy of Automatic 
-Words having a Decidable MSO Theory
Vince Bárány Mathematische Grundlagen der Informatik, RWTH Aachen, Aachen, Germany; vbarany@logic.rwth-aachen.de
Published online: 3 June 2008
Abstract
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