Learning Cover Context-Free Grammars from Structural Data

DOI10.1007/978-3-319-10882-7_15zbMATH Open1422.68146arXiv1404.2409OpenAlexW2115538152MaRDI QIDQ2938166FDOQ2938166

Mircea Marin, Gabriel Istrate

Publication date: 13 January 2015

Published in: Theoretical Aspects of Computing – ICTAC 2014 (Search for Journal in Brave)

Abstract: We consider the problem of learning an unknown context-free grammar when the only knowledge available and of interest to the learner is about its structural descriptions with depth at most $ell.$ The goal is to learn a cover context-free grammar (CCFG) with respect to $ell$, that is, a CFG whose structural descriptions with depth at most $ell$ agree with those of the unknown CFG. We propose an algorithm, called $L{A}^{e}ll$, that efficiently learns a CCFG using two types of queries: structural equivalence and structural membership. We show that $L{A}^{e}ll$ runs in time polynomial in the number of states of a minimal deterministic finite cover tree automaton (DCTA) with respect to $ell$. This number is often much smaller than the number of states of a minimum deterministic finite tree automaton for the structural descriptions of the unknown grammar.

Full work available at URL: https://arxiv.org/abs/1404.2409

Recommendations

• Learning cover context-free grammars from structural data
• Learning context-free grammars from structural data in polynomial time
• scientific article; zbMATH DE number 1670726
• Learning context free grammars with the syntactic concept lattice
• Efficient learning of context-free grammars from positive structural examples
• Learning context-free grammars using tabular representations
• scientific article; zbMATH DE number 2019603
• Towards dual approaches for learning context-free grammars based on syntactic concept lattices
• Canonical context-free grammars and strong learning: two approaches
• Distributional Learning of Context-Free and Multiple Context-Free Grammars

zbMATH Keywords

automata theorygrammatical inferencestructural descriptions

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational learning theory (68Q32) Grammars and rewriting systems (68Q42)

Cited In (3)

• Title not available (Why is that?)
• Learning context-free grammars from structural data in polynomial time
• Learning deterministic context free grammars: the Omphalos competition

This page was built for publication: Learning Cover Context-Free Grammars from Structural Data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2938166)