Decidability of periodicity for infinite words
From MaRDI portal
Publication:4727446
DOI10.1051/ita/1986200100431zbMath0617.68063OpenAlexW69418090MaRDI QIDQ4727446
Publication date: 1986
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/92244
Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)
Related Items (33)
Automatic sequences of rank two ⋮ Periodic D0L languages ⋮ Aperiodic SFTs on Baumslag-Solitar groups ⋮ Bounded D0L languages ⋮ Prefixes of infinite words and ambiguous context-free languages ⋮ On the subword equivalence problem for morphic words ⋮ Logarithmic equal-letter runs for BWT of purely morphic words ⋮ Presentations of Schützenberger groups of minimal subshifts. ⋮ Properties of infinite words : Recent results ⋮ Iterative devices generating infinite words ⋮ Self-similarity and spectral theory: on the spectrum of substitutions ⋮ Decidable problems in substitution shifts ⋮ The set of strings mapped into a submonoid by iterates of a morphism ⋮ Periodicity Problem of Substitutions over Ternary Alphabets ⋮ An algorithm for enumerating all infinite repetitions in a D0L-system ⋮ Spectral theory of substitutions ⋮ Relations on words ⋮ Cancellation and periodicity properties of iterated morphisms ⋮ Periodic points in random substitution subshifts ⋮ A graph approach to computing nondeterminacy in substitutional dynamical systems ⋮ Regularity of sets of initial strings of periodic D0L-systems ⋮ Iterative algebras. ⋮ Periodicity of morphic words ⋮ Coding of substitution dynamical systems as shifts of finite type ⋮ On the simplification of infinite morphic words ⋮ Singular substitutions of constant length ⋮ A DECISION PROBLEM FOR ULTIMATELY PERIODIC SETS IN NONSTANDARD NUMERATION SYSTEMS ⋮ ON UNIFORMLY RECURRENT MORPHIC SEQUENCES ⋮ DECIDABILITY OF UNIFORM RECURRENCE OF MORPHIC SEQUENCES ⋮ More on morphisms and almost-periodicity ⋮ On D0L systems with immigration ⋮ Periodicity and ultimate periodicity of D0L systems ⋮ Spectrum of a Rudin-Shapiro-like sequence
Cites Work
This page was built for publication: Decidability of periodicity for infinite words