An algorithm for constructing an even grammar from a language sample

ABSTRACT

Two skeleton based algorithms are presented for the grammatical inference problem. The first demonstrates the use of a new relation on internal skeleton nodes that focuses on decedent information. The second addresses those positive samples that contain repeated substrings.

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: M. Francel and D. John. Skeleton properties that guarantee a certain relationship between a language and an inference of the language, Proceedings of the 41st Southeastern Regional Meeting of the ACM, Mark Burge, editor, ACM Press 2003, pages 183--187.
• 3: 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, January 1975.
• 4: 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.
• 5: E. M. Gold. Language identification in the limit. Inf. Control, 10:447--474, 1967.
• 6: John E. Hopcroft , Rajeev Motwani , Rotwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computability, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 7: 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]
• 8: 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]
• 9: 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
• 10: 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
• 11: Michael Sipser, Introduction to the Theory of Computation, International Thomson Publishing, 1996

INDEX TERMS

Keywords:
equivalence relation, grammatical inference, skeleton