6533b856fe1ef96bd12b1dd5

RESEARCH PRODUCT

Minimal forbidden words and symbolic dynamics

Filippo MignosiMarie-pierre BéalAntonio Restivo

subject

Discrete mathematicsFactorial010102 general mathematics[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Symbolic dynamicsComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]0102 computer and information sciencesInvariant (physics)16. Peace & justice01 natural sciencesCombinatorics010201 computation theory & mathematicsTheoryofComputation_LOGICSANDMEANINGSOFPROGRAMSInformation complexityFormal language0101 mathematicsComputer Science::Formal Languages and Automata TheoryComputingMilieux_MISCELLANEOUSMathematicsofComputing_DISCRETEMATHEMATICSMathematics

description

We introduce a new complexity measure of a factorial formal language L: the growth rate of the set of minimal forbidden words. We prove some combinatorial properties of minimal forbidden words. As main result we prove that the growth rate of the set of minimal forbidden words for L is a topological invariant of the dynamical system defined by L.

yearjournalcountryeditionlanguage
1996-01-01
https://hal.science/hal-00619860