MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Learning XML Specifications

Timo Kötzing
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Friday, 17 February 2012
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

We study the problem of generalizing from a finite sample to an infinite language taken from a predefined language class. The two language classes we consider are subsets of the regular languages and have significance in the specification of XML documents (the classes corresponding to so called chain regular expressions, CHAREs, and to single occurrence regular expressions, SOREs).


The previous literature gave a number of algorithms for generalizing to SOREs providing a trade off between generalization speed and quality of the solution. Furthermore, a fast but non-optimal algorithm for generalizing to CHAREs is known.

For each of the two language classes we give an efficient algorithm returning a minimal generalization from the given finite sample to an element of the fixed language class; such generalizations are called descriptive. In this sense, both our algorithms are optimal.

Contact

Timo Kötzing
--email hidden
passcode not visible
logged in users only

Timo Kötzing, 02/16/2012 13:41
Timo Kötzing, 02/10/2012 10:41 -- Created document.