The Word Matching Problem Is Undecidable For Finite Special String-Rewriting Systems That Are Confluent.

Paliath Narendran Friedrich Otto

Published in: ICALP (1997)

Keyphrases

string matching
rewriting systems
pattern matching
approximate string matching
edit distance
n gram
string similarity
matching algorithm
regular expressions
suffix tree
graph matching
rewriting rules
similarity measure
keywords