Learning structurally reversible context-free grammars from queries and counterexamples in polynomial time

ABSTRACT

In this paper we present an algorithm to learn languages defined by structurally reversible deterministic context-free grammars from queries and counterexamples. The algorithm works in time polynomial in input size and the size of the original grammar. A context-free grammar is said to be structurally reversible if among all non-terminal strings that might derive a given terminal string, no one is an extension of the other. The concept of learning from queries and counterexamples was introduced by D. Angluin in 1987. She showed that regular languages are polynomial-time learnable from queries and counterexamples. Since that paper there has been considerable interest in extending the result to a larger class of languages. Among structurally reversible grammars there are very simple grammars which have been recently investigated towards learnability, and weighted grammars. As the complexity of algorithm presented here does not depend on the terminal alphabet size, it is applicable to learning left Szilard languages. Weighted grammars are grammars with integer weights assigned to all symbols such that each rule preserves the weight. The vast majority context-free languages used in practice (for example, most programming languages) can be generated by weighted grammars.

REFERENCES

• 1: Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
• 2: Dana Angluin, Inference of Reversible Languages, Journal of the ACM (JACM), v.29 n.3, p.741-765, July 1982 [doi>10.1145/322326.322334]
• 3: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• 4: 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]
• 5: A. Burago. Fault-tolerance recognition for languages with stable block structure. Manuscript in preparation.
• 6: Andrzej Ehrenfeucht , Grzegorz Rozenberg, An easy proof of Greibach normal form, Information and Control, v.63 n.3, p.190-199, Dec. 1986 [doi>10.1016/S0019-9958(84)80013-3]
• 7: Takashi Yokomori, Polynomial-time learning of very simple grammars from positive data, Proceedings of the fourth annual workshop on Computational learning theory, p.213-227, August 05-07, 1991, Santa Cruz, California, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Grammar types (e.g., context-free, context-sensitive)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Theory, Verification