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

Piece resolution: Towards larger perspectives

  • Conference paper
  • First Online:
Conceptual Structures: Theory, Tools and Applications (ICCS 1998)

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

Included in the following conference series:

Abstract

This paper focuses on two aspects of piece resolution in backward chaining for conceptual graph rules [13]. First, as conceptual graphs admit a first-order logic interpretation, inferences can be proven by classical theorem provers. Nevertheless, they do not use the notion of piece, which is a graph notion. So we define piece resolution over a class of first-order logical formulae: the logical rules. An implementation of this procedure has been done, and we compare the results with the classical SLD-resolution (i.e. Prolog). We point out several interesting results: it appears that the number of backtracks is strongly reduced. Second, we point out the similarities between these rules and database data dependencies. The implication problem for dependencies is to decide whether a given dependency is logically implied by a given set of dependencies. A proof procedure for the implication problem, called “chase”, was already studied. The chase is a bottom-up procedure: from hypothesis to conclusion. This paper introduces a new proof procedure which is topdown: from conclusion to hypothesis. Indeed, we show that the implication problem for dependencies can be reduced to the existence of a piece resolution.

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.

References

  1. S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, Reading, Mass., 1995.

    MATH  Google Scholar 

  2. Catriel Beeri and Moshe Y. Vardi. A proof procedure for data dependencies. Journal of the ACM, 31(4): 718–741, October 1984.

    Article  MATH  MathSciNet  Google Scholar 

  3. Chin-Liang Chang and Richard Char-Tung Lee. Symbolic Logic and Mechanical Theorem Proving. Academic Press, New York, 1973.

    MATH  Google Scholar 

  4. M. Chein and M.-L. Mugnier. Représenter des connaissances et raisonner avec des graphes. Revue d'Intelligence Artificielle, 10(1): 7–56, 1996.

    Article  MATH  Google Scholar 

  5. Alain Colmerauer. Prolog in 10 figures. Communications of the ACM, 28(12): 1296–1310, December 1985.

    Article  MathSciNet  Google Scholar 

  6. Stéphane Coulondre. Exploitation de la notion de pièce des règles de graphes conceptuels en programmation logique et en bases de données. Master's thesis, Université Montpellier II, 1997.

    Google Scholar 

  7. Jean Fargues, Marie-Claude Landau, Anne Dugourd, and Laurent Catach. Conceptual graphs for semantics and knowledge processing. IBM Journal of Research and Development, 30(1): 70–79, January 1986.

    Article  Google Scholar 

  8. Bikash Chandra Ghosh and V. Wuwongse. A direct proof procedure for definite conceptual graph programs. Lecture Notes in Computer Science, 954, 1995.

    Google Scholar 

  9. R. A. Kowalski. Predicate logic as a programming language. Proc. IFIP 4, pages 569–574, 1974.

    Google Scholar 

  10. J. W. Lloyd. Foundations of Logic Programming, Second Edition. Springer-Verlag, 1987.

    Google Scholar 

  11. Donald W. Loveland. A simplified format for the model elimination procedure. Journal of the ACM, 16(3): 233–248, July 1969.

    Article  MathSciNet  Google Scholar 

  12. Eric Salvat. Raisonner avec des opérations de graphes: graphes conceptuels et règles d'inférence. PhD thesis, Université Montpellier II, Montpellier, France, December 1997.

    Google Scholar 

  13. Eric Salvat and Marie-Laure Mugnier. Sound and complete forward and backward chainings of graph rules. In Proceedings of the Fourth International Conference on Conceptual Structures (ICCS-96), volume 1115 of LNAI, pages 248–262, Berlin, Augustl9–22 1996. Springer.

    Google Scholar 

  14. Moshe Y. Vardi. The implication and finite implication problems for typed template dependencies. Journal of Computer and System Sciences, 28(1): 3–28, February 1984.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. L.I.R.M.M. (U.M.R. 9928 Université Montpellier II/C.N.R.S.), 161 rue Ada, 34392, Montpellier cedex 5, France

    Stéphane Coulondre & Eric Salvat

Authors
  1. Stéphane Coulondre
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Eric Salvat
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Marie-Laure Mugnier Michel Chein

Rights and permissions

Reprints and permissions

Copyright information

© 1998 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Coulondre, S., Salvat, E. (1998). Piece resolution: Towards larger perspectives. In: Mugnier, ML., Chein, M. (eds) Conceptual Structures: Theory, Tools and Applications. ICCS 1998. Lecture Notes in Computer Science, vol 1453. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054914

Download citation

  • DOI: https://doi.org/10.1007/BFb0054914

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-64791-1

  • Online ISBN: 978-3-540-68673-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation