Finding a homomorphism between two words in NP-complete
References (1)
- et al.
The Design and Analysis of Computer Algorithms
(1974)
Cited by (40)
Hide and seek with repetitions
2019, Journal of Computer and System SciencesCitation Excerpt :Recall first the pattern-description problem: This problem is NP-complete and it remains as hard for g non-erasing (see [21]). We begin by considering the restriction requiring that the root of the pseudo-repetition has at least 2 letters.
Linear-time version of Holub's algorithm for morphic imprimitivity testing
2015, Theoretical Computer SciencePattern matching with variables: A multivariate complexity analysis
2015, Information and ComputationInferring descriptive generalisations of formal languages
2013, Journal of Computer and System SciencesA note on the complexity of matching patterns with variables
2013, Information Processing LettersCitation Excerpt :Ehrenfeucht and Rozenberg investigate the more general problem of deciding on the existence of a (possibly erasing) morphism between two given words, which is equivalent to matching patterns without terminal symbols, where variables can also be substituted by the empty word. In both [2] and [3] the NP-completeness of these slightly different versions of the pattern matching problem described above is shown by a reduction from 3SAT. In the pattern matching community, independent from Angluinʼs work, the problem of matching patterns with variables has been rediscovered by a series of papers (see Baker [20], Amir et al. [21], Amir and Nor [22], Clifford et al. [23]).
Inclusion problems for patterns with a bounded number of variables
2012, Information and ComputationCitation Excerpt :All known cases of (non-trivial) decidability of the inclusion problem for various classes of patterns rely on the fact that for these classes, inclusion is characterized by the existence of a terminal-preserving morphism mapping one pattern to the other. This is a purely syntactical condition that, although NP-complete (cf. Ehrenfeucht and Rozenberg [8]), can be straightforwardly verified. Finding cases of inclusion that are not covered by this condition, but still decidable, could uncover (or rule out) previously unknown phenomena, and be of immediate use for related areas of research.