Constructing an even grammar from a 2-element sample

ABSTRACT

This paper shows that for sample set size two, skeleton based algorithms for inferring even linear grammars either produce a language of the form {w1w2ⁿw3w4ⁿw5 | n ε Z⁺}. or a language that contains only the original samples. The proof uses the fact that the sample set size is two to create a template for the transitive closure used in generating the inferred grammar.

REFERENCES

• 1: Dana Angluin , Carl H. Smith, Inductive Inference: Theory and Methods, ACM Computing Surveys (CSUR), v.15 n.3, p.237-269, Sept. 1983 [doi>10.1145/356914.356918]
• 2: J. D. Emerald , K. G. Subramanian , D. G. Thomas, Inferring Subclasses of Contextual Languages, Proceedings of the 5th International Colloquium on Grammatical Inference: Algorithms and Applications, p.65-74, September 11-13, 2000
• 3: Margaret Francel , David J. John, An algorithm for constructing an even grammar from a language sample, Proceedings of the 42nd annual Southeast regional conference, April 02-03, 2004, Huntsville, Alabama [doi>10.1145/986537.986594]
• 4: K. Fu and T. L. Booth, Grammatical Inference: Introduction and Survey-Part I. IEEE Transactions on Systems, Man, and Cybernetics, SMC-5(1):95--111, Jan. 1975.
• 5: K. Fu and T. L. Booth, Grammatical Inference: Introduction and Survey-Part II. IEEE Transactions on Systems, Man, and Cybernetics, SMC-5(4):409--423, July 1975.
• 6: E. M. Gold. Language identification in the limit. Inf. Control, 10:447--474, 1967.
• 7: Henning Fernau, Even linear simple matrix languages: formal language properties and grammatical inference, Theoretical Computer Science, v.289 n.1, p.425-456, 23 October 2002 [doi>10.1016/S0304-3975(01)00313-9]
• 8: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 9: Takeshi Koshiba , Erkki Mäkinen , Yuji Takada, Learning deterministic even linear languages from positive examples, Theoretical Computer Science, v.185 n.1, p.63-79, Oct. 10, 1997 [doi>10.1016/S0304-3975(97)00016-9]
• 10: Takeshi Koshiba , Erkki Mäkinen , Yuji Takada, Inferring pure context-free languages from positive data, Acta Cybernetica, v.14 n.3, p.469-477, June 2000
• 11: J. A. Laxminarayana and G. Nagaraja, Incremental Inference of a subclass of even linear languages, In the proceedings of Eleventh International Conference on Advanced Computing and Communication, PSG College of Technology, Coimbatore, INDIA, 2003.
• 12: J. A. Laxminarayana and G. Nagaraja, Efficient Learning of a subclass of Regular languages, Artificial Intelligence: Theory and Practice, Proceedings of the International Conference KBCS-2002:301--310, 2002.
• 13: V. Radhakrishnan , G. Nagaraja, Inference of even linear grammars and its applications to picture description languages, Pattern Recognition, v.21 n.1, p.55-62, 1988 [doi>10.1016/0031-3203(88)90071-4]
• 14: Jose M. Sempere , Antonio Fos, Learning linear grammars from structural information, Proceedings of the 3rd International Colloquium on Grammatical Inference: Learning Syntax from Sentences, p.126-133, September 25-27, 1996
• 15: Jose M. Sempere , Pedro Garcia, Learning Locally Testable Even Linear Languages from Positive Data, Proceedings of the 6th International Colloquium on Grammatical Inference: Algorithms and Applications, p.225-236, September 23-25, 2002
• 16: Jose M. Sempere , G. Nagaraja, Learning a Subclass of Linear Languages from Positive Structural Information, Proceedings of the 4th International Colloquium on Grammatical Inference, p.162-174, July 12-14, 1998
• 17: Michael Sipser, Introduction to the Theory of Computation, International Thomson Publishing, 1996

INDEX TERMS

Keywords:
equivalence relation, grammatical inference, skeleton