Complexity of testing morphic primitivity

zbMath1266.68150arXiv1207.5690MaRDI QIDQ5298777

Vojtěch Matocha, Štěpán Holub

Publication date: 14 June 2013

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

zbMATH Keywords

complexityfixed pointsmorphic primitivity

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (4)

The Billaud conjecture for \(|\varSigma| = 4\), and beyond ⋮ Linear-time version of Holub's algorithm for morphic imprimitivity testing ⋮ On Billaud words and their companions ⋮ On Billaud words and their companions

Cites Work

• Unnamed Item
• Finding a homomorphism between two words is NP-complete
• Morphically primitive words
• Polynomial-time algorithm for fixed points of nontrivial morphisms
• Fixed languages and the adult languages of ol schemest^†
• On two-sided infinite fixed points of morphisms

This page was built for publication: Complexity of testing morphic primitivity