Ergodic Theory and Dynamical Systems · 1983 · 65 citations · 14 references
Natural SciencesMathematicsCombinatoricsDynamical SystemsTopologyGraph TheoryGroup TheorySymbolic DynamicsGraph HomomorphismsGraph IsomorphismShifts Of Finite TypeSubshifts Of Finite TypeTopological Conjugacy
Abstract The global maps of homomorphisms of directed graphs are very closely related to homomorphisms of a class of symbolic dynamical systems called subshifts of finite type. In this paper, we introduce the concepts of ‘induced regular homomorphism’ and ‘induced backward regular homomorphism’ which are associated with every homomorphism between strongly connected graphs whose global map is finite-to-one and onto, and using them we study the structure of constant-to-one and onto global maps of homorphisms between strongly connected graphs and that of constant-to-one and onto homomorphisms of irreducible subshifts of finite type. We determine constructively, up to topological conjugacy, the subshifts of finite type which are constant-to-one extensions of a given irreducible subshift of finite type. We give an invariant for constant-to-one and onto homomorphisms of irreducible subshifts of finite type.
14
Dominic Welsh · Bulletin of the London Mathematical Society · 1974 · 1.1K citations
Classification of Subshifts of Finite Type
R. F. Williams · Annals of Mathematics · 1973 · 251 citations
The Theory of Definite Automata
Micha A. Perles, M. O. Rabin, Eliahu Shamir · IEEE Transactions on Electronic Computers · 1963 · 172 citations