Polynomial-time algorithm for fixed points of nontrivial morphisms

DOI10.1016/J.DISC.2009.03.019zbMath1187.68364OpenAlexW2046738730MaRDI QIDQ1044983

Štěpán Holub

Publication date: 15 December 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2009.03.019

zbMATH Keywords

fixed pointpolynomial algorithmmorphical primitivity

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (9)

Ambiguity of Morphisms in a Free Group ⋮ The Billaud conjecture for \(|\varSigma| = 4\), and beyond ⋮ Inferring descriptive generalisations of formal languages ⋮ Weakly unambiguous morphisms ⋮ Complexity of testing morphic primitivity ⋮ Linear-time version of Holub's algorithm for morphic imprimitivity testing ⋮ Restricted ambiguity of erasing morphisms ⋮ 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
• Fixed languages and the adult languages of ol schemest^†
• On two-sided infinite fixed points of morphisms

This page was built for publication: Polynomial-time algorithm for fixed points of nontrivial morphisms