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
Thumbnail | Title | Date Uploaded | Visibility | Actions |
---|---|---|---|---|
findingAHomomorphismBetweenTwoWordsInNpCompleteCuCs1.pdf | 2019-12-21 | Public | Download |