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.
Done