Linear-time version of Holub's algorithm for morphic imprimitivity testing

DOI10.1016/J.TCS.2015.07.055MaRDI QIDQ497670zbMATH OpenOpenAlexFDO

Authors Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

Publication date 25 September 2015

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

Full work available at URL https://doi.org/10.1016/j.tcs.2015.07.055

zbMATH Keywords

linear-time algorithmmorphical primitivityword morphism

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Recommendations

• Linear-Time Version of Holub’s Algorithm for Morphic Imprimitivity Testing
• Complexity of testing morphic primitivity
• Polynomial-time algorithm for fixed points of nontrivial morphisms
• Morphically primitive words
• scientific article; zbMATH DE number 777280

Cites work

• scientific article; zbMATH DE number 3940748 (Why is no real title available?)
• A fast algorithm for solving systems of linear equations with two variables per equation
• Algorithms on Strings
• Complexity of testing morphic primitivity
• Fast Algorithms for Finding Nearest Common Ancestors
• Finding a homomorphism between two words is NP-complete
• Fixed languages and the adult languages of ol schemest^†
• Linear-Time Version of Holub’s Algorithm for Morphic Imprimitivity Testing
• Morphically primitive words
• Polynomial-time algorithm for fixed points of nontrivial morphisms

Cited in

(7)

• Polynomial-time algorithm for fixed points of nontrivial morphisms
• The Billaud conjecture for \(|\varSigma| = 4\), and beyond
• Complexity of testing morphic primitivity
• Crochemore's partitioning on weighted strings and applications
• Linear-Time Version of Holub’s Algorithm for Morphic Imprimitivity Testing
• On Billaud words and their companions
• On Billaud words and their companions

This page was built for publication: Linear-time version of Holub's algorithm for morphic imprimitivity testing

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