{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,13]],"date-time":"2025-07-13T04:10:06Z","timestamp":1752379806101,"version":"3.41.2"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2000,1,1]],"date-time":"2000-01-01T00:00:00Z","timestamp":946684800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2000,1]]},"DOI":"10.1023\/a:1009866317252","type":"journal-article","created":{"date-parts":[[2002,12,22]],"date-time":"2002-12-22T18:53:29Z","timestamp":1040583209000},"page":"7-41","source":"Crossref","is-referenced-by-count":5,"title":["Ordering Constraints over Feature Trees"],"prefix":"10.1007","volume":"5","author":[{"given":"Martin","family":"M\u00fcller","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joachim","family":"Niehren","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Podelski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"243793_CR1","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0304-3975(86)90047-2","volume":"45","author":"A. Hassan","year":"1986","unstructured":"Hassan A\u00eft-Kaci (1986). An algebraic semantics approach to the effective resolution of type equations. Theoretical Computer Science 45: 293-351.","journal-title":"Theoretical Computer Science"},{"key":"243793_CR2","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF01806313","volume":"2","author":"A. Hassan","year":"1989","unstructured":"Hassan A\u00eft-Kaci and R. Nasr (1989). LOGIN: A logic programming language with built-in inheritance. Journal on Lisp and Symbolic Computation 2:51-89.","journal-title":"Journal on Lisp and Symbolic Computation"},{"issue":"3","key":"243793_CR3","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0743-1066(86)90013-0","volume":"3","author":"H. A\u00eft-Kaci","year":"1986","unstructured":"Hassan A\u00eft-Kaci and R. Nasr (1986). LOGIN: A logic programming language with built-in inheritance. The Journal of Logic Programming 3(3):185-215.","journal-title":"The Journal of Logic Programming"},{"key":"243793_CR4","series-title":"Lecture Notes in Artificial Intelligence","first-page":"1","volume-title":"Proceedings of the 4 th International Conference on Logic Programming and Automated Reasoning","author":"H. A\u00eft-Kaci","year":"1993","unstructured":"Hassan A\u00eft-Kaci and Andreas Podelski (1993). Entailment and disentailment of order-sorted feature constraints. In Andrei Voronkov, editor, Proceedings of the 4\nth\nInternational Conference on Logic Programming and Automated Reasoning, volume 698 of Lecture Notes in Artificial Intelligence, pages 1-18, Springer-Verlag, Berlin."},{"issue":"3-4","key":"243793_CR5","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0743-1066(93)90043-G","volume":"16","author":"H. A\u00eft-Kaci","year":"1993","unstructured":"Hassan A\u00eft-Kaci and Andreas Podelski (1993). Towards a meaning of life. The Journal of Logic Programming 16(3-4): 195-234.","journal-title":"The Journal of Logic Programming"},{"issue":"1-2","key":"243793_CR6","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0304-3975(94)90209-7","volume":"122","author":"A. Hassan","year":"1994","unstructured":"Hassan A\u00eft-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.","journal-title":"Theoretical Computer Science"},{"key":"243793_CR7","volume-title":"Expressivity and Decidability of First-order Languages over Feature Trees","author":"B. Rolf","year":"1994","unstructured":"Rolf Backofen (1994). Expressivity and Decidability of First-order Languages over Feature Trees. Doctoral Dissertation, Universit\u00e4t des Saarlandes, Technische Fakult\u00e4t, D-66041 Saarbr\u00a8ucken."},{"key":"243793_CR8","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1006\/jsco.1994.1028","volume":"17","author":"R. Backofen","year":"1994","unstructured":"Rolf Backofen (1994). Regular path expressions in feature logic. Journal of Symbolic Computation 17: 421-455.","journal-title":"Journal of Symbolic Computation"},{"issue":"1-2","key":"243793_CR9","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0743-1066(95)00033-G","volume":"24","author":"R. Backofen","year":"1995","unstructured":"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.","journal-title":"The Journal of Logic Programming"},{"key":"243793_CR10","unstructured":"Rolf Backofen (1996). Controlling functional uncertainty. In Wolfgang Wahlster, editor, Proceedings of 12\nth\nEuropean Conference on Artificial Intelligence, John Wiley & Sons, Ltd, pages 557-561."},{"issue":"1-2","key":"243793_CR11","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0304-3975(94)00188-O","volume":"146","author":"R. Backofen","year":"1995","unstructured":"Rolf Backofen and Gert Smolka (1995). A complete and recursive feature theory. Theoretical Computer Science 146(1-2): 243-268.","journal-title":"Theoretical Computer Science"},{"key":"243793_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"320","DOI":"10.1007\/BFb0016863","volume-title":"1st International Conference on Constraints in Computational Logics","author":"R. Backofen","year":"1994","unstructured":"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\u00fcnchen, Germany, Springer-Verlag."},{"key":"243793_CR13","unstructured":"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."},{"key":"243793_CR14","series-title":"Cambridge Tracts in Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511530098","volume-title":"The logic of typed feature structures-with applications to unification grammars, logic programs and constraint resolution","author":"B. Carpenter","year":"1992","unstructured":"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."},{"key":"243793_CR15","doi-asserted-by":"crossref","unstructured":"Witold Charatonik and Andreas Podelski (1996). The independence property of a class of set constraints. In Eugene C. Freuder, editor, Proceedings of the 2\nnd\nInternational Conference on Principles and Practice of Constraint Programming, volume 1118 of Lecture Notes in Computer Science, pages 76-90.","DOI":"10.1007\/3-540-61551-2_67"},{"key":"243793_CR16","unstructured":"Witold Charatonik and Andreas Podelski. Set constraints with intersection. In Proceedings of the 12\nth\nIEEE Symposium on Logic in Computer Science, Warsaw, Poland, pages 352-361. IEEE Computer Society Press."},{"key":"243793_CR17","first-page":"85","volume-title":"Proceedings of the 2 nd International Conference on Fifth Generation Computer Systems","author":"A. Colmerauer","year":"1984","unstructured":"Alain Colmerauer (1984). Equations and inequations on finite and infinite trees. In ICOT, editor, Proceedings of the 2\nnd\nInternational Conference on Fifth Generation Computer Systems, pages 85-99. Omsha Ltd., Tokyo and North-Holland, Amsterdam."},{"issue":"4","key":"243793_CR18","doi-asserted-by":"crossref","first-page":"738","DOI":"10.1137\/S0097539791194094","volume":"23","author":"M. Dietzfelbinger","year":"1994","unstructured":"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.","journal-title":"SIAM Journal of Computing"},{"key":"243793_CR19","doi-asserted-by":"crossref","unstructured":"Jochen D\u00f6rre (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.","DOI":"10.1016\/B978-0-08-050296-0.50014-0"},{"key":"243793_CR20","series-title":"DISKI-Dissertationen zur K\u00a8unstlichen Intelligenz","volume-title":"Feature-Logik und Semiunifikation","author":"J. D\u00f6rre","year":"1996","unstructured":"Jochen D\u00f6rre (1996). Feature-Logik und Semiunifikation. Number 128 in DISKI-Dissertationen zur K\u00a8unstlichen Intelligenz, Infix Verlag, Sankt Augustin. In German."},{"key":"243793_CR21","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1016\/S0747-7171(08)80107-1","volume":"13","author":"J. D\u00f6rre","year":"1992","unstructured":"Jochen D\u00f6rre and William C. Rounds (1992). On subsumption and semi-unification in feature algebras. Journal of Symbolic Computation 13: 441-461.","journal-title":"Journal of Symbolic Computation"},{"key":"243793_CR22","doi-asserted-by":"crossref","unstructured":"R. Helm, K. Marriott, and M. Odersky (1991). Constraint-based query optimization for spatial databases. In 10\nth\nAnnual IEEE Symposium on the Principles of Database Sytems, pages 181-191.","DOI":"10.1145\/113413.113429"},{"key":"243793_CR23","unstructured":"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."},{"key":"243793_CR24","first-page":"173","volume-title":"The Mental Representation of Grammatical Relations","author":"R. M. Kaplan","year":"1982","unstructured":"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."},{"key":"243793_CR25","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.3115\/981131.981166"},{"key":"243793_CR26","doi-asserted-by":"crossref","unstructured":"Martin Kay (1979). Functional grammar. In C. Chiarello et al., editor, Proceedings of the 5\nth\nAnnual Meeting of the Berkeley Linguistics Society, pages 142-158","DOI":"10.3765\/bls.v5i0.3262"},{"key":"243793_CR27","unstructured":"J. Lassez and K. McAloon (1988). Applications of a canonical form for generalized linear constraints. In Proceedings of the 5\nth\nInternational Conference on Fifth Generation Computer Systems, pages 703-710."},{"key":"243793_CR28","volume-title":"Proceedings of the 6th International Conference on Fifth Generation Computer Systems","author":"K. Mukai","year":"1988","unstructured":"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."},{"key":"243793_CR29","unstructured":"Martin M\u00fcller (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."},{"key":"243793_CR30","unstructured":"Martin M\u00fcller and Joachim Niehren (1997). Entailment for set constraints is not feasible. Technical Report, Programming Systems Lab, Universit\u00e4t des Saarlandes, http:\/\/www.ps.unisb. de\/Papers\/abstracts\/inesInfeas.html."},{"key":"243793_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1007\/BFb0052371","volume-title":"International Conference on Rewriting Techniques and Applications","author":"M. M\u00fcller","year":"1998","unstructured":"Martin M\u00fcller 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."},{"key":"243793_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1007\/BFb0030609","volume-title":"Proceedings of the Theory and Practice of Software Development","author":"M. M\u00fcller","year":"1997","unstructured":"Martin M\u00fcller, 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."},{"key":"243793_CR33","unstructured":"Martin M\u00fcller, Joachim Niehren, and Ralf Treinen (1998). The first-order theory of ordering constraints over feature trees. In Proceedings of the 13\nth\nIEEE Symposium on Logic in Computer Science, pages 432-443, IEEE Computer Society Press, 1998."},{"key":"243793_CR34","series-title":"Lecture Notes in Artificial Intelligence","volume-title":"Reasoning and revision in hybrid representation","author":"B. Nebel","year":"1990","unstructured":"Bernhard Nebel (1990). Reasoning and revision in hybrid representation. Volume 422 of Lecture Notes in Artificial Intelligence, Springer-Verlag, Berlin."},{"key":"243793_CR35","first-page":"112","volume-title":"Sorts and Types in Artificial Intelligence, volume 418 of Lecture Notes in Artificial Intelligence","author":"B. Nebel","year":"1990","unstructured":"Bernhard Nebel and Gert Smolka (1990). Representation and reasoning with attributive descriptions. In K. H. Bl\u00e4sius, U. Hedtst\u00fcck, 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."},{"key":"243793_CR36","first-page":"285","volume-title":"Fourteenth Annual IEEE Symposium on Logic in Computer Science (LICS99)","author":"J. Niehren","year":"1999","unstructured":"Joachim Niehren, Martin M\u00fcller, 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."},{"key":"243793_CR37","doi-asserted-by":"crossref","unstructured":"Jens Palsberg (1994). Efficient inference of object types. In Proceedings of the 9\nth\nIEEE Symposium on Logic in Computer Science, pages 186-185. IEEE Computer Society Press.","DOI":"10.1109\/LICS.1994.316073"},{"key":"243793_CR38","first-page":"449","volume-title":"Proceedings of the 12 th International Conference on Logic Programming","author":"A. Podelski","year":"1995","unstructured":"Andreas Podelski and Gert Smolka (1995). Operational semantics of constraint logic programs with coroutining. In Leon Sterling, editor, Proceedings of the 12\nth\nInternational Conference on Logic Programming, pages 449-463, Kanagawa, Japan. The MIT Press, Cambridge, MA."},{"key":"243793_CR39","series-title":"Studies in Contemporary Linguistics","volume-title":"Head-Driven Phrase Structure Grammar","author":"C. Pollard","year":"1994","unstructured":"Carl Pollard and Ivan Sag (1994). Head-Driven Phrase Structure Grammar. Studies in Contemporary Linguistics. Cambridge University Press, Cambridge, England."},{"key":"243793_CR40","unstructured":"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."},{"key":"243793_CR41","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1145\/232627.232642","volume-title":"Proceedings of the ACM SIGPLAN International Conference on Functional Programming","author":"F. Pottier","year":"1996","unstructured":"Fran\u00b8cois 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."},{"key":"243793_CR42","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1016\/B978-044481714-3\/50012-6","volume-title":"Handbook of Logic and Language","author":"W. C. Rounds","year":"1997","unstructured":"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)."},{"key":"243793_CR43","unstructured":"Steward Shieber (1986). An Introduction to Unification-based Approaches to Grammar. CSLI Lecture Notes No. 4, Center for the Study of Language and Information."},{"key":"243793_CR44","unstructured":"Steward Shieber (1989). Parsing and Type Inference for Natural and Computer Languages. SRI International Technical Note 460, Stanford University."},{"key":"243793_CR45","volume-title":"Research on Interactive Acquisition and Use of Knowledge","author":"S. Shieber","year":"1983","unstructured":"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."},{"issue":"1-2","key":"243793_CR46","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0743-1066(92)90039-6","volume":"12","author":"G. Smolka","year":"1992","unstructured":"Gert Smolka (1992). Feature constraint logics for unification grammars. The Journal of Logic Programming 12(1-2): 51-87.","journal-title":"The Journal of Logic Programming"},{"key":"243793_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1007\/BFb0015252","volume-title":"Computer Science Today","author":"G. Smolka","year":"1995","unstructured":"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."},{"issue":"3","key":"243793_CR48","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0743-1066(94)90044-2","volume":"18","author":"G. Smolka","year":"1994","unstructured":"Gert Smolka and Ralf Treinen (1994). Records for logic programming. The Journal of Logic Programming 18(3): 229-258.","journal-title":"The Journal of Logic Programming"},{"key":"243793_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"734","DOI":"10.1007\/3-540-57182-5_64","volume-title":"International Symposium on Mathematical Foundations of Computer Science","author":"R. Treinen","year":"1993","unstructured":"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\u00b4nsk, Poland, Springer-Verlag."},{"key":"243793_CR50","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/3-540-60406-5_15","volume-title":"Proceedings of the 5th European Software Engineering Conference","author":"A. Zeller","year":"1995","unstructured":"Andreas Zeller and Gregor Snelting (1995). Handling version sets through feature logic. In W. Sch\u00e4fer 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."},{"issue":"4","key":"243793_CR51","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1145\/261640.261654","volume":"6","author":"A. Zeller","year":"1997","unstructured":"Andreas Zeller and Gregor Snelting (1997). Unified versioning through feature logic. ACM Transactions on Software Engineering and Methodology 6(4): 398-441.","journal-title":"ACM Transactions on Software Engineering and Methodology"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009866317252.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1009866317252\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1009866317252.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,13]],"date-time":"2025-07-13T03:46:00Z","timestamp":1752378360000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1009866317252"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,1]]},"references-count":51,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2000,1]]}},"alternative-id":["243793"],"URL":"https:\/\/doi.org\/10.1023\/a:1009866317252","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"type":"print","value":"1383-7133"},{"type":"electronic","value":"1572-9354"}],"subject":[],"published":{"date-parts":[[2000,1]]}}}