File(s) under permanent embargo

Reason: This item is currently closed access.

Fast learning of restricted regular expressions and DTDs

conference contribution
posted on 05.09.2017, 15:35 by Dominik FreydenbergerDominik Freydenberger, Timo Kotzing
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 nonoptimal 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. Copyright 2013 ACM.

History

School

  • Science

Department

  • Computer Science

Published in

ACM International Conference Proceeding Series

Pages

45 - 56

Citation

FREYDENBERGER, D.D. and KÖTZING, T., 2013. Fast learning of restricted regular expressions and DTDs. ACM International Conference Proceeding Series, pp.45-56

Publisher

© Association for Computing Machinery, Inc.

Version

VoR (Version of Record)

Publisher statement

This work is made available according to the conditions of the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0) licence. Full details of this licence are available at: https://creativecommons.org/licenses/by-nc-nd/4.0/

Publication date

2013

Notes

This paper is closed access.

ISBN

9781450315982

Language

en

Usage metrics

Keywords

Exports