4
$\begingroup$

Grammar induction of Context Free Languages seems to be a very well researched field. I would like to know the current state of the art in inducing a Context Free Grammar (I am reading up Higuera's Grammatical Inference book, and looking through previous papers). What is the current bound on inducing a Context Free Grammar given unstructured (non parenthesized) input?

In particular, I would like to know the community's opinion on the paper by Bastani et al. Synthesizing Program Input Grammars. How it compares to existing work. Does it improve the algorithmic bounds?

Improve this question
$\endgroup$
1
  • $\begingroup$ I do not have the privilege for creating tags: I wish these tags were added: grammar-inference grammar-induction $\endgroup$
    – Rahul Gopinath
    Nov 23, 2018 at 10:07

1 Answer 1

Reset to default
2
$\begingroup$

de la Higuera's book focuses mostly on the classical theory of Angluin style learning of finite state automata and related results. This theory has been lifted to the class of context free grammars and beyond to multiple context free grammars etc. using what is called "distributional learning" which in its modern form started with Clark & Eyraud paper in JMLR 2007 (I was the first author). The most recent papers in this line of research are Chihiro Shibata, Ryo Yoshinaka: Probabilistic learnability of context-free grammars with basic distributional properties from positive examples. Theor. Comput. Sci. 620: 46-72 (2016) which looks at learning when the samples are generated by a PCFG. There are analogues of the basic Angluin results using membership queries etc as well, and results for strong learning where you want to recover a CFG which generates the same trees as the target grammar (Learning Trees from Strings, Clark JMLR 2013). (Apologies for the self citations)

I wasn't familiar with the Bastani paper, but it seems to be a heuristic paper with no theoretical guarantees.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you so much for the answer, and the hints on which papers to look at. (I was wondering why the paper by Bastani et al. was comparing to L-Star and RPNI, both of which are algorithms on identifying automata, and some what old at this point. They do cite (Higuera 2010), but miss out on a lot of important work such as yours). $\endgroup$
    – Rahul Gopinath
    Nov 29, 2018 at 12:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.