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