2011/09/28 by Anna Frid, Frid, Anna, Luca Zamboni +1
Computer Science · Mathematics · #05A05 #68R15 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO #msc:05A05 #msc:68R15
paper · pdf · doi:10.48550/arxiv.1109.6131
Reported at Journées Montoises 2010; accepted to RAIRO ITA
arxiv created 2011/09/28 · arxiv updated 2011/09/29
An infinite permutation α is a linear ordering of \mathbb N. We study properties of infinite permutations analogous to those of infinite words, and show some resemblances and some differences between permutations and words. In this paper, we try to extend to permutations the notion of automaticity. As we shall show, the standard definitions which are equivalent in the case of words are not equivalent in the context of permutations. We investigate the relationships between these definitions and prove that they constitute a chain of inclusions. We also construct and study an automaton generating the Thue-Morse permutation.