Name
Abstract | ||
|---|---|---|
We study the problem of generalizing from a finite sample to a 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 quality of the solution and speed. 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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/s00224-014-9559-3 | Theory of Computing Systems \/ Mathematical Systems Theory |
Keywords | Field | DocType |
Subregular language learning,Single-occurrence regular expression,Chain regular expression,Descriptive generalization | Generalized star height problem,Discrete mathematics,Regular expression,XML,Generalization,Computer science,Theoretical computer science,Regular grammar,Regular language | Conference |
Volume | Issue | ISSN |
57 | 4 | 1432-4350 |
Citations | PageRank | References |
10 | 0.50 | 14 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dominik D. Freydenberger | 1 | 89 | 9.14 |
| Timo Kötzing | 2 | 443 | 38.58 |