{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:28:01Z","timestamp":1725488881833},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422518"},{"type":"electronic","value":"9783540457381"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45738-0_7","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T11:40:39Z","timestamp":1186746039000},"page":"106-125","source":"Crossref","is-referenced-by-count":5,"title":["Dominance Constraints: Algorithms and Complexity"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Koller","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joachim","family":"Niehren","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ralf","family":"Treinen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,6,18]]},"reference":[{"key":"7_CR1","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/BF01048403","volume":"4","author":"R. Backofen","year":"1995","unstructured":"Backofen, R., J. Rogers, and K. Vijay-Shanker. A first-order axiomatization of the theory of finite trees. Journal of Logic, Language, and Information, 4:5\u201339, 1995.","journal-title":"Journal of Logic, Language, and Information"},{"key":"7_CR2","unstructured":"Bos, J. Predicate logic unplugged. In Proceedings of the 10th Amsterdam Colloquium, pages 133\u2013143, 1996."},{"key":"7_CR3","unstructured":"Duchier, D., and C. Gardent. A constraint-based treatment of descriptions. In Proceedings of IWCS-3, Tilburg, 1999."},{"key":"7_CR4","series-title":"Technical report","volume-title":"Solving dominance constraints with finite set constraint programming","author":"D. Duchier","year":"1999","unstructured":"Duchier, D., and J. Niehren. Solving dominance constraints with finite set constraint programming. Technical report, Universit\u00e4t des Saarlandes, Programming Systems Lab, 1999. http:\/\/www.ps.uni-sb.de\/Papers\/abstracts\/DomCP99.html ."},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"Egg, M., J. Niehren, P. Ruhrberg, and F. Xu. Constraints over Lambda-Structures in Semantic Underspecification. In Proceedings COLING\/ACL\u201998, Montreal, 1998.","DOI":"10.3115\/980845.980905"},{"key":"7_CR6","unstructured":"Gardent, C., and B. Webber. Describing discourse semantics. In Proceedings of the 4th TAG+ Workshop, Philadelphia, 1998. University of Pennsylvania."},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Johnson, D. S. A catalog of complexity classes. In Leeuwen, J. van, editor, Handbook of Theoretical Computer Science, vol A: Algorithms and Complexity, chapter 2, pages 67\u2013161. Elsevier, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50007-2"},{"key":"7_CR8","series-title":"Diplom thesis","volume-title":"Constraint languages for semantic underspecification","author":"A. Koller","year":"1999","unstructured":"Koller, A. Constraint languages for semantic underspecification. Diplom thesis, Universit\u00e4t des Saarlandes, Saarbr\u00fccken, Germany, 1999. http:\/\/www.coli.uni-sb.de\/~koller\/papers\/da.html ."},{"key":"7_CR9","unstructured":"Koller, A., and J. Niehren. Constraint programming in computational linguistics. Submitted. http:\/\/www.coli.uni-sb.de\/~koller\/cpcl.html , 1999."},{"key":"7_CR10","unstructured":"Koller, A., and J. Niehren. Scope underspecification and processing. Lecture Notes, ESSLLI\u2019 99, Utrecht, 1999. http:\/\/www.coli.uni-sb.de\/~koller\/papers\/esslli99.html"},{"key":"7_CR11","doi-asserted-by":"crossref","unstructured":"Marcus, M. P., D. Hindle, and M. M. Fleck. D-theory: Talking about talking about trees. In Proceedings of the 21st ACL, pages 129\u2013136, 1983.","DOI":"10.3115\/981311.981337"},{"key":"7_CR12","unstructured":"Meyer-Viol, W., and R. Kempson. Sequential construction of logical forms. In Proceedings of the Third Conference on Logical Aspects of Computational Linguistics, Grenoble, France, 1998."},{"key":"7_CR13","series-title":"Technical Report","volume-title":"Underspecified semantics","author":"R. Muskens","year":"1998","unstructured":"Muskens, R. Underspecified semantics. Technical Report 95, Universit\u00e4t des Saarlandes, Saarbr\u00fccken, 1998. To appear."},{"key":"7_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/1995086","volume":"141","author":"M. Rabin","year":"1969","unstructured":"Rabin, M. 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":"7_CR15","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1093\/jos\/10.2.123","volume":"10","author":"U. Reyle","year":"1993","unstructured":"Reyle, U. Dealing with ambiguities by underspecification: construction, representation, and deduction. Journal of Semantics, 10:123\u2013179, 1993.","journal-title":"Journal of Semantics"},{"key":"7_CR16","unstructured":"Rogers, J. Studies in the Logic of Trees with Applications to Grammar Formalisms. PhD thesis, University of Delaware, 1994."},{"key":"7_CR17","doi-asserted-by":"crossref","unstructured":"Rogers, J., and K. Vijay-Shanker. Reasoning with descriptions of trees. In Proceedings of the 30th ACL, pages 72\u201380, University of Delaware, 1992.","DOI":"10.3115\/981967.981977"},{"key":"7_CR18","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L. J., and A. R. Meyer. Word problems requiring exponential time. In 5th Annual ACM Symposium on the Theory of Computing, pages 1\u20139, 1973.","DOI":"10.1145\/800125.804029"},{"key":"7_CR19","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J. W. Thatcher","year":"1968","unstructured":"Thatcher, J. W., and J. B. Wright. Generalized finite automata with an application to a decision problem of second-order logic. Mathematical Systems Theory, 2:57\u201368, 1968.","journal-title":"Mathematical Systems Theory"},{"key":"7_CR20","first-page":"481","volume":"18","author":"K. Vijay-Shanker","year":"1992","unstructured":"Vijay-Shanker, K. Using descriptions of trees in a tree adjoining grammar. Computational Linguistics, 18:481\u2013518, 1992.","journal-title":"Computational Linguistics"}],"container-title":["Lecture Notes in Computer Science","Logical Aspects of Computational Linguistics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45738-0_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T18:21:07Z","timestamp":1556734867000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45738-0_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422518","9783540457381"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-45738-0_7","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}