[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Generalization Algorithms for Second-Order Terms

  • Conference paper
Inductive Logic Programming (ILP 2004)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 3194))

Included in the following conference series:

Abstract

In this paper, we study the generalization algorithms for second-order terms, which are treated as first-order terms with function variables, under an instantiation order denoted by≽. First, we extend the least generalization algorithm lg for a pair of first-order terms under≽, introduced by Plotkin and Reynolds, to the one for a pair of second-order terms. The extended algorithm lg, however, is insufficient to characterize the generalization for a pair of second-order terms, because it computes neither the least generalization under≽nor the structure-preserving generalization. Since the transformation rule for second-order matching algorithm consists of an imitation and a projection, in this paper, we introduce the imitation-free generalization algorithm ifg and the projection-free generalization algorithm pfg. Then, we show that ifg computes the least generalization under≽of any pair of second-order terms, whereas pfg computes the generalization equivalent to lg under≽. Nevertheless, neither ifg nor pfg preserves the structural information. Hence, we also introduce the algorithm spg and show that it computes a structure-preserving generalization. Finally, we show that the algorithms lg, pfg and spg are associative, while the algorithm ifg is not.

This work is partially supported by Grand-in-Aid for Scientific Research 15700137 and 16016275 from the Ministry of Education, Culture, Sports, Science and Technology, Japan, and 13558036 from the Japan Society for the Promotion of Science.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Baxter, L.D.: The complexity of unification, Doctoral Thesis, Department of Computer Science, University of Waterloo (1977)

    Google Scholar 

  2. Dietzen, S., Pfenning, F.: Higher-order and modal logic as a framework for explanation-based generalization. Mach. Learn. 9, 23–55 (1992)

    Google Scholar 

  3. Farmer, W.M.: Simple second-order languages for which unification is undecidable. Theor. Comput. Sci. 87, 25–41 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  4. Feng, C., Muggleton, S.: Towards inductive generalisation in higher order logic. In: Proc. 9th Internat. Conf. Machine Learning, pp. 154–162 (1992)

    Google Scholar 

  5. Goldfarb, W.D.: The undecidability of the second-order unification problem, Theor. Comput. Sci. 13, 225–230 (1981)

    MATH  MathSciNet  Google Scholar 

  6. Harao, M.: Proof discovery in LK system by analogy. In: Shyamasundar, R.K. (ed.) ASIAN 1997. LNCS, vol. 1345, pp. 197–211. Springer, Heidelberg (1997)

    Chapter  Google Scholar 

  7. Hasker, R.: The reply of program derivations, Ph.D. Thesis, Department of Computer Science, University of Illinois at Urbana-Champaign (1995)

    Google Scholar 

  8. Hirata, K., Yamada, K., Harao, M.: Tractable and intractable second-order matching problems. J. Symb. Comput. 37, 611–628 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  9. Huet, G.P.: A unification algorithm for typed λ-calculus. Theor. Comput. Sci. 1, 27–57 (1975)

    Article  MathSciNet  Google Scholar 

  10. Huet, G.P., Lang, B.: Proving and applying program transformations expressed with second-order patterns. Acta Inform. 11, 31–55 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  11. Kapur, D., Narendran, P.: Complexity of unification problems with associativecommutative operators. J. Auto. Reason. 9, 261–288 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  12. Lassez, J.-L., Maher, M.J., Marriot, L.: Unification revisited. In: Minker, J. (ed.) Foundations of deductive databases and logic programming, pp. 587–625. Morgan-Kaufmann, San Francisco (1988)

    Google Scholar 

  13. Lu, J., Mylopoulos, J., Harao, M., Hagiya, M.: Higher order generalization and its application in program verification. Ann. Math. Artif. Intel. 28, 107–126 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  14. Miller, D.: A logic programming language with lambda-abstraction, function variables, and simple unification. J. Logic Comput. 1, 497–536 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  15. Muggleton, S.: Inverse entailment and Progol, New Generat. Comput. 13, 245–286 (1995)

    Google Scholar 

  16. Nienhuys-Cheng, S.-H., de Wolf, R.: Foundations of Inductive Logic Programming. LNCS(LNAI), vol. 1228. Springer, Heidelberg (1997)

    Google Scholar 

  17. Pfenning, F.: Unification and anti-unification in the calculus of constructions. In: Proc. 6th Annual Symp. Logic in Computer Science, pp. 74–85 (1991)

    Google Scholar 

  18. Plotkin, G.D.: A note on inductive generalization. Mach. Intel. 5, 153–163 (1970)

    MathSciNet  Google Scholar 

  19. Reynolds, J.C.: Transformational systems and the algebraic structure of atomic formulas. Mach. Intel. 5, 135–152 (1970)

    MathSciNet  Google Scholar 

  20. Suzuki, Y., Inomae, K., Shoudai, T., Miyahara, T., Uchida, T.: A polynomial time matching algorithm of structured ordered tree patterns for data mining from semistractural data. In: Matwin, S., Sammut, C. (eds.) ILP 2002. LNCS (LNAI), vol. 2583, pp. 270–284. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  21. Suzuki, Y., Shoudai, T., Matsumoto, S., Uchida, T.: Efficient learning of unlabeled term trees with contractible variables from positive data. In: Horváth, T., Yamamoto, A. (eds.) ILP 2003. LNCS (LNAI), vol. 2835, pp. 347–364. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Artificial Intelligence,  

    Kouichi Hirata & Masateru Harao

  2. Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology, Kawazu 680-4, Iizuka, 820-8502, Japan

    Takeshi Ogawa

Authors
  1. Kouichi Hirata
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Takeshi Ogawa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Masateru Harao
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Faculdade de Engenharia & LIAAD, Universidade do Porto, Portugal

    Rui Camacho

  2. Department of Computer Science, Penglais, Aberystwyth, Ceredigion, University of Wales, SY23 3DB, Wales, UK

    Ross King

  3. Dept. of Computer Science and Engineering & Centre for Health Informatics, University of New South Wales, Sydney

    Ashwin Srinivasan

Rights and permissions

Reprints and permissions

Copyright information

© 2004 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Hirata, K., Ogawa, T., Harao, M. (2004). Generalization Algorithms for Second-Order Terms. In: Camacho, R., King, R., Srinivasan, A. (eds) Inductive Logic Programming. ILP 2004. Lecture Notes in Computer Science(), vol 3194. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30109-7_14

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-30109-7_14

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-22941-4

  • Online ISBN: 978-3-540-30109-7

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation