Morphically primitive words

DOI10.1016/J.TCS.2009.01.020MaRDI QIDQ1019730zbMATH OpenOpenAlexFDO

Authors Daniel Reidenbach, Johannes Schneider

Publication date 28 May 2009

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

Full work available at URL https://dspace.lboro.ac.uk/2134/4561

zbMATH Keywords

combinatorics on wordsfixed pointsprimitivitymorphisms

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Recommendations

• Primitive morphisms
• scientific article; zbMATH DE number 1004349
• On the robustness of primitive words
• Complexity of testing morphic primitivity
• Morphic primitivity and alphabet reductions

Cites work

• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Decision problems for patterns
• Discontinuities in pattern inference
• Finding a homomorphism between two words is NP-complete
• Finding patterns common to a set of strings
• Fixed languages and the adult languages of ol schemest^†
• Morphically primitive words
• On Almost Periodicity Criteria for Morphic Sequences in Some Particular Cases
• On a conjecture about finite fixed points of morphisms
• The Number of Partitions of a Set
• The Unambiguity of Segmented Morphisms
• UNAMBIGUOUS MORPHIC IMAGES OF STRINGS

Cited in

(28)

• Periodicity forcing words
• On the dual Post correspondence problem
• Polynomial-time algorithm for fixed points of nontrivial morphisms
• The Billaud conjecture for \(|\varSigma| = 4\), and beyond
• The unambiguity of segmented morphisms
• Unambiguous erasing morphisms in free monoids
• Primitive morphisms
• Morphic primitivity and alphabet reductions
• Existence and nonexistence of descriptive patterns
• Restricted ambiguity of erasing morphisms
• Some operations preserving primitivity of words
• Weakly unambiguous morphisms
• On the robustness of primitive words
• Existence and Nonexistence of Descriptive Patterns
• Unambiguous injective morphisms in free groups
• Unambiguous Erasing Morphisms in Free Monoids
• Complexity of testing morphic primitivity
• The block structure of successor morphisms
• scientific article; zbMATH DE number 6792663 (Why is no real title available?)
• scientific article; zbMATH DE number 604881 (Why is no real title available?)
• A little more about morphic Sturmian words
• Inferring descriptive generalisations of formal languages
• Relative Watson-Crick primitivity of words
• Linear-time version of Holub's algorithm for morphic imprimitivity testing
• Ambiguity of morphisms in a free group
• Morphically primitive words
• On Billaud words and their companions
• On Billaud words and their companions

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Morphically primitive words

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