VIERAILULUENTO
Dr. Alvis Brazma (Riika) pitää torstaina 12.10.1995 klo 10.15 - 12
tietojenkäsittelytieteen laitoksen salissa A318 vierailuluennon
aiheesta
Learning Subclasses of Regular Expressions from One Good Example
and some Applications to Genome Informatics.
Abstract
The problem of inductive generalization (learning) of regular languages from
one 'good' example is considered. An almost linear time method restoring simple
regular expressions from one good example is presented. In particular, two
cases are considered. The first case is of expressions of star-height one with
one or no union operations under each iteration. The second case is expressions
without union operations, but the generalization is performed from examples
which may contain errors (i.e., some level of noise is permitted). In both
cases the class of target expressions and the notion of good examples are
defined, and the correctness of the algorithms is proved. A generalized
algorithm that can synthesize simple expressions containing unions from noisy
examples has been implemented and some computer experiments show that the
algorithm is quite practical and may have applications in genome informatics.
Tervetuloa!
Esko Ukkonen