Freydenberger_Reidenbach_COLT_2010[1].pdf (256.93 kB)
Download fileInferring descriptive generalisations of formal languages
conference contribution
posted on 2010-07-06, 10:42 authored by Dominik FreydenbergerDominik Freydenberger, Daniel ReidenbachIn the present paper, we introduce a variant of Gold-style learners that is not required to infer precise
descriptions of the languages in a class, but that must find descriptive patterns, i.e., optimal
generalisations within a class of pattern languages. Our first main result characterises those indexed
families of recursive languages that can be inferred by such learners, and we demonstrate that this
characterisation shows enlightening connections to Angluin’s corresponding result for exact inference.
Using a notion of descriptiveness that is restricted to the natural subclass of terminal-free
E-pattern languages, we introduce a generic inference strategy, and our second main result characterises
those classes of languages that can be generalised by this strategy. This characterisation
demonstrates that there are major classes of languages that can be generalised in our model, but not
be inferred by a normal Gold-style learner. Our corresponding technical considerations lead to deep
insights of intrinsic interest into combinatorial and algorithmic properties of pattern languages.
History
School
- Science
Department
- Computer Science
Citation
FREYDENBERGER, D.D. and REIDENBACH, D., 2010. Inferring descriptive generalisations of formal languages. IN: Kalai, A.T. and Mohri, M. (eds). COLT 2010: Proceedings of the 23rd Conference on Learning Theory, Haifa, Israel, June 27-29, 2010. Madison, Wisconsin : OmniPress, pp. 194-206.Publisher
OmniPress for the Association for Computational Learning (ACL) / © The authorsVersion
- AM (Accepted Manuscript)
Publication date
2010Notes
This conference paper is also freely available online from: http://www.colt2010.org/proceedings.htmlISBN
9780982252925Language
- en