@inbook {IOPORT.02087044,
    author       = {Chakaravarthy, Venkatesan T. and Krishnamurthy, Rajasekar},
    title        = {The problem of context sensitive string matching.},
    year         = {2002},
    booktitle    = {Combinatorial pattern matching. 13th annual symposium, CPM 2002, Fukuoka, Japan, July 3--5, 2002. Proceedings},
    isbn         = {3-540-43862-9},
    pages        = {64-75},
    publisher    = {Berlin: Springer},
    abstract     = {Summary: In the context sensitive string matching problem, we are given a pattern and a text. The pattern is a string over variables and constants and the text is a string of constants. The goal is to find if there is a mapping from variables to strings of constants so that on applying this mapping to the pattern we get the given text. Languages like Perl and Python support such a sophisticated string matching. The problem is known to be NP-complete. In this paper, we consider a weighted version of this problem that checks how close the pattern can be matched with the text. We show that this variation is MAXSNP-complete and cannot be approximated within a factor of 3313/3312. We show that even the restriction, where the pattern consists of variables only, is NP-complete and MAXSNP-complete. When the alphabet is bounded, we give an approximation algorithm for this restriction.},
    identifier   = {02087044},
}