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

DOI10.1016/J.TCS.2015.07.055zbMATH Open1329.68199OpenAlexW1105731415MaRDI QIDQ497670FDOQ497670

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

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

zbMATH Keywords

linear-time algorithmmorphical primitivityword morphism

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

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

Cited In (7)

• The Billaud conjecture for \(|\varSigma| = 4\), and beyond
• On Billaud words and their companions
• On Billaud words and their companions
• 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
• Crochemore's partitioning on weighted strings and applications

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)