{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,14]],"date-time":"2025-07-14T02:54:22Z","timestamp":1752461662761,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540643012"},{"type":"electronic","value":"9783540697213"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0052371","type":"book-chapter","created":{"date-parts":[[2006,6,7]],"date-time":"2006-06-07T05:31:11Z","timestamp":1149658271000},"page":"196-210","source":"Crossref","is-referenced-by-count":4,"title":["Ordering constraints over feature trees expressed in second-order monadic logic"],"prefix":"10.1007","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"}]}],"member":"297","published-online":{"date-parts":[[2006,5,18]]},"reference":[{"issue":"3","key":"16_CR1","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0743-1066(93)90043-G","volume":"16","author":"H. A\u00cft-Kaci","year":"1993","unstructured":"H. A\u00cft-Kaci and A. Podelski. Towards a Meaning of Life. The Journal of Logic Programming, 16(3 and 4): 195\u2013234, July, Aug. 1993.","journal-title":"The Journal of Logic Programming"},{"issue":"1\u20132","key":"16_CR2","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0304-3975(94)90209-7","volume":"122","author":"H. A\u00cft-Kaci","year":"1994","unstructured":"H. A\u00cft-Kaci, A. Podelski, and G. Smolka. A Feature-based Constraint System for Logic Programming with Entailment. Theoretical Computer Science, 122(1\u20132):263\u2013283, 1994.","journal-title":"Theoretical Computer Science"},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"R. Backofen. A Complete Axiomatization of a Theory with Feature and Arity Constraints. The Journal of Logic Programming, 1995. Special Issue on Computational Linguistics and Logic Programming.","DOI":"10.1016\/0743-1066(95)00033-G"},{"issue":"1\u20132","key":"16_CR4","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0304-3975(94)00188-O","volume":"146","author":"R. Backofen","year":"1995","unstructured":"R. Backofen and G. Smolka. A Complete and Recursive Feature Theory. Theoretical Computer Science, 146(1\u20132):243\u2013268, July 1995.","journal-title":"Theoretical Computer Science"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"H. Comon. Sequentially, second-order monadic logic and tree automata. In K. Dexter, editor, Proceedings of the Logic in Computer Science Conference, pages 508\u2013517, 1995.","DOI":"10.1109\/LICS.1995.523285"},{"key":"16_CR6","first-page":"151","volume-title":"Annual ACM Symposium on Theory of Computing","author":"S. A. Cook","year":"1971","unstructured":"S. A. Cook. The Complexity of Theorem-Proving Procedures. In Annual ACM Symposium on Theory of Computing, pages 151\u2013158, New York, 1971. ACM."},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"J. D\u00f6rre. Feature logics with weak subsumption constraints. In Annual Meeting of the ACL (Association of Computational Logics), pages 256\u2013263, 1991.","DOI":"10.3115\/981344.981377"},{"key":"16_CR8","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979."},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"F. Henglein and J. Rehof. The Complexity of Subtype Entailment for Simple Types. In 12th IEEE Symposium on Logic in Computer Science, Warsaw, Poland, 1997.","DOI":"10.1109\/LICS.1997.614961"},{"key":"16_CR10","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"J. D. Hopcroft","year":"1979","unstructured":"J. D. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA, 1979."},{"key":"16_CR11","first-page":"173","volume-title":"Lexical-Functional Grammar: A Formal System for Grammatical Representation","author":"R. M. Kaplan","year":"1982","unstructured":"R. M. Kaplan and J. Bresnan. Lexical-Functional Grammar: A Formal System for Grammatical Representation, pages 173\u2013381. The MIT Press, Cambridge, MA, 1982."},{"key":"16_CR12","doi-asserted-by":"crossref","unstructured":"M. Kay. Functional Grammar. In C. Chiarello et al., editor, Proc. of the 5th Annual Meeting of the Berkeley Linguistics Society, pages 142\u2013158, 1979.","DOI":"10.3765\/bls.v5i0.3262"},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"M. M\u00fcller. Ordering Constraints over Feature Trees with Ordered Sorts. In P. Lopez, S. Manandhar, and W. Nutt, editors, Computational Logic and Natural Language Understanding, Lecture Notes in Artificial Intelligence, to appear, 1997.","DOI":"10.1007\/BFb0017447"},{"key":"16_CR14","unstructured":"M. M\u00fcller and J. Niehren. Entailment for Set Constraints is not Feasible. Technical report, Programming Systems Lab, Universit\u00e4t des Saarlandes, 1997. http: \/\/www.ps. uni-sb.de\/Papers\/abstracts\/inesInfeas.html"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"M. M\u00fcller and J. Niehren. Ordering Constraints over Feature Trees Expressed in Secondorder Monadic Logic. Full version available at http:\/\/vnw.ps.uni-sb.de\/ Papers\/abstracts\/SWS97.html 1997.","DOI":"10.1007\/BFb0052371"},{"key":"16_CR16","unstructured":"M. M\u00fcller, J. Niehren, and R. Treinen. The First-order Theory of Ordering Constraints over Feature Trees. Submitted. http:\/\/www.ps.uni-sb.de\/Papers\/abstracts\/ FTSubTheory-98.html. 1997."},{"key":"16_CR17","volume-title":"Studies in Contemporary Linguistics","author":"M. M\u00fcller","year":"1994","unstructured":"M. M\u00fcller, J. Niehren, and A. Podelski. Ordering Constraints over Feature Trees. In 3rd Int. Conf. on Principles and Practice of Constraint Programming, vol 1330 of LNCS, 1997. 18. C. Pollard and I. Sag. Head-Driven Phrase Structure Grammar. Studies in Contemporary Linguistics. Cambridge University Press, Cambridge, England, 1994."},{"key":"16_CR18","first-page":"1","volume":"141","author":"M. O. Rabin","year":"1969","unstructured":"M. O. Rabin. Decidability of second-order theories and automata on infinite trees. Transactions of the American Mathematical Society, 141:1\u201335, 1969.","journal-title":"Transactions of the American Mathematical Society"},{"key":"16_CR19","volume-title":"Handbook of Logic and Language","author":"W. C. Rounds","year":"1997","unstructured":"W. C. Rounds. Feature Logics. In J. v. Benthem and A. ter Meulen, editors, Handbook of Logic and Language. Elsevier Science Publishers B.V. (North Holland), 1997."},{"issue":"3","key":"16_CR20","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1137\/0219027","volume":"19","author":"H. Seidl","year":"1990","unstructured":"H. Seidl. Deciding Equivalence of Finite Tree Automata. SIAM Journal of Computing, 19(3):424\u2013437, June 1990.","journal-title":"SIAM Journal of Computing"},{"key":"16_CR21","unstructured":"S. Shieber. An Introduction to Unification-based Approaches to Grammar. CSLI Lecture Notes No. 4. Center for the Study of Language and Information, 1986."},{"key":"16_CR22","first-page":"324","volume-title":"Computer Science Today, LNCS, vol. 1000","author":"G. Smolka","year":"1995","unstructured":"G. Smolka. The Oz Programming Model. In J. van Leeuwen, editor, Computer Science Today, LNCS, vol. 1000, pages 324\u2013343. Springer-Verlag, Berlin, Germany, 1995."},{"issue":"3","key":"16_CR23","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1016\/0743-1066(94)90044-2","volume":"18","author":"G. Smolka","year":"1994","unstructured":"G. Smolka and R. Treinen. Records for Logic Programming. The Journal of Logic Programming, 18(3):229\u2013258, Apr. 1994.","journal-title":"The Journal of Logic Programming"},{"issue":"1","key":"16_CR24","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J. W. Thatcher","year":"1967","unstructured":"J. W. Thatcher and J. B. Wright. Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical Systems Theory, 2(1):57\u201381, 1967.","journal-title":"Mathematical Systems Theory"},{"key":"16_CR25","doi-asserted-by":"crossref","unstructured":"S. Vorobyov. An improved lower bound for the elementary theories of trees. In Internat. Conf. on Automated Deduction, vol. 1104 of LNCS, 275\u2013287, 1996.","DOI":"10.1007\/3-540-61511-3_91"}],"container-title":["Lecture Notes in Computer Science","Rewriting Techniques and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0052371","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T07:11:07Z","timestamp":1736406667000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0052371"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540643012","9783540697213"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/bfb0052371","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}