Venkat Chakaravarthy (UW-Madison):
Context Sensitive String Matching
In this talk, we will discuss about context sensitive string matching
and related problems. Given a pattern (a string of variables and constants)
and a text (a string of constants), the problem is to check if
the pattern can be matched with the text by uniformly substituting
each variable with a string of constants. We shall discuss the complexity
of this problem and its weighted version. We will also look at
some related problems such as unavoidability testing and
checking the equivalence/inclusion among patterns.
Joint work with Rajasekar Krishnamurthy.