Minimal forbidden words and symbolic dynamics

M -P. Béal, F. Mignosi, A. Restivo

IBP-Litp 1995/59: Rapport de Recherche Litp / Litp research reports
14 pages - Janvier/January 1996 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: Minimal forbidden words and symbolic dynamics

Résumé : Nous introduisons une nouvelle mesure de complexité pour un langage factoriel L: le taux de croissance de l'ensemble des mots interdits minimaux. Nous prouvons quelques propriétés combinatoires des mots interdits minimaux. Nous montrons, comme principal résultat, que ce taux de croissance est un invariant topologique du système dynamique défini par L.

Abstract : We introduce a new complexity measure of a factorial formal language L: the growth rate of the set of minimal forbidden words. We prove some combinatorial properties of minimal forbidden words. As main result we prove that the growth rate of the set of minimal forbidden words for L is a topological invariant of the dynamical system defined by L.

Publications internes Litp 1995 / Litp research reports 1995