Finding a homomorphism between two words is NP-complete
From MaRDI portal
Publication:599499
DOI10.1016/0020-0190(79)90135-2zbMath0414.68022OpenAlexW2100850484MaRDI QIDQ599499
Grzegorz Rozenberg, Andrzej Ehrenfeucht
Publication date: 1979
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(79)90135-2
Related Items (22)
A parameterized study of maximum generalized pattern matching problems ⋮ On the parameterised complexity of string morphism problems ⋮ Inferring descriptive generalisations of formal languages ⋮ Inclusion problems for patterns with a bounded number of variables ⋮ Hide and seek with repetitions ⋮ Complexity of testing morphic primitivity ⋮ A note on the complexity of matching patterns with variables ⋮ Discontinuities in pattern inference ⋮ Detecting One-Variable Patterns ⋮ Linear-time version of Holub's algorithm for morphic imprimitivity testing ⋮ Unambiguous erasing morphisms in free monoids ⋮ The unambiguity of segmented morphisms ⋮ Unambiguous Erasing Morphisms in Free Monoids ⋮ Existence and nonexistence of descriptive patterns ⋮ Unnamed Item ⋮ Detecting patterns in finite regular and context-free languages ⋮ A Polynomial Time Match Test for Large Classes of Extended Regular Expressions ⋮ Morphically primitive words ⋮ Existence and Nonexistence of Descriptive Patterns ⋮ The hardness of solving simple word equations ⋮ Polynomial-time algorithm for fixed points of nontrivial morphisms ⋮ Pattern matching with variables: a multivariate complexity analysis
Cites Work
This page was built for publication: Finding a homomorphism between two words is NP-complete
