Finding a homomorphism between two words in NP-complete

https://doi.org/10.1016/0020-0190(79)90135-2Get rights and content

First page preview

First page preview
Click to open first page preview

References (1)

  • A. Aho et al.

    The Design and Analysis of Computer Algorithms

    (1974)

Cited by (40)

  • Hide and seek with repetitions

    2019, Journal of Computer and System Sciences
    Citation 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.

  • Inferring descriptive generalisations of formal languages

    2013, Journal of Computer and System Sciences
  • A note on the complexity of matching patterns with variables

    2013, Information Processing Letters
    Citation 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 Computation
    Citation 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.

View all citing articles on Scopus
View full text