An algorithm for enumerating all infinite repetitions in a D0L-system

DOI10.1016/J.JDA.2015.03.006MaRDI QIDQ491624zbMATH OpenOpenAlexFDO

Authors Karel Klouda, Štěpán Starosta

Publication date 18 August 2015

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.6408

zbMATH Keywords

D0L-systemperiodicityrepetition

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Combinatorics on words (68R15)

Abstract: We describe a simple algorithm which, for a given D0L system, returns all factors $v$ such that $v^k$ is in the language of the system for all $k$. This algorithm can be used to decide whether a D0L system is repetitive.

Recommendations

• On recursive enumerability with finite repetitions
• On infinite words generated by polynomial D0L systems
• Algorithmic recognition of infinite cyclic extensions
• An infinite version of the Pólya enumeration theorem
• An enumeration algorithm for all integers nonrepresentable by some positive integers
• scientific article; zbMATH DE number 1361492
• Algorithms for Constructing Computably Enumerable Sets
• scientific article; zbMATH DE number 3934415
• Exact enumeration of acyclic deterministic automata

Cites work

• Cancellation and periodicity properties of iterated morphisms
• Decidability of periodicity for infinite words
• Elementary homomorphisms and a solution of the DOL sequence equivalence problem
• Factor complexity
• scientific article; zbMATH DE number 4112045 (Why is no real title available?)
• scientific article; zbMATH DE number 3569855 (Why is no real title available?)
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• scientific article; zbMATH DE number 1088280 (Why is no real title available?)
• If a DOL language is k-power free then it is circular
• On critical exponents in fixed points of non-erasing morphisms
• On Critical exponents in fixed points ofk-uniform binary morphisms
• On the defect theorem and simplifiability
• On the periodicity of morphisms on free monoids
• Periodicity and ultimate periodicity of D0L systems
• Repetition of subwords in DOL languages
• Repetitiveness of languages generated by morphisms

Cited in

(12)

• Substitutive systems and a finitary version of Cobham's theorem
• Lie complexity of words
• Characterization of circular D0L-systems
• Morphic words and equidistributed sequences
• Palindromic length of words and morphisms in class \(\mathcal{P}\)
• Topological invariants for words of linear factor complexity
• Automatic sequences of rank two
• The number of primitive words of unbounded exponent in the language of an HD0L-system is finite
• Circularity and repetitiveness in non-injective DF0L systems
• On the minimal components of substitution subshifts
• The limit of repetition thresholds of rich sequences
• Synchronizing delay for binary uniform morphisms

Describes a project that uses

Uses Software

• SageMath

This page was built for publication: An algorithm for enumerating all infinite repetitions in a D0L-system

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q491624)