Alladi Ramakrishnan Hall

Graphs and sequences

Didier Caucal

University Paris Est-Marne la Vallee

A sequence is an omega-word that we recognize in base k by a deterministic and complete k-automaton (finite or not). A sequence is k-symmetric if it can be recognized by a vertex-transitive k-automaton. We show that such automata form a family of graphs defined since 1878 and for which a first structural characterization is obtained.