Linear-time version of Holub's algorithm for morphic imprimitivity testing
From MaRDI portal
Publication:497670
DOI10.1016/j.tcs.2015.07.055zbMath1329.68199OpenAlexW1105731415MaRDI QIDQ497670
Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
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
Related Items (4)
The Billaud conjecture for \(|\varSigma| = 4\), and beyond ⋮ Crochemore's partitioning on weighted strings and applications ⋮ 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
- A fast algorithm for solving systems of linear equations with two variables per equation
- Fast Algorithms for Finding Nearest Common Ancestors
- 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
- Algorithms on Strings
This page was built for publication: Linear-time version of Holub's algorithm for morphic imprimitivity testing