Entailment and disentailment of order-sorted feature constraints | SpringerLink
Skip to main content
Springer Nature Link
Log in

Entailment and disentailment of order-sorted feature constraints

  • Conference paper
  • First Online:
Logic Programming and Automated Reasoning (LPAR 1993)

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

  • 133 Accesses

Abstract

LIFE uses matching on order-sorted feature structures for passing arguments to functions. As opposed to unification which amounts to normalizing a conjunction of constraints, solving a matching problem consists of deciding whether a constraint (guard) or its negation are entailed by the context. We give a complete and consistent set of rules for entailment and disentailment of order-sorted feature constraints. These rules are directly usable for relative simplification, a general proof-theoretic method for proving guards in concurrent constraint logic languages using guarded rules.

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. Hassan Aït-Kaci. An algebraic semantics approach to the effective resolution of type equations. Theoretical Computer Science, 45:293–351 (1986).

    Article  Google Scholar 

  2. Hassan Aït-Kaci and Roger Nasr. LOGIN: A logic programming language with built-in inheritance. Journal of Logic Programming, 3:185–215 (1986).

    Article  Google Scholar 

  3. Hassan Aït-Kaci and Roger Nasr. Integrating logic and functional programming. Lisp and Symbolic Computation, 2:51–89 (1989).

    Article  Google Scholar 

  4. Hassan Aït-Kaci and Andreas Podelski. Functions as passive constraints in LIFE. PRL Research Report 13, Digital Equipment Corporation, Paris Research Laboratory, Rueil-Malmaison, France (June 1991). (Revised, November 1992).

    Google Scholar 

  5. Hassan Aït-Kaci and Andreas Podelski. Towards a meaning of LIFE. PRL Research Report 11, Digital Equipment Corporation, Paris Research Laboratory, Rueil-Malmaison, France (1991). (Revised, October 1992; to appear in the Journal of Logic Programming).

    Google Scholar 

  6. Hassan Aït-Kaci, Andreas Podelski, and Gert Smolka. A feature-based constraint system for logic programming with entailment. In Proceedings of the 5th International Conference on Fifth Generation Computer Systems, pages 1012–1022, Tokyo, Japan (June 1992). ICOT. (Full paper to appear in Theoretical Computer Science).

    Google Scholar 

  7. Rolf Backofen and Gert Smolka. A complete and decidable feature theory. DFKI Research Report RR-30-92, German Research Center for Artificial Intelligence, Saarbrücken, Germany (1992).

    Google Scholar 

  8. Bruno Courcelle. Fundamentalproperties of infinite trees. TheoreticalComputerScience, 25:95–169 (1983).

    Google Scholar 

  9. Seif Haridi and Sverker Janson. Kernel Andorra Prolog and its computation model. In David H. D. Warren and Peter Szeredi, editors, Logic Programming, Proceedings of the 7th International Conference, pages 31–46, Cambridge, MA (1990). MIT Press.

    Google Scholar 

  10. Jean-Louis Lassez, Michael Maher, and Kimball Mariott. Unification revisited. In Jack Minker, editor, Foundations of Deductive Databases and Logic Programming, chapter 15, pages 587–625. Morgan-Kaufmann, Los Altos, CA (1988).

    Google Scholar 

  11. Michael Maher. Logic semantics for a class of committed-choice programs. In Jean-Louis Lassez, editor. Logic Programming, Proceedings of the Fourth International Conference, pages 858–876, Cambridge, MA (1987). MIT Press.

    Google Scholar 

  12. Vijay Saraswat and Martin Rinard. Concurrent constraint programming. In Proceedings of the 7th Annual ACM Symposium on Principles of Programming Languages, pages 232–245. ACM (January 1990).

    Google Scholar 

  13. Gert Smolka and Ralf Treinen. Records for logic programming. In Krzysztof Apt, editor. Logic Programming, Proceedings of the Joint International Conference and Symposium on Logic Programming, pages 240–254, Cambridge, MA (1992). MIT Press.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Paris Research Laboratory, Digital Equipment Corporation, 85, avenue Victor Hugo, 92500, Rueil-Malmaison, France

    Hassan Aït-Kaci & Andreas Podelski

Authors
  1. Hassan Aït-Kaci
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Andreas Podelski
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Andrei Voronkov

Rights and permissions

Reprints and permissions

Copyright information

© 1993 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Aït-Kaci, H., Podelski, A. (1993). Entailment and disentailment of order-sorted feature constraints. In: Voronkov, A. (eds) Logic Programming and Automated Reasoning. LPAR 1993. Lecture Notes in Computer Science, vol 698. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56944-8_37

Download citation

  • DOI: https://doi.org/10.1007/3-540-56944-8_37

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-56944-2

  • Online ISBN: 978-3-540-47830-0

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics