THE SYNTACTIC GRAPH OF A SOFIC SHIFT IS INVARIANT UNDER SHIFT EQUIVALENCE

DOI10.1142/S0218196706003050zbMath1098.68062MaRDI QIDQ5483448

Dominique Perrin, Marie-Pierre Béal, Francesca Fiorenzi

Publication date: 14 August 2006

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

zbMATH Keywords

symbolic dynamicsautomata and formal languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Semigroups in automata theory, linguistics, etc. (20M35) Symbolic dynamics (37B10)

Related Items (5)

Pseudovarieties defining classes of sofic subshifts closed under taking shift equivalent subshifts. ⋮ A new algebraic invariant for weak equivalence of sofic subshifts ⋮ A categorical invariant of flow equivalence of shifts ⋮ CONJUGACY INVARIANTS OF SUBSHIFTS: AN APPROACH FROM PROFINITE SEMIGROUP THEORY ⋮ A hierarchy of shift equivalent sofic shifts

Cites Work

• Unnamed Item
• On sofic systems. I
• On sofic systems. II
• A conjugacy invariant for reducible sofic shifts and its semigroup characterizations
• The Williams conjecture is false for irreducible subshifts
• Symbolic dynamics. One-sided, two-sided and countable state Markov shifts
• Minimal automaton for a factorial, transitive, and rational language
• Subshifts of finite type and sofic systems
• A characterization of strictly locally testable languages and its application to subsemigroups of a free semigroup
• On a syntactically defined invariant of symbolic dynamics
• MINIMAL FORBIDDEN PATTERNS OF MULTI-DIMENSIONAL SHIFTS
• Puissance extérieure d'un automate déterministe, application au calcul de la fonction zêta d'un système sofique
• On the structure of a sofic shift space
• An Introduction to Symbolic Dynamics and Coding
• Endomorphisms and automorphisms of the shift dynamical system

This page was built for publication: THE SYNTACTIC GRAPH OF A SOFIC SHIFT IS INVARIANT UNDER SHIFT EQUIVALENCE