There are a number of connexions between the theory of finite automata and symbolic dynamics, as first pointed out by Adler and Weiss and appearing in the paper of 1973 by Benjamin Weiss introducing sofic systems.

As an example, the classical property of the existence of a unique minimal deterministic automaton recognizing a given formal language has a natural counterpart with the existence of a minimal presentation of sofic shifts, usually called the Fischer cover.

In a more interesting perspective, the classification of subshifts up to various kinds of reductions (including shift equivalence) has a counterpart in the classification of formal languages up to finite-state transformations (such as sequential mappings).

In this talk, I will present several results connecting both fields, including results on length distributions obtained together with Frederique Bassino and Marie-Pierre Beal (see also the talk of Marie-Pierre Beal in the same meeting). Other topics include the so-called road-coloring problem and Krieger's embedding theorem.

References

• Marie-Pierre Beal and Dominique Perrin, Symbolic dynamics and finite automata, in Handbook of Formal Languages, G. Rosenberg and A. Salomaa eds., vol. 2, Springer verlag, 1997, 463-506. http://www-igm.univ-mlv.fr/~beal/Recherche/MiseAJourHandBook/Handbook.ps

• Benjamin Weiss, Subshifts of finite type and sofic systems, Monats. Math., 77, 462-474, 1973.

• Frederique Bassino, Marie-Pierre Beal, Dominique Perrin, A "finite state" version of the Kraft-McMillan theorem, rapport IGM 97-27, 1997, http://www-igm.univ-mlv.fr/~beal/Recherche/Publications/super.ps

• John Ashley, Brian Marcus, Dominique Perrin and Selim Tuncel, Surjective extensions of sliding block codes, SIAM J. Discrete Math., 1993, 6, 582-611.

• Dominique Perrin, Marcel-Paul Schutzenberger, Synchronizing words and automata and the road coloring problem, in Symbolic Dynamics and its Applications, 1992, Peter Walters ed., 295-318, American Mathematical Society, Contemporary Mathematics, vol. 135.

Materials used used during the talk

Back to Codes, Systems and Graphical Models