On almost cylindrical languages and the decidability of the D0L and PWD0L primitivity problems

DOI10.1016/0304-3975(95)00168-9zbMath0874.68173OpenAlexW1988348399MaRDI QIDQ671421

Juan-Miguel Gracia

Publication date: 27 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00168-9

zbMATH Keywords

undecidabilityprimitivityprimitive sequencesprimitive wordscontext-sensitive languagealmost cylindrical setD0L language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dynamical properties of PWD0L systems
• Periodicity and ultimate periodicity of D0L systems
• Automata accepting primitive words
• Morphic congruences and D0L languages
• Nondeterministic Space is Closed under Complementation
• Expanded subalphabets in the theories of languages and semigroups†
• The lattice of semiretracts of a free monoid
• Simplifications of homomorphisms

This page was built for publication: On almost cylindrical languages and the decidability of the D0L and PWD0L primitivity problems