Bar-Ilan University and Johns Hopkins University
Date and time: 11.30am - 12.30pm, Friday 7th Nov, 2008
Venue: 10.08.03 (Building 10, Level 8, Room 3)
Abstract:
Traditional pattern matching assumes an input text and
pattern strings and looks for all text locations where there is a match of
the pattern to the text. Different match relations were
considered and many match approximations were proposed and examined. An
underlying assumption in these studies was that the text or pattern
might present content errors do due various causes while
the order of the contents is kept as is. While this is a reasonable
assumption in many situations, it does not answer many
applications.
In the asynchronous pattern matching model the input
text and pattern are originated at different net users. Thus, the owner of
the text is searching for a pattern delivered in packets
through asynchronous communication. Each packet has a content field -
keeping the data of the pattern location, and an address
field - keeping the original location of this content. Now, messages might
suffer from communication errors occurring on content or
address level. We start the study of the asynchronous pattern matching by
assuming a simplified model where the errors are only at the address
field. This talk presents efficient algorithms for coping
with bit-flips errors in the address field.
Organizer: Dr. Falk Scholer