Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Automatic Sequences and their ...

Automatic Sequences and their Shuffles

Tomi Kärki, Automatic Sequences and their Shuffles. TUCS Technical Reports 745, Turku Centre for Computer Science, 2006.

Abstract:

Infinite sequences are basic objects in modern discrete mathematics
and theoretical computer science. Especially, sequences generated by
some simple model of computation, for example by morphisms or
automata, are widely studied. This work focuses on automatic
sequences. Such a sequence can be generated by a finite
deterministic automaton with output. From another viewpoint,
automatic sequences are fixed points of uniform morphisms under a
coding.

In this work we present four equivalent definitions of automatic
sequences using finite automata with output, kernels, fibers and
uniform morphisms. Basic closure properties of this class of
sequences are considered. We also mention how automatic sequences
are related to transcendental number theory via the subword
complexity of a sequence. In addition we give a detailed proof of
the famous Cobham's theorem. It states that if a set is both $k$-
and $l$-automatic, for two multiplicatively independent integers $k$
and $l$, then it is ultimately periodic. Particularly, sequences are
consider from an algorithmic point of view in context with so called
regular shuffles. We present algorithms, which enable us to easily
calculate generating morphisms and codings for sequences obtained by
shuffling fixed points of uniform morphisms.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tKarki06a,
  title = {Automatic Sequences and their Shuffles},
  author = {Kärki, Tomi},
  number = {745},
  series = {TUCS Technical Reports},
  publisher = {Turku Centre for Computer Science},
  year = {2006},
  keywords = {automatic sequences, finite automata with output, Cobham's theorem, regular shuffles, perfect shuffles},
  ISBN = {952-12-1688-3},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication