6533b82dfe1ef96bd1291d33

RESEARCH PRODUCT

Forbidden words in symbolic dynamics

Antonio RestivoFilippo MignosiMarinella SciortinoMarie-pierre Béal

subject

Discrete mathematicsApplied Mathematicsautomata and formal languages010102 general mathematics[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Symbolic dynamics[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]0102 computer and information sciencesFunction (mathematics)16. Peace & justice01 natural sciencesDecidabilitysymbolic dynamics010201 computation theory & mathematicsEquivalence relationcombinatoric on words0101 mathematicsInvariant (mathematics)Dynamical system (definition)Equivalence (measure theory)Computer Science::Formal Languages and Automata TheoryWord (group theory)ComputingMilieux_MISCELLANEOUSMathematics

description

AbstractWe introduce an equivalence relation≃between functions from N to N. By describing a symbolic dynamical system in terms of forbidden words, we prove that the≃-equivalence class of the function that counts the minimal forbidden words of a system is a topological invariant of the system. We show that the new invariant is independent from previous ones, but it is not characteristic. In the case of sofic systems, we prove that the≃-equivalence of the corresponding functions is a decidable question. As a more special application, we show, by using the new invariant, that two systems associated to Sturmian words having “different slope” are not conjugate.

yearjournalcountryeditionlanguage
2000-08-01
https://hal-upec-upem.archives-ouvertes.fr/hal-00619230