Abstract
Non-terminally separated (NTS) languages are a subclass of deterministic context free languages where there is a stable relationship between the substrings of the language and the non-terminals of the grammar. We show that when the distribution of samples is generated by a PCFG, based on the same grammar as the target language, the class of unambiguous NTS languages is PAC-learnable from positive data alone, with polynomial bounds on data and computation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adriaans, P.: Learning shallow context-free languages under simple distributions. Technical Report ILLC Report PP-1999-13, Institute for Logic, Language and Computation, Amsterdam (1999)
Boasson, L., Senizergues, S.: NTS languages are deterministic and congruential. J. Comput. Syst. Sci. 31(3), 332–342 (1985)
Clark, A., Eyraud, R.: Identification in the limit of substitutable context free languages. In: Jain, S., Simon, H.U., Tomita, E. (eds.) ALT 2005. LNCS (LNAI), vol. 3734, pp. 283–296. Springer, Heidelberg (2005)
Charniak, E.: Immediate head parsing for language models. In: Proceedings of the 39th annual meeting of the ACL, Toulouse, France, pp. 116–123 (2001)
Clark, A.: Learning deterministic context free grammars in the Omphalos competition. Machine Learning (to appear, 2006)
Clark, A., Thollard, F.: PAC-learnability of probabilistic deterministic finite state automata. Journal of Machine Learning Research 5, 473–497 (2004)
Clark, A., Thollard, F.: Partially distribution-free learning of regular languages from positive samples. In: Proceedings of COLING, Geneva, Switzerland (2004)
Dubhashi, D.P., Ranjan, D.: Balls and bins: A study in negative dependence. Random Structures and Algorithms 13(2), 99–124 (1998)
Harris, Z.: Distributional structure. Word 10(2-3), 146–162 (1954)
Jelinek, F., Chelba, C.: Structured language modeling for speech recognition. Computer, Speech and Language 14(4), 283–332 (2000)
Kearns, M.J., Mansour, Y., Ron, D., Rubinfeld, R., Schapire, R.E., Sellie, L.: On the learnability of discrete distributions. In: Proc. of the 25th Annual ACM Symposium on Theory of Computing, pp. 273–282 (1994)
Ron, D., Singer, Y., Tishby, N.: On the learnability and usage of acyclic probabilistic finite automata. J. Comput. Syst. Sci. 56(2), 133–152 (1998)
Senizergues, G.: The equivalence and inclusion problems for NTS languages. J. Comput. Syst. Sci. 31(3), 303–331 (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Clark, A. (2006). PAC-Learning Unambiguous NTS Languages. In: Sakakibara, Y., Kobayashi, S., Sato, K., Nishino, T., Tomita, E. (eds) Grammatical Inference: Algorithms and Applications. ICGI 2006. Lecture Notes in Computer Science(), vol 4201. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11872436_6
Download citation
DOI: https://doi.org/10.1007/11872436_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-45264-5
Online ISBN: 978-3-540-45265-2
eBook Packages: Computer ScienceComputer Science (R0)