Path: utzoo!utgpu!watmath!maytag!water!wlrush
From: wlrush@water.waterloo.edu (Wenchantress Wench Wendall)
Newsgroups: ont.events,uw.talks
Subject: DATA STRUCTURES SEMINAR
Keywords: Mr. Ricardo Baeza-Yates, Graduate Student, Dept. of Computer Science, University of Waterloo, will speak on "Searching Regular Expressions".
Message-ID: <2227@water.waterloo.edu>
Date: 12 Apr 89 17:35:07 GMT
Distribution: ont
Organization: U of Waterloo, Ontario
Lines: 37



DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES

REVISED ROOM CHANGE!

DATA STRUCTURES SEMINAR

                       -Monday, April 17, 1989

Mr. Ricardo Baeza-Yates will speak on "Searching Regular Expressions".

TIME:          3:30-5:30 PM

ROOM:          DC 1302

ABSTRACT

We   present  algorithms  for  efficient  searching  of
regular  expressions  on  preprocessed  text. We obtain
logarithmic  (in the size of the text) average time for
a  wide  subclass of regular expressions, and sublinear
average   time   for   any  regular  expression,  hence
providing  the  first  known  algorithm to achieve this
time complexity.

The motivation behind these algorithms is the work done
in the New Oxford English Dictionary Project.

As   a  subproduct  of  the  analysis  of  one  of  the
algorithms,  a technique to solve matricial recurrences
is  proposed.  This  technique  can be applied to other
problems,   like  fringe  analysis  and  partial  match
queries in k-d tries.
           ---