Repetitiveness of D0L-languages is decidable in polynomial time

DOI10.1007/BFB0029977MaRDI QIDQ4699310zbMATH OpenFDO

Authors Friedrich Otto, Yuji Kobayashi

Publication date 17 October 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0029977

zbMATH Keywords

languages generated by morphismssubwords

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Languages polylog-time reducible to dot-depth 1/2
• Bounds for the D0L language equivalence problem
• A new bound for the D0L language equivalence problem
• Repetitiveness of languages generated by morphisms
• Simple reductions between D0L language and sequence equivalence problems
• scientific article; zbMATH DE number 4047163
• Kolmogorov Complexity and Deterministic Context-Free Languages
• A predicative and decidable characterization of the polynomial classes of languages
• On almost cylindrical languages and the decidability of the D0L and PWD0L primitivity problems
• scientific article; zbMATH DE number 1936756

Cited in

(5)

• Languages, D0L-systems, sets of curves, and surface automorphisms.
• Repetitiveness of languages generated by morphisms
• Repetition of subwords in DOL languages
• If a DOL language is k-power free then it is circular
• An algorithm for enumerating all infinite repetitions in a D0L-system

This page was built for publication: Repetitiveness of D0L-languages is decidable in polynomial time

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