Published in Volume XXIV, Issue 2, 2014, pages 253-286, doi: 10.7561/SACS.2014.2.253

Authors: M. Marin, G. Istrate

Abstract

We consider the problem of learning an unknown context-free gram- mar from its structural descriptions with depth at most ℓ. The structural descriptions of the context-free grammar are its unlabelled derivation trees. The goal is to learn a cover context-free grammar (CCFG) with respect to ℓ, that is, a CFG whose structural descriptions with depth at most ℓ agree with those of the unknown CFG. We propose an algorithm, called LAℓ, that efficiently learns a CCFG using two types of queries: structural equivalence and structural membership. The learning proto- col is based on what is called in the literature a “minimally adequate teacher.” We show that LAℓ runs in time polynomial in the number of states of a minimal deterministic finite cover tree automaton (DCTA) with respect to ℓ. 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 Text (PDF)

References

[1] Dana Angluin. Learning regular sets from queries and counterex- amples. Information and Computation, 75(2):87–106, 1987. http://dx.doi.org/10.1016/0890-5401(87)90052-6 .

[2] Dana Angluin and Michael Kharitonov. When won’t membership queries help? Journal of Computer and System Sciences, 50(2):336–355, 1995. http://dx.doi.org/10.1006/jcss.1995.1026 .

[3] Walter S. Brainerd. The minimalization of tree automata. Informa- tion and Control, 13(5):484–491, 1968. http://dx.doi.org/10.1016/S0019-9958(68)90917-0 .

[4] Cezar Câmpeanu, Nicolae Sântean, and Sheng Yu. Minimal cover- automata for finite languages. Theoretical Computer Science, 267(1– 2):3–16, 2001. Workshop on Implementing Automata ’98. http://dx.doi.org/10.1016/S0304-3975(00)00292-9.

[5] Colin De la Higuera. Grammatical inference: Learning automata and Grammars. Cambridge University Press, 2010.

[6] Azadeh Farzan, Yu-Fang Chen, Edmund M. Clarke, Yih-Kuen Tsay, and Bow-Yaw Wang. Extending automated compositional verification to the full class of omega-regular languages. In C. R. Ramakrishnan and Jakob Rehof, editors, Proceedings of the 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, (TACAS 2008), Held as Part of the Joint European Conferences on Theory and Practice of Software (ETAPS 2008), volume 4963 of Lecture Notes in Computer Science, pages 2–17. Springer, 2008. http://dx.doi.org/10.1007/978-3-540-78800-3_2 .

[7] John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. Pearson Addison Wesley, second edition, 2003.

[8] Florentin Ipate. Learning finite cover automata from queries. Journal of Computer and System Sciences, 78(1):221–244, 2012. http://dx.doi.org/10.1016/j.jcss.2011.04.002 .

[9] Viraj Kumar, P. Madhusudan, and Mahesh Viswanathan. Minimization, learning, and conformance testing of boolean programs. In Christel Baier and Holger Hermanns, editors, Proceedings of the 17th International Conference on Concurrency Theory (CONCUR 2006), volume 4137 of Lecture Notes in Computer Science, pages 203–217. Springer, 2006. http://dx.doi.org/10.1007/11817949_14 .

[10] Leon S. Levy and Aravind K. Joshi. Skeletal structural descrip- tions. Information and Control, 39(2):192–211, 1978. http://dx.doi.org/10.1016/S0019-9958(78)90849-5 .

[11] Oded Maler and Amir Pnueli. On the learnability of infinitary regular sets. Information and Computation, 118(2):316–326, 1995. http://dx.doi.org/10.1006/inco.1995.1070 .

[12] Yasubumi Sakakibara. Learning context-free grammars from structural data in polynomial time. Theoretical Computer Science, 76(2-3):223–242, 1990. http://dx.doi.org/10.1016/0304-3975(90)90017-C .

[13] Michael Sipser. Introduction to the Theory of Computation. Thomson, 2nd edition, 2006.

Bibtex

@article{sacscuza:marin2014lccgfsd,
  title={Learning Cover Context-Free Grammars from Structural Data},
  author={M. Marin and G. Istrate},
  journal={Scientific Annals of Computer Science},
  volume={24},
  number={2},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2014},
  pages={253--286},
  doi={10.7561/SACS.2014.2.253},
  publisher={``A.I. Cuza'' University Press}
}