This paper studies the descriptional complexity of (i) sequences over a finite alphabet ; and (ii) subsets of (the natural numbers). If is a sequence over a finite alphabet , then we define the - of , to be the smallest possible number of states in any deterministic finite automaton that, for all with , takes expressed in base as input and computes . We give examples of sequences that have high automaticity in all bases ; for example, we show that the characteristic sequence of...
Nous montrons que le tracé d’un kolam indien classique, que l’on retrouve aussi dans la tradition des dessins sur le sable aux îles Vanuatu, peut être engendré par un morphisme de monoïde. La suite infinie morphique ainsi obtenue est reliée à la célèbre suite de Prouhet-Thue-Morse, mais elle n’est -automatique pour aucun entier .
We consider the position and number of occurrences of squares
in the Thue-Morse sequence, and show that the corresponding sequences
are -regular. We also prove that changing any finite but nonzero
number of bits in the Thue-Morse sequence creates an overlap, and any
linear subsequence of the Thue-Morse sequence (except those corresponding
to decimation by a power of ) contains an overlap.
We fill a gap in the proof of a theorem of our paper cited in the title.
Download Results (CSV)