Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper deals with a class of Prolog programs, called context-free term transformations (CTF). We present a polynomial time algorithm to identify a subclass of CFT, whose program consists of at most two clauses, from positive data; The algorithm uses 2-mmg (2-minimal multiple generalization) algorithm, which is natural extension of Plotkin's least generalization algorithm, to reconstruct the pair of heads of the unknown program. Using this algorithm, we show the consistent and conservative polynomial time identifiability of the class of tree languages defined by CFTFBuniq together with tree languages defined by pairs of two tree patterns, both of which are proper subclasses of CFT, in the limit from positive data.

REFERENCES

• Ang79: Dana Angluin, Finding patterns common to a set of strings (Extended Abstract), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.130-141, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804406]
• Ang82: 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]
• ASO91: H. Arimura, T. Shinohara, and S. Otsuki. Polynomial time inference of unions of tree pattern languages. In Proceedings of the Second Workshop on Algorithmic Learning Theory, pp. 105-114, 1991.
• Ish88: H. Ishizaka, Model inference incorporating generalization, Journal of Information Processing, v.11 n.3, p.206-211, Sept. 1988
• Lio87: J. W. Lloyd, Foundations of logic programming; (2nd extended ed.), Springer-Verlag New York, Inc., New York, NY, 1987
• LMM88: J.-L. Lassez , M. J. Maher , K. Marriott, Unification revisited, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• MNL88: K. Marriott, L. Naish, and J-L. Lassez. Most specific logic programs. In Proc. 5th ICLP, pp. 909-923. MIT Press, 1988.
• Mug88: S. Muggleton. Machine invention of firstorder predicates by inverting resolution. In Proceedings of the Fifth International Conference on Machine Learning, pp. 339-352, 1988.
• Pit89: Leonard Pitt, Inductive Inference, DFAs, and Computational Complexity, Proceedings of the International Workshop on Analogical and Inductive Inference, p.18-44, October 01-06, 1989
• Plo70: G. Plotkin. A note on inductive generalization. In B. Meltzer and D. Mitchie, editors, Machine Intelligence, volume 5, pp. 153-163. Edinburgh University Press, 1970.
• Sak89: Yasubumi Sakakibara, Efficient learning of context-free grammars from positive structural examples, Information and Computation, v.97 n.1, p.23-60, March 1992 [doi>10.1016/0890-5401(92)90003-X]
• Sha81: E.Y. Shapiro. Inductive inference of theories from facts. Technical Report 192, Yale University, Department of Computer Science, 1981.
• Shi90: T. Shinohara. Inductive inference of monotonic formal systems from positive data. In Proceedings of the First International Workshop on Algorithmic Learning Theory, pp. 339-351, 1990.
• Wri89a: Keith Wright, Identification of unions of languages drawn from an identifiable class, Proceedings of the second annual workshop on Computational learning theory, p.328-333, December 1989, Santa Cruz, California, United States
• Wri89b: K. Wright, Inductive inference of pattern languages, University of Pittsburgh, Pittsburgh, PA, 1989

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

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

General Terms:
Algorithms, Theory, Verification