No CrossRef data available.
Article contents
A Hierarchy of Automatic ω-Words having a Decidable MSO Theory
Published online by Cambridge University Press: 03 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.
- Type
- Research Article
- Information
- RAIRO - Theoretical Informatics and Applications , Volume 42 , Issue 3: JM'06 , July 2008 , pp. 417 - 450
- Copyright
- © EDP Sciences, 2008