Morphically primitive words

DOI10.1016/j.tcs.2009.01.020zbMath1166.68036OpenAlexW1981721733MaRDI QIDQ1019730

Johannes C. Schneider, Daniel Reidenbach

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

fixed pointsmorphismscombinatorics on wordsprimitivity

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (19)

Ambiguity of Morphisms in a Free Group ⋮ The Billaud conjecture for \(|\varSigma| = 4\), and beyond ⋮ Inferring descriptive generalisations of formal languages ⋮ Weakly unambiguous morphisms ⋮ Complexity of testing morphic primitivity ⋮ Periodicity forcing words ⋮ Linear-time version of Holub's algorithm for morphic imprimitivity testing ⋮ Unambiguous erasing morphisms in free monoids ⋮ The unambiguity of segmented morphisms ⋮ Restricted ambiguity of erasing morphisms ⋮ Unambiguous Erasing Morphisms in Free Monoids ⋮ Existence and nonexistence of descriptive patterns ⋮ On Billaud words and their companions ⋮ On Billaud words and their companions ⋮ Morphically primitive words ⋮ Existence and Nonexistence of Descriptive Patterns ⋮ Polynomial-time algorithm for fixed points of nontrivial morphisms ⋮ ON THE DUAL POST CORRESPONDENCE PROBLEM ⋮ Unambiguous injective morphisms in free groups

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• On a conjecture about finite fixed points of morphisms
• Finding a homomorphism between two words is NP-complete
• Discontinuities in pattern inference
• Morphically primitive words
• Finding patterns common to a set of strings
• Decision problems for patterns
• Fixed languages and the adult languages of ol schemest^†
• The Unambiguity of Segmented Morphisms
• On Almost Periodicity Criteria for Morphic Sequences in Some Particular Cases
• UNAMBIGUOUS MORPHIC IMAGES OF STRINGS
• The Number of Partitions of a Set

This page was built for publication: Morphically primitive words