Reports

 

Finding a Homomorphism Between Two Words in NP-Complete ; CU-CS-134-78 Public Deposited

Downloadable Content

Download PDF
https://scholar.colorado.edu/concern/reports/7h149q71s
Abstract
  • We demonstrate that to find a homomorphism between two words x and y where letters of x can be chosen from an infinite alphabet and y is a word over a two letter alphabet is an NP-complete problem.
Creator
Date Issued
  • 1978-09-01
Academic Affiliation
Last Modified
  • 2019-12-21
Resource Type
Rights Statement
Language

Relationships

Items