Polynomial-time algorithm for fixed points of nontrivial morphisms

DOI10.1016/J.DISC.2009.03.019MaRDI QIDQ1044983zbMATH OpenOpenAlexFDO

Authors Štěpán Holub

Publication date 15 December 2009

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2009.03.019

zbMATH Keywords

fixed pointmorphical primitivitypolynomial algorithm

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Recommendations

• Complexity of testing morphic primitivity
• scientific article; zbMATH DE number 2051165
• On two-sided infinite fixed points of morphisms
• scientific article; zbMATH DE number 1390089
• Linear-time version of Holub's algorithm for morphic imprimitivity testing

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

Cited in

(21)

• Reachability problems in nondeterministic polynomial maps on the integers
• The Billaud conjecture for \(|\varSigma| = 4\), and beyond
• Fine costs for Euclid's algorithm on polynomials and Farey maps
• Ambiguity of morphisms in a free group
• Inferring descriptive generalisations of formal languages
• scientific article; zbMATH DE number 3915627 (Why is no real title available?)
• Weakly unambiguous morphisms
• scientific article; zbMATH DE number 2051165 (Why is no real title available?)
• Linear-Time Version of Holub’s Algorithm for Morphic Imprimitivity Testing
• Linear-time version of Holub's algorithm for morphic imprimitivity testing
• Complexity of testing morphic primitivity
• Fixed points of morphisms among binary generalized pseudostandard words
• Restricted ambiguity of erasing morphisms
• On a conjecture about finite fixed points of morphisms
• Detecting Fully Irreducible Automorphisms: A Polynomial Time Algorithm
• On Billaud words and their companions
• On Billaud words and their companions
• On two-sided infinite fixed points of morphisms
• A polynomial-time computable curve whose interior has a nonrecursive measure
• A polynomial-time algorithm for computing the yolk in fixed dimension
• The Billaud conjecture for alphabet size 4

This page was built for publication: Polynomial-time algorithm for fixed points of nontrivial morphisms

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