Directed graphs and substitutions. (English) Zbl 0993.68075

Holton, C.; Zamboni, L. Q.

Theory Comput. Syst. 34, No. 6, 545-564 (2001).

Summary: A substitution naturally determines a directed graph with an ordering of the edges incident at each vertex. We describe a simple method by which any primitive substitution can be modified (without materially changing the bi-infinite fixed points of the substitution) so that points in the substitution minimal shift are in bijective correspondence with one-sided infinite paths on its associated directed graph. Using this correspondence, we show that primitive substitutive sequences in the substitution minimal shift are precisely those sequences represented by eventually periodic paths. We use directed graphs to show that all measures of cylinders in a substitution minimal shift lie in a finite union of geometric sequences, confirming a conjecture of Boshernitzan. Our methods also yield sufficient conditions for a geometric realization of a primitive substitution to be “almost injective”.

MSC:

68R10

Graph theory (including graph drawing) in computer science

Keywords:

directed graph