R. Rhs, 15 return R Algorithm 4: Reduced rhs adapted for k, l-local contextually substitutability languages References [1] Noam Chomsky. On certain formal properties of grammars, Information and control, vol.2, issue.2, pp.137-167, 1959.

A. Clark, Learning deterministic context free grammars: The Omphalos competition, Machine Learning, pp.93-110, 2007.
DOI : 10.1007/s10994-006-9592-9

A. Clark, Learning trees from strings: A strong learning algorithm for some contextfree grammars, The Journal of Machine Learning Research, vol.14, issue.1, pp.3537-3559, 2013.

F. Coste, G. Garet, and J. Nicolas, Local substitutability for sequence generalization, Proceedings of the Eleventh International Conference on Grammatical Inference, ICGI 2012, pp.97-111, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00730553

F. Coste, G. Garet, and J. Nicolas, A bottom-up efficient algorithm learning substitutable languages from positive examples, Proceedings of the 12th International Conference on Grammatical Inference, ICGI 2014, pp.49-63, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01080249

F. Coste, F. Luque, G. Garet, and J. Nicolas, Learning efficiently substitutable context-free languages from positive examples by reduction, pp.1001-1028, 2016.

C. De and L. Higuera, Characteristic sets for polynomial grammatical inference, Machine Learning, pp.125-138, 1997.

C. De and L. Higuera, A bibliographical study of grammatical inference, Pattern recognition, vol.38, issue.9, pp.1332-1348, 2005.
URL : https://hal.archives-ouvertes.fr/ujm-00376590

J. Earley, An efficient context-free parsing algorithm, Communications of the ACM, vol.13, issue.2, pp.94-102, 1970.
DOI : 10.1145/362007.362035

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=

D. Fredouille, H. Christopher, and . Bryant, Speeding up Parsing of Biological Context-Free Grammars, Combinatorial Pattern Matching, pp.241-256, 2005.
DOI : 10.1007/11496656_21

E. Mark and G. , Language identification in the limit, Information and control, vol.10, issue.5, pp.447-474, 1967.

M. Stuart, Y. Shieber, . Schabes, C. Fernando, and . Pereira, Principles and implementation of deductive parsing. The Journal of logic programming, pp.3-36, 1995.

R. Yoshinaka, Identification in the Limit of k,l-Substitutable Context-Free Languages, Proceedings of the 9th international colloquium conference on Grammatical inference: theoretical results and applications, ICGI'08, pp.266-279, 2008.
DOI : 10.1007/978-3-540-88009-7_21