Complexity of testing morphic primitivity

MaRDI QIDQ5298777zbMATH OpenFDO

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

Publication date 14 June 2013

Full work available at URL https://arxiv.org/abs/1207.5690, http://www.kybernetika.cz/content/2013/2/216

zbMATH Keywords

complexityfixed pointsmorphic primitivity

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: We analyze the algorithm in [Holub, 2009], which decides whether a given word is a fixed point of a nontrivial morphism. We show that it can be implemented to have complexity in O(mn), where n is the length of the word and m the size of the alphabet.

Recommendations

• Polynomial-time algorithm for fixed points of nontrivial morphisms
• Linear-Time Version of Holub’s Algorithm for Morphic Imprimitivity Testing
• Linear-time version of Holub's algorithm for morphic imprimitivity testing
• Morphically primitive words
• On the periodicity of morphic words

Cites work

• Finding a homomorphism between two words is NP-complete
• Fixed languages and the adult languages of ol schemest^†
• scientific article; zbMATH DE number 3940748 (Why is no real title available?)
• Morphically primitive words
• On two-sided infinite fixed points of morphisms
• Polynomial-time algorithm for fixed points of nontrivial morphisms

Cited in

(9)

• Morphically primitive words
• Polynomial-time algorithm for fixed points of nontrivial morphisms
• The Billaud conjecture for \(|\varSigma| = 4\), and beyond
• The constant of recognizability is computable for primitive morphisms
• Linear-Time Version of Holub’s Algorithm for Morphic Imprimitivity Testing
• Linear-time version of Holub's algorithm for morphic imprimitivity testing
• On Billaud words and their companions
• On Billaud words and their companions
• The Billaud conjecture for alphabet size 4

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

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