Skip to main content
SpringerLink
Log in

Ordering Constraints over Feature Trees

  • Published:
Constraints Aims and scope Submit manuscript

Abstract

Feature trees are the formal basis for algorithms manipulating record like structures in constraint programming, computational linguistics and in concrete applications like software configuration management. Feature trees model records, and constraints over feature trees yield extensible and modular record descriptions. We introduce the constraint system FT≤ of ordering constraints interpreted over feature trees. Under the view that feature trees represent symbolic information, the relation ≤ corresponds to the information ordering (“carries less information than”). We present two algorithms in cubic time, one for the satisfiability problem and one for the entailment problem of FT≤. We show that FT≤ has the independence property. We are thus able to handle negative conjuncts via entailment and obtain a cubic algorithm that decides the satisfiability of conjunctions of positive and negated ordering constraints over feature trees. Furthermore, we reduce the satisfiability problem of Dörre's weak subsumption constraints to the satisfiability problem of FT≤ and improve the complexity bound for solving weak subsumption constraints from O(n5) to O(n3) .

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Hassan Aït-Kaci (1986). An algebraic semantics approach to the effective resolution of type equations. Theoretical Computer Science 45: 293-351.

    Google Scholar 

  2. Hassan Aït-Kaci and R. Nasr (1989). LOGIN: A logic programming language with built-in inheritance. Journal on Lisp and Symbolic Computation 2:51-89.

    Google Scholar 

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

    Google Scholar 

  4. Hassan Aït-Kaci and Andreas Podelski (1993). Entailment and disentailment of order-sorted feature constraints. In Andrei Voronkov, editor, Proceedings of the 4 th International Conference on Logic Programming and Automated Reasoning, volume 698 of Lecture Notes in Artificial Intelligence, pages 1-18, Springer-Verlag, Berlin.

    Google Scholar 

  5. Hassan Aït-Kaci and Andreas Podelski (1993). Towards a meaning of life. The Journal of Logic Programming 16(3-4): 195-234.

    Google Scholar 

  6. Hassan Aït-Kaci, Andreas Podelski, and Gert Smolka (1994). A feature-based constraint system for logic programming with entailment. Theoretical Computer Science 122(1-2): 263-283.

    Google Scholar 

  7. Rolf Backofen (1994). Expressivity and Decidability of First-order Languages over Feature Trees. Doctoral Dissertation, Universität des Saarlandes, Technische Fakultät, D-66041 Saarbr¨ucken.

    Google Scholar 

  8. Rolf Backofen (1994). Regular path expressions in feature logic. Journal of Symbolic Computation 17: 421-455.

    Google Scholar 

  9. Rolf Backofen (1995). A complete axiomatization of a theory with feature and arity constraints. The Journal of Logic Programming 24(1-2): 37-71. Special Issue on Computational Linguistics and Logic Programming.

    Google Scholar 

  10. Rolf Backofen (1996). Controlling functional uncertainty. In Wolfgang Wahlster, editor, Proceedings of 12 th European Conference on Artificial Intelligence, John Wiley & Sons, Ltd, pages 557-561.

  11. Rolf Backofen and Gert Smolka (1995). A complete and recursive feature theory. Theoretical Computer Science 146(1-2): 243-268.

    Google Scholar 

  12. Rolf Backofen and Ralf Treinen (1994). How to win a game with features. In Jean-Pierre Jouannaud, editor, 1st International Conference on Constraints in Computational Logics, Lecture Notes in Computer Science, vol. 845, pages 320-335, München, Germany, Springer-Verlag.

    Google Scholar 

  13. Ronald J. Brachman and Hector J. Levesque (1984). The tractability of subsumption in frame-based description languages. In Proceedings of the National Conference on Artificial Intelligence, pages 34-37.

  14. Bob Carpenter (1992). The logic of typed feature structures-with applications to unification grammars, logic programs and constraint resolution. Number 32 in Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge, England.

    Google Scholar 

  15. Witold Charatonik and Andreas Podelski (1996). The independence property of a class of set constraints. In Eugene C. Freuder, editor, Proceedings of the 2 nd International Conference on Principles and Practice of Constraint Programming, volume 1118 of Lecture Notes in Computer Science, pages 76-90.

  16. Witold Charatonik and Andreas Podelski. Set constraints with intersection. In Proceedings of the 12 th IEEE Symposium on Logic in Computer Science, Warsaw, Poland, pages 352-361. IEEE Computer Society Press.

  17. Alain Colmerauer (1984). Equations and inequations on finite and infinite trees. In ICOT, editor, Proceedings of the 2 nd International Conference on Fifth Generation Computer Systems, pages 85-99. Omsha Ltd., Tokyo and North-Holland, Amsterdam.

    Google Scholar 

  18. Martin Dietzfelbinger, Anna Karlin, Kurt Mehlhorn, Friedhelm Meyer Auf Der Heide, Hans Rohnert, and Robert E. Tarjan (1994). Dynamic perfect hashing: Upper and lower bounds. SIAM Journal of Computing 23(4): 738-761.

    Google Scholar 

  19. Jochen Dörre (1994). Feature-logic with weak subsumption constraints. In M. A. Rosner, C. J. Rupp, and R. L. Johnson, editors, Constraints, Languages, and Computation, chapter 7, pages 187-203, Academic Press.

  20. Jochen Dörre (1996). Feature-Logik und Semiunifikation. Number 128 in DISKI-Dissertationen zur K¨unstlichen Intelligenz, Infix Verlag, Sankt Augustin. In German.

    Google Scholar 

  21. Jochen Dörre and William C. Rounds (1992). On subsumption and semi-unification in feature algebras. Journal of Symbolic Computation 13: 441-461.

    Google Scholar 

  22. R. Helm, K. Marriott, and M. Odersky (1991). Constraint-based query optimization for spatial databases. In 10 th Annual IEEE Symposium on the Principles of Database Sytems, pages 181-191.

  23. Mark Johnson (1988). Attribute-Value Logic and the Theory of Grammar. Number 16 in CSLI Lecture Notes. Center for the Study of Language and Information.

  24. Ronald M. Kaplan and Joan Bresnan (1982). Lexical-functional grammar: A formal system for grammatical representation. In J. Bresnan, editor, The Mental Representation of Grammatical Relations, pages 173-281, The MIT Press, Cambridge, MA.

    Google Scholar 

  25. Robert T. Kasper and William C. Rounds (1986). A logical semantics for feature structures. In Proceedings of the Annual Meeting of the Association of Computational Linguistics, pages 257-265.

  26. Martin Kay (1979). Functional grammar. In C. Chiarello et al., editor, Proceedings of the 5 th Annual Meeting of the Berkeley Linguistics Society, pages 142-158

  27. J. Lassez and K. McAloon (1988). Applications of a canonical form for generalized linear constraints. In Proceedings of the 5 th International Conference on Fifth Generation Computer Systems, pages 703-710.

  28. Kuniaki Mukai (1988). Partially specified terms in logic programming for linguistic analysis. In Proceedings of the 6th International Conference on Fifth Generation Computer Systems, Tokyo, Japan. ICOT.

    Google Scholar 

  29. Martin Müller (to appear). Ordering constraints over feature trees with ordered sorts. In P. Lopez, Suresh Manandhar, and Werner Nutt, editors, Computational Logic and Natural Language Understanding, Lecture Notes in Artificial Intelligence. Springer-Verlag, Berlin. Available at: http://www.ps.unisb. de/~mmueller/papers/clnlp.ps.z.

  30. Martin Müller and Joachim Niehren (1997). Entailment for set constraints is not feasible. Technical Report, Programming Systems Lab, Universität des Saarlandes, http://www.ps.unisb. de/Papers/abstracts/inesInfeas.html.

  31. Martin Müller and Joachim Niehren (1998). Ordering constraints over feature trees expressed in secondorder monadic logic. In Tobias Nipkow, editor, International Conference on Rewriting Techniques and Applications, volume 1379 of Lecture Notes in Computer Science, pages 196-210, Tsukuba, Japan, Springer-Verlag, Berlin.

    Google Scholar 

  32. Martin Müller, Joachim Niehren, and Andreas Podelski (1997). Inclusion constraints over non-empty sets of trees. In Michel Bidoit and Max Dauchet, editors, Proceedings of the Theory and Practice of Software Development, volume 1214 of Lecture Notes in Computer Science, pages 345-356, Lille, France, Springer-Verlag, Berlin.

    Google Scholar 

  33. Martin Müller, Joachim Niehren, and Ralf Treinen (1998). The first-order theory of ordering constraints over feature trees. In Proceedings of the 13 th IEEE Symposium on Logic in Computer Science, pages 432-443, IEEE Computer Society Press, 1998.

  34. Bernhard Nebel (1990). Reasoning and revision in hybrid representation. Volume 422 of Lecture Notes in Artificial Intelligence, Springer-Verlag, Berlin.

    Google Scholar 

  35. Bernhard Nebel and Gert Smolka (1990). Representation and reasoning with attributive descriptions. In K. H. Bläsius, U. Hedtstück, and C.-R. Rollinger, editors, Sorts and Types in Artificial Intelligence, volume 418 of Lecture Notes in Artificial Intelligence, pages 112-139, Springer-Verlag, Berlin.

    Google Scholar 

  36. Joachim Niehren, Martin Müller, and Jean-Marc Talbot (1999). Entailment of atomic set constraints is PSPACE-complete. In Fourteenth Annual IEEE Symposium on Logic in Computer Science (LICS99), pages 285-294, Trento, Italy, 2-5, July. IEEE Press.

    Google Scholar 

  37. Jens Palsberg (1994). Efficient inference of object types. In Proceedings of the 9 th IEEE Symposium on Logic in Computer Science, pages 186-185. IEEE Computer Society Press.

  38. Andreas Podelski and Gert Smolka (1995). Operational semantics of constraint logic programs with coroutining. In Leon Sterling, editor, Proceedings of the 12 th International Conference on Logic Programming, pages 449-463, Kanagawa, Japan. The MIT Press, Cambridge, MA.

    Google Scholar 

  39. Carl Pollard and Ivan Sag (1994). Head-Driven Phrase Structure Grammar. Studies in Contemporary Linguistics. Cambridge University Press, Cambridge, England.

    Google Scholar 

  40. Carl J. Pollard and Ivan A. Sag (1987). Information-Based Syntax and Semantics, Vol. 1. Number 13 in CSLI Lecture Notes. Center for the Study of Language and Information, Stanford University. Distributed by University of Chicago Press.

  41. Fran¸cois Pottier (1996). Simplifying subtyping constraints. In Proceedings of the ACM SIGPLAN International Conference on Functional Programming, pages 122-133. ACM Press, New York, May 1996.

    Google Scholar 

  42. William C. Rounds (1997). Feature logics. In Johan van Benthem and Alice ter Meulen, editors, Handbook of Logic and Language, pages 475-533. Elsevier Science Publishers B.V. (North Holland).

    Google Scholar 

  43. Steward Shieber (1986). An Introduction to Unification-based Approaches to Grammar. CSLI Lecture Notes No. 4, Center for the Study of Language and Information.

  44. Steward Shieber (1989). Parsing and Type Inference for Natural and Computer Languages. SRI International Technical Note 460, Stanford University.

  45. Steward Shieber, Hans Uszkoreit, Fernando Pereira, J. Alan Robinson, and M. Tyson (1983). The formalism and implementation of PATR-II. In Joan Bresnan, editor, Research on Interactive Acquisition and Use of Knowledge, SRI International, Menlo Park, California.

    Google Scholar 

  46. Gert Smolka (1992). Feature constraint logics for unification grammars. The Journal of Logic Programming 12(1-2): 51-87.

    Google Scholar 

  47. Gert Smolka (1995). The Oz programming model. In Jan van Leeuwen, editor, Computer Science Today, volume 1000 of Lecture Notes in Computer Science, pages 324-343, Springer-Verlag, Berlin.

    Google Scholar 

  48. Gert Smolka and Ralf Treinen (1994). Records for logic programming. The Journal of Logic Programming 18(3): 229-258.

    Google Scholar 

  49. Ralf Treinen (1993). Feature constraints with first-class features. In Andrzej M. Borzyszkowski and Stefan Sokolowski, editors, International Symposium on Mathematical Foundations of Computer Science, volume 711 of Lecture Notes in Computer Science, pages 734-743, Gda´nsk, Poland, Springer-Verlag.

    Google Scholar 

  50. Andreas Zeller and Gregor Snelting (1995). Handling version sets through feature logic. In W. Schäfer and P. Botella, editors, Proceedings of the 5th European Software Engineering Conference, volume 989 of Lecture Notes in Computer Science, pages 191-204, Sitges, Spain, Springer-Verlag, Berlin.

    Google Scholar 

  51. Andreas Zeller and Gregor Snelting (1997). Unified versioning through feature logic. ACM Transactions on Software Engineering and Methodology 6(4): 398-441.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Programming Systems Lab, Universität des Saarlandes, Stuhlsatzenhausweg 3, D-66041, Saarbrücken, Germany

    Martin Müller & Joachim Niehren

  2. Max-Planck-Institut für Informatik, Im Stadtwald, D-66123, Saarbrücken, Germany

    Andreas Podelski

Authors
  1. Martin Müller
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Joachim Niehren
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Andreas Podelski
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Müller, M., Niehren, J. & Podelski, A. Ordering Constraints over Feature Trees. Constraints 5, 7–41 (2000). https://doi.org/10.1023/A:1009866317252

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1009866317252

Search

Navigation