Symbolic Dynamics and Finite Automata^{∗}

Dominique Perrin Université de Marne la Vallée 93166 Noisy le Grand France

July 5, 1996

Abstract

In this survey, we present some connections between notions and results in automata theory and other ones in symbolic dynamics.

1 Introduction

Symbolic dynamics is a field born with the work in topology of Marston Morse at the beginning of the years 20 [25]. It is, according to Morse, an “algebra and geometry of recurrence”. The idea is to study the sequences of symbols obtained by scanning the successive regions of a surface met while following a trajectory starting from a given point. A further paper by Morse and Hedlund ([24]) gives the basic results of this theory. Later, the theory was developed by many authors as a branch of ergodic theory (see for example the collected works in [32] or [7]). One of the main directions of research has been the problem of the isomorphism of subshifts of finite type (see below the definition of these objects). It is not yet completely solved although the last results of Kim and Roush [21] indicate a counterexample to a long-standing conjecture formulated by F. Williams [34].

There are many links between symbolic dynamics and the theory of automata, as pointed out by R. Adler and B. Weiss ([33]). The interplay is interesting to explore since it brings new problems and methods. In this paper, I will present some of these interconnections and report some of the new results that have been obtained in this direction together with some interesting open problems.

The material presented here does not cover all existing connections of this kind. There are in particular interesting links between symbolic dynamics and representation of numbers that are not presented here (see [17]). There are also important connections with cellular automata (see e.g. [11]).

∗To appear in Proceedings of MFCS 95, Lecture Notes in Comput. Sci., Springer, 1995

2 What is symbolic dynamics about?

We present in this Section a short introduction to the concepts of symbolic dynamics. For a more detailed exposition, we refer to [32].

We consider the set A^{Z} of two-sided infinite words as a topological space with respect to the usual product topology. The shift transformation σ acts on A^{Z} bijectively. It associates to x ∈ A^{Z} the element y = σ(x) ∈ A^{Z} defined for n ∈ Z by

y_{n} = x_{n+1}

A symbolic dynamical system or subshift is a subset S of A^{Z}which is both

1. closed and,

2. shift-invariant i.e. such that σ(S) = S.

The system is denoted S or (S, σ) to emphasize the role of the shift σ. For example, (A^{Z}, σ) itself is a symbolic dynamical system, often called the full shift in contrast with other ones called subshifts to refer to the embedding in A^{Z}.

It is not difficult to verify that a subshift is given unambiguously by a set of ordinary finite words F = F_{S} ⊂ A^{∗} subject to the conditions to be

1. factorial: uvw ∈ F ⇒ v ∈ F.

2. extensible: ∀v ∈ F, ∃u, w ∈ F : uvw ∈ F

The subshift S is said to be irreducible if for any x, y ∈ F there is a word u such that xuy ∈ F. It is said to be primitive if there is an integer n > 0 such that all such words u can be chosen of length n.

A morphism between two subshifts (S, σ) and (T, τ) is a map f : S → T which is continuous and commutes with the shift, i.e. such that fσ = τf. When f is a morphism from S onto T, it is said that T is a factor of S.

An isomorphism or a conjugacy is a bijective morphism. If f is an isomorphism from S onto T, then S and T are said to be conjugate.

Let k ≥ 1 and let f : A^{k} → B be a function. We still denote by f the mapping from A^{Z} into B^{Z} associating to a word x ∈ A^{Z} the word y = f(x) defined for n ∈ Z by

y_{n} = f(x_{n}x_{n+1} ⋯ x_{n+k−1})

Such a function f is said to be k-local. It is well-known that a function f : S ⊂ A^{Z} → Y ⊂ B^{Z} is a morphism if it is, up to some composition with the shift, k-local for some k ≥ 0.

A morphism between subshifts can be realized by a local automaton with set of states the set A^{k−1} of words of length k − 1 and an edge between au and ub labelled (b, f(aub)). The morphism is said to be right-resolving if the automaton is deterministic.

A sofic system is a subshift S which is the set of labels of infinite paths in a finite graph labelled by the symbols of A. A sofic system is thus essentially the same as a subshift recognizable by a finite automaton.

A system of finite type is a subshift which is made of all infinite words avoiding a given finite set of words. One can prove that this notion, (as that of a sofic system) is invariant under conjugacy in the sense that any conjugate of a system of finite type is again of finite type.

Any system of finite type can be obtained, up to conjugacy, as follows: let G be a finite graph with E as its set of edges. Let S_{G} be the subshift of E^{Z} formed of all biinfinite paths in G. It is clear that S_{G} is a subshift of finite type and that any subshift of finite type defined by a set of forbidden blocks of length 2 is of that form. Clearly, any system of finite type is also a sofic system. Conversely, it follows from the definition of a sofic system that any sofic system is a factor of some system of finite type.

3 The Shannon cover

The close connection between a subshift S and the set F_{S} of its finite blocks leads to a possibility of studying the same objects from both points of view of symbolic dynamics and of finite automata as first shown by F. Blanchard and G. Hansel [10].

As a first example of a result with equivalent formulations in terms of symbolic dynamics and in terms of finite automata, the existence of a unique minimal automaton takes the following form for sofic systems.

A right-resolving cover of a sofic system S is a right-resolving morphism f : T → S from a system of finite type T = T_{G} onto S. It is minimal if the graph G has the minimal possible number of vertices.

It has been shown by Fischer [16] that an irreducible sofic system has a unique minimal right-resolving cover. It is often called the Shannon cover. It is actually essentially equivalent to the minimal deterministic automaton of the set F_{S} as shown by Danièle Beauquier (see [6],[4]).

4 Codes and finite-to-one maps

A morphism φ : S → Y is said to be finite-to-one if, for all y ∈ Y, the set φ^{−1}(y) is finite. There is a close connection between this notion and that of codes and unambiguous automata.

Indeed, let A = (Q, 1, 1) be a strongly connected automaton with a unique initial and final state 1 ∈ Q. Let X be the set of labels of simple paths from 1 to 1. The map going from paths in the automaton to their labels is finite-to-one iff the automaton is unambiguous. Moreover, the automaton is unambiguous iff the set X is recognized unambiguously and is a code.

This connection allows to translate results from codes to finite-to-one maps and conversely. For instance, a result due to Ehrenfeucht and Rosenberg says that any rational code is included in a finite maximal one (see [8] p. 62). An analogous proof can be used to obtain the following result [2]:

Theorem 1 If S, T are irreducible subshifts of finite type, and φ : S → T is a finite-to-one morphism, then there is a subshift of finite type U containing S and a finite-to-one morphism from U onto T extending φ.

The theorem of Ehrenfeucht and Rozenberg corresponds to the case where T is the full shift. The more general case where a code X is constraint to be included in a fixed factorial set F has been studied by A. Restivo who has shown that the results known previously extend to this case [28].

The paper [2] contains other results of the same kind. One of them deals with right-closing morphisms, a notion intermediary between finite-to-one and right-resolving which is defined precisely as follows.

A function φ : S → T is right-closing if whenever x, y ∈ S have a common left-infinite tail and φ(x) = φ(y) then x = y. Right-closing morphisms correspond to automata with bounded delay in the same way as right-resolving morphisms correspond to deterministic automata. The result on right-closing morphisms proved in [2] corresponds to one on codes with bounded deciphering delay proved by V. Bruyère, L. Wong and L. Zhang in [14]: any rational code with finite deciphering delay may be embedded into a rational maximal one.

Finally, the paper [2] contains an analogous result on extending morphisms belonging this time to the class of biclosing morphisms i.e. morphisms that are both left and right closing. This is related to a result proved recently by L. Zhang: any rational biprefix code can be embedded into a rational maximal one [35].

5 Shift equivalence

Let S = S_{G}, T = T_{H} be two subshifts of finite type given by the adjacency matrices M, N of the graphs G, H. In [34], R. F. Williams has introduced two equivalence relations on matrices allowing to formulate in algebraic terms the relation of conjugacy on the subshifts.

Two square matrices M, N with nonnegative coefficients are said to be elementary shift equivalent if there exist two nonnegative integral matrices U, V such that

M = UV,  N = V U  (1)

Note that M and N may be of different dimensions.

Then M and N are called strong shift equivalent if there is a chain of elementary shift equivalences between M and N. We then have the following result

Theorem 2 (Williams [34]) Two subshifts of finite type S and T given by the matrices M, N as above are conjugate iff the matrices M, N are strong shift equivalent.

Before introducing the second equivalence relation, we make two observations about strong shift equivalence.

First, the relation of strong shift equivalence is not easy to compute because in a chain (M_{1}, M_{2}, …, M_{n}) of elementary equivalences, the dimensions of the matrices M_{i} is not a priori bounded. It is actually not known whether it is recursively computable or not.

Second, it is worth noting that there is a combinatorial version of the elementary equivalence in terms of state splitting. The operation of (output) splitting is the following. It operates on a graph G transforming it in a graph G′. Let v be a vertex of G. Let I be the set of edges of G entering v and S the set of edges going out of v. Let S = S′ + S′′ be a partition of the set S. We transform the vertex v into two vertices v′, v′′ with both the set I of input edges and with S′ (resp. S′′) as set of outgoing edges for v′ (resp. v′′). The operation of output split is dual and obtained by partitioning the set I of ingoing edges instead of S.

Then it can be proved that a strong shift equivalence can be obtained by a succession of input and output splitting and conversely [34].

We now come to the second equivalence relation on square matrices. Two square matrices M and N are called shift equivalent if there exist two nonnegative integral matrices U, V and an integer k such that

\begin{aligned}MU & = & UN & , & NV & = & V M \\ M^{k} & = & UV & , & N^{k} & = & V U \end{aligned}  (2)

It is clear that k = 1 corresponds to an elementary shift equivalence and thus that strong shift equivalence implies shift equivalence.

The converse was posed by Williams as a problem: does shift equivalence imply strong shift equivalence? It was shown by Kim and Roush in [21] that the answer is negative in general. However the subshifts of their counterexample are reducible and the conjecture is still pending for irreducible subshifts of finite type.

It is interesting to note that shift equivalence has been proved decidable by Kim and Roush [20]. Also, the problem of comparing, inside a given semigroup, the various relations generalizing the group conjugacy has been studied by several authors (see [15]). It is however a different problem here since the relation is defined among square matrices of different dimensions and not inside a semigroup.

6 Entropy

The entropy of a subshift S is the limit

h(S) = lim_{n→∞} \frac{1}{n} log s_{n}

where s_{n} is the number of blocks of length n appearing in the elements of S.

Let X be a rational code and let S be the associated sofic system formed of all biinfinite sequences of elements of X. The entropy of S is equal to log(1/r) where r = r_{X} is the unique positive real number r such that

∑_{x∈X} r^{|x|} = 1.

In other terms, if α_{n} = Card(X ∩ A^{n}) and f_{X}(z) = ∑_{n≥0} α_{n}z^{n}, then r_{X} is the unique positive root of f_{X}(z) = 1. If the alphabet A has k elements, then r_{X} ≤ 1/k or equivalently

f_{X}(1/k) ≤ 1  (3)

which is Kraft’s inequality. Conversely, for any series f with positive coefficients satisfying (3), it is well-known that there exists a prefix code X on a k-symbol alphabet such that f = f_{X}.

Recall that a series f = ∑_{k≥0} f_{k}z^{k} is said to be an N-rational series if there exists a nonnegative integral n × n matrix M, and two vectors i ∈ N^{1×n}, t ∈ N^{n×1} such that identically f_{k} = iM^{k}t.

If X is a rational code, then f_{X} satisfies (3) and is additionally an N-rational series. What can be said conversely? It is tempting to conjecture that for any N-rational series f = ∑_{n≥0} α_{n}z^{n}, such that f(1/k) ≤ 1, there exists a rational prefix code X over a k-letter alphabet such that f = f_{X}.

A particular case of this is proved in [26].

If X is a finite code, then f_{X} is a polynomial and r_{X} has the property that it has no other positive real conjugate. The following result has been proved conversely by Handelman:

Theorem 3 (Handelman [19]) An algebraic integer r satisfies r = r_{X} for some finite code X iff it has no other real positive algebraic conjugate.

This result has been extended to study the star height of one-variable rational series by F. Bassino. It was known that the star height of a one variable Nrational series is at most two (see [30]). She has obtained, in the primitive case, a characterization of the series of star height one [3].

7 The road coloring problem

A classical notion in automata theory is that of a synchronizing word. We recall that, given a deterministic and complete automaton A on a state set Q, a word w is said to be synchronizing if the state reached from any state q ∈ Q after reading w is independent of q. The automaton itself is called synchronizing if there exists a synchronizing word.

A maximal prefix code X is called synchronizing if it is the set of first returns to the initial state in a synchronizing automaton.

It is clear that a necessary (but not sufficient) condition for an automaton to be synchronizing is that the underlying graph is primitive (i.e. strongly connected and the gcd of the cycle lengths is 1). The same holds for a prefix code (which is called aperiodic if it is maximal and the gcd of the word lengths is 1).

The following problem was raised in [1]. Let G be a finite directed graph with the following properties:

1. All the vertices of G have the same outdegree.

2. G is primitive.

The problem is to find, for any graph G satisfying these hypotheses, a labeling turning G into a synchronizing deterministic automaton. The problem is called the road-coloring problem because of the following interpretation: a labeling (or coloring) making the automaton synchronizing allows a traveller lost on the graph G to follow a path which is a succession of colors leading back home wherever he actually started from.

In terms of symbolic dynamics, such a labeling defines a right-resolving map f : S_{G} → A^{Z} from the system of finite type S_{G} onto a full shift which is 1-to-1 almost everywhere. In this context, a synchronizing word is called a resolving block.

It is proved in [1] that there exists a conjugate T of S_{G} such that such a map f : T → A^{Z} exists. The proof consists in considering the subshift S_{G^{(n)}}, for large enough n, where G^{(n)} is the graph having as edges the paths of length n in G. Actually, it is shown in [27] that this result can also be obtained applying a construction from [31].

The following result is proved in [27], providing a partial answer to the problem. For a prefix code X, we denote by T_{X} the usual (unlabelled) tree whose leaves correspond to the elements of X. Several prefix codes may thus correspond to the same tree according to the choice of a labeling of the sons of each node.

Theorem 4 Given a finite aperiodic prefix code X, there is a synchronizing prefix code Y such that T_{X} = T_{Y}.

The proof uses heavily the theorem of C. Reutenauer ([29]) on the noncommutative polynomial of a code.

In terms of symbolic dynamics, Theorem 4 solves positively the road-coloring problem for those graphs G satisfying the following additional assumption:

(3) All vertices except one have indegree 1.

The road-coloring problem itself remains still open.

8 The zeta function of a subshift

Let (S, σ) be a subshift and let

S_{n} = {x ∈ S | σ^{n}(x) = x}

be the set of points of period dividing n.

The zeta function of a subshift S is the series

ζ_{S}(z) = exp ∑ \frac{s_{n}}{n} z^{n}

with s_{n} = Card(S_{n}). It is an invariant under conjugacy. since the same holds for each of the coefficients s_{n} for n ≥ 1.

It was proved by R. Bowen and O. Lanford in [12] that the zeta function of a system of finite type S is a rational series. They proved actually that

ζ_{S}(z) = det(I − Mz)^{−1}

where M is the adjacency matrix of the graph defining S.

It was proved later by A. Manning [23] that the zeta function of a sofic system is also rational.

This has motivated further investigations in several directions. On one hand, J. Berstel and C. Reutenauer have extended the result of Manning to the case of a generalization of the zeta function to some formal series [9].

On the other hand M. P. Béal has introduced a new operation on finite automata, the external power allowing to obtain the zeta function of a sofic system as a combination of the values obtained on the different external powers (see [4]). This gives a different proof of the rationality of the zeta function. This proof has been later extended to a result on sets of cyclic words [5].

9 Circular codes and subshifts of finite type

Recall that X ⊂ A^{+} is called a circular code if any circular word over A has at most one decomposition as a product of words from X.

There is a close connection between the notion of a subshift of finite type and that of a circular code. Indeed, if X ⊂ A^{∗} is a finite circular code, then the set of biinfinite words having a factorization in words of X is a subshift of finite type denoted S.

Let, as in Section 6, α_{n} = Card(X ∩A^{n}) and f_{X}(z) = ∑_{n≥0} α_{n}z^{n}. The zeta function of S has the simple form

ζ_{S} = (1 − f_{X})^{−1}

and the number s_{n} of points of S of period dividing n can be computed from this formula. The number of points having period exactly n is denoted by u_{n}(S) or simply u_{n}. Obviously s_{n} and u_{n} are related by s_{n} = ∑_{d|n} u_{d}. The following inequalities are then satisfied for all n ≥ 1.

u_{n} ≤ l_{n}(k)  (4)

where l_{n}(k) is the number of points of period exactly n in the full shift over k symbols.

The length distribution (α_{n})_{n≥1} of a circular codes satisfies inequalities stronger than (3) which are obtained after expressing in 4 the integers u_{n} in terms of the α_{n}.

The first inequalities are, in explicit form:

α_{1} ≤ k
α_{2} + \frac{1}{2}(α_{1}^{2} − α_{1}) ≤ \frac{1}{2}(k^{2} − k)
… ≤ …

It was shown by Schützenberger (see [8] p. 343) that conversely

Theorem 5 (Schützenberger) A sequence α_{n} of integers is the length distribution of a circular code over a k-letter alphabet iff it satisfies the above inequalities.

This is linked in a very interesting way with a theorem of Krieger which gives a necessary and sufficient condition for the existence of a strict embedding of a subshift of finite type into another one.

Theorem 6 (Krieger [22]) Let S and T be two subshifts of finite type. Then there exists an isomorphism f from S into T with f(S) ≠ T iff

1. h_{S} < h_{T}.

2. for each n ≥ 1, u_{n}(S) ≤ u_{n}(T)

Given a finite sequence α = (α_{i})_{1≤i≤n}, let G be the renewal graph made of n simple cycles of lengths α_{1}, …, α_{n} with exactly one common point. Any circular code on the alphabet A with length distribution α defines an isomorphism from S_{G} into A^{Z}. Thus Theorem 5 gives a proof of Theorem 6 in the particular case where S is a the subshift defined by a renewal graph and T is a full shift. This raises the following questions:

1. Is it true that for any N-rational series f = ∑_{n≥0} α_{n}z^{n} whose coefficients satisfy (4) there is a rational circular code over a k-letter alphabet such that f = f_{X}?

2. Can Theorem 5 be extended to the case where the alphabet A is replaced by a circular code Y?

10 N-rational series and positive matrices

Much of the study of subshifts of finite type is linked to that of positive matrices. Indeed, a subshift of finite type is given by a finite graph which in turn is given by its adjacency matrix. The subshift of finite type itself corresponds to a class of equivalent matrices. The study of this equivalence has motivated a lot of research (see [13] for a survey).

One aspect of this research is the study of the cone of positive matrices inside the algebra of all integer matrices. The basic properties of positive matrices were obtained long ago by Perron and Frobenius. The theorem says essentially that a nonnegative real matrix has an eigenvalue of maximal modulus which is a positive real number. If it is irreducible, it has a corresponding eigenvector with positive coefficients. And if is primitive, there is only one eigenvalue of maximal modulus.

In a more recent work, Handelman [18] has proved a kind of converse of the Perron Frobenius theorem. A matrix is said to be eventually positive if some power has only strictly positive coefficients. A dominant eigenvalue is an eigenvalue α such that α > |β| for any other eigenvalue.

Theorem 7 (Handelman [18]) A matrix with integer coefficients is conjugate to an eventually positive matrix iff it has a dominant eigenvalue.

This result is very close to one due to M. Soittola (see [30]) characterizing Nrational series in one variable among Z-rational series. We quote it for series having a minimal pole i.e. a unique pole with minimal modulus.

Theorem 8 (Soittola) A Z-rational series with nonnegative integer coefficients

f = ∑_{n≥0} α_{n}z^{n}

having a minimal pole is N-rational.

In [27] we show how both theorems can be deduced from a construction leading to a basis in which the matrices have the appropriate properties.

References

[1] Roy Adler, I. Goodwin, and Benjamin Weiss. Equivalence of topological Markov shifts. Israel J. Math., 27:49–63, 1977.

[2] John Ashley, Brian Marcus, Dominique Perrin, and Selim Tuncel. Surjective extensions of sliding block codes. SIAM J. Discrete Math., 6:582–611, 1993.

[3] Frédérique Bassino. Hauteur d’étoile d’une série N-rationnelle. Technical report, Institut Gaspard Monge, 1995.

[4] Marie-Pierre Béal. Codage Symbolique. Masson, 1993.

[5] Marie-Pierre Béal and Olivier carton. Cyclic languages and languages of stabilizers. Technical report, Institut Gaspard Monge, 1995.

[6] Danièle Beauquier. Minimal automaton for a factorial, transitive rational language. Theoret. Comput. Sci., 67:65–73, 1989.

[7] Tim Bedford, Michael Keane, and Caroline Series, editors. Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces. Oxford University Press, 1991.

[8] Jean Berstel and Dominique Perrin. Theory of codes. Academic Press, 1985.

[9] Jean Berstel and Christophe Reutenauer. Zeta functions of formal languages. Trans. Amer. Math. Soc., 321:533–546, 1990.

[10] François Blanchard and Georges Hansel. Languages and subshifts. In M. Nivat and D. Perrin, editors, Automata on Infinite Words, volume 192 of Lecture notes in Computer Science, pages 138–146. Springer Verlag, 1985.

[11] François Blanchard and Alejandro Maass. On dynamical properties of generalized cellular automata. In Ricardo Baeeza-Yates and Eric Goles, editors, LATIN 95: Theoretical Informatics, volume 911 of Lecture Notes in Comput. Sci., pages 84–98, 1995.

[12] Rufus Bowen and O. Lanford. Zeta functions of restrictions of the shift transformation. Proc. Symp. Pure Math., 14:43–50, ?

[13] Mike Boyle. Symbolic dynamics and matrices. In S Friedland, V. Brualdi, and V. Klee, editors, Combinatorial and Graph-Theoretic Problems in Linear Algebra, volume 50 of IMA Volumes in Mathematics and its Applications. 1993.

[14] Véronique Bruyère, L. Wong, and Liang Zhang. On completion of codes with finite deciphering delay. European J. Combin., 11:513–521, 1990.

[15] Christian Choffrut. Conjugacy in free inverse monoids. Int. J. Alg. Comput., 3:169–188, 1993.

[16] R. Fischer. Sofic systems and graphs. Monatshefte Math., 80:179–186, 1975.

[17] Christiane Frougny and Boris Solomyak. Finite beta-expansions. Ergod. Th. & Dynam. Syst., 12:45–82, 1992.

[18] David Handelman. Positive matrices and dimension groups affiliated to C^{∗}-algebras and topological Markov chains. J. Operator Theory, 6:55–74, 1981.

[19] David Handelman. Spectral radii of primitive integral companion matrices and log-concave poynomials. In Peter Walters, editor, Symbolic Dynamics and its Applications, volume 135 of Contemporary Mathematics, pages 231– 238. Amer. Math. Soc., 1992.

[20] K. H. Kim and F. W. Roush. Decidability of shift equivalence. In Symbolic Dynamics, volume 1342 of Lecture Notes in Mathematics, pages 374–424. Springer, 1988.

[21] K. H. Kim and F. W. Roush. William’s conjecture is false for reducible matrices. J. Amer. Math. Soc., 5:213–215, 1992.

[22] Wolfgang Krieger. On the subsystems of topological Markov chains. Ergod. Th. & Dynam. Syst., 2:195–202, 1982.

[23] Anthony Manning. Axiom a diffeomorphisms have rational zeta function. Bull. London Math. Soc., 3:215–220, 1971.

[24] M. Morse and G. Hedlund. Symbolic dynamics. Amer. J. of Math., 3:286– 303, 1936.

[25] Marston Morse. Recurrent geodesics on a surface of negative curvature. Trans. Amer. Math. Soc., 22:84–110, 1921.

[26] Dominique Perrin. Arbres et séries rationnelles. C. R. Acad. Sci. Paris, 309:713–716, 1989.

[27] Dominique Perrin and Marcel-Paul Schützenberger. Synchronizing prefix codes and automata and the road coloring problem. In Peter Walters, editor, Symbolic Dynamics and its Applications, volume 135 of Contemporary Mathematics, pages 295–318. Amer. Math. Soc., 1992.

[28] Antonio Restivo. Codes and local constraints. Theoret. Comput. Sci., 72:55–64, 1990.

[29] Christophe Reutenauer. Non commutative factorization of variable length codes. J. Pure and Applied Algebra, 36:157–186, 1985.

[30] A. Salomaa and Matti Soittola. Automatic-Theoretic Aspects of Formal Power Series. New York, Springer-Verlag, 1978.

[31] Marcel-Paul Schützenberger. On synchronizing prefix codes. Inform and Control, 11:396–401, 1967.

[32] Peter Walters, editor. Symbolic Dynamics and its Applications, volume 135 of Contemporary Mathematics. Amer. Math. Soc., 1992.

[33] Benjamin Weiss. Subshifts of finite type and sofic systems. Monats. Math., 77:462–474, 1973.

[34] Frank Williams. Classification of subshifts of finite type. Ann. of Math., 98:120–153, 1973. (Errata ibid. 99:380-381,1974).

[35] Liang Zhang and Zhonghui Shen. Completion of recognizable bifix codes. Theoret. Comput. Sci., 145:345–355, 1995.