Linear-Time Version of Holub’s Algorithm for Morphic Imprimitivity Testing

DOI10.1007/978-3-642-37064-9_34MaRDI QIDQ4910477zbMATH OpenOpenAlexFDO

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

Publication date 18 March 2013

Published in Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-37064-9_34

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Recommendations

• Linear-time version of Holub's algorithm for morphic imprimitivity testing
• Hommel's procedure in linear time
• Complexity of testing morphic primitivity
• Verifying an enhanced cover array in linear time
• On Tinhofer's linear programming approach to isomorphism testing
• Polynomial-time algorithm for fixed points of nontrivial morphisms
• On the complexity of testing primality by homogeneous structures
• Deterministic polynomial identity tests for multilinear bounded-read formulae
• An efficient algorithm for testing immutability of variable-length codes
• Verification complexity of linear prime ideals

Cited in

(3)

• Ambiguity of morphisms in a free group
• Complexity of testing morphic primitivity
• Linear-time version of Holub's algorithm for morphic imprimitivity testing

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 Q4910477)