{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T13:32:37Z","timestamp":1726407157522},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540402541"},{"type":"electronic","value":"9783540448815"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-44881-0_17","type":"book-chapter","created":{"date-parts":[[2007,3,5]],"date-time":"2007-03-05T11:39:56Z","timestamp":1173094796000},"page":"234-245","source":"Crossref","is-referenced-by-count":4,"title":["On the Complexity of Higher-Order Matching in the Linear \u03bb-Calculus"],"prefix":"10.1007","author":[{"given":"Sylvain","family":"Salvati","sequence":"first","affiliation":[]},{"given":"Philippe","family":"de Groote","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2003,6,18]]},"reference":[{"issue":"4","key":"17_CR1","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1006\/jsco.1997.0185","volume":"25","author":"H. Comon","year":"1998","unstructured":"H. Comon. Completion of rewrite systems with membership constraints. Part I: Deduction rules. Journal of Symbolic Computation, 25(4):397\u2013419, 1998.","journal-title":"Journal of Symbolic Computation"},{"issue":"4","key":"17_CR2","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1006\/jsco.1997.0186","volume":"25","author":"H. Comon","year":"1998","unstructured":"H. Comon. Completion of rewrite systems with membership constraints. Part II: Constraint solving. Journal of Symbolic Computation, 25(4):421\u2013453, 1998.","journal-title":"Journal of Symbolic Computation"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"S. A. Cook. The complexity of theorem proving procedures. Proceedings of the 3rd annual ACM Symposium on Theory of Computing, pages 151\u2013158, 1971.","DOI":"10.1145\/800157.805047"},{"key":"17_CR4","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/3-540-45610-4_24","volume":"2378","author":"D. Dougherty","year":"2002","unstructured":"D. Dougherty and T. Wierzbicki. A decidable variant of higher order matching. In Proc. 13th Conf. on Rewriting Techniques and Applications, RTA\u201902, volume 2378, pages 340\u2013351, 2002.","journal-title":"Proc. 13th Conf. on Rewriting Techniques and Applications, RTA\u201902"},{"issue":"2\u20133","key":"17_CR5","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0168-0072(94)90083-3","volume":"69","author":"G. Dowek","year":"1994","unstructured":"G. Dowek. Third order matching is decidable. Annals of Pure and Applied Logic, 69(2\u20133):135\u2013155, 1994.","journal-title":"Annals of Pure and Applied Logic"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"G. Dowek. Higher-order unification and matching. In A. Robinson and A. Voronkov (eds.), Handbook of Automated Reasoning, pp. 1009\u20131062, Elsevier, 2001.","DOI":"10.1016\/B978-044450813-3\/50018-7"},{"issue":"2","key":"17_CR7","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0304-3975(81)90040-2","volume":"13","author":"W. D. Goldfarb","year":"1981","unstructured":"W. D. Goldfarb. The undecidability of the second-order unification problem. Theoretical Computer Science, 13(2):225\u2013230, 1981.","journal-title":"Theoretical Computer Science"},{"key":"17_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/10721975_9","volume-title":"Higher-order linear matching is np-complete","author":"Ph. Groote de","year":"2000","unstructured":"Ph. de Groote. Higher-order linear matching is np-complete. Lecture Notes in Computer Science, 1833:127\u2013140, 2000."},{"issue":"3","key":"17_CR9","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/S0019-9958(73)90301-X","volume":"22","author":"G. Huet","year":"1973","unstructured":"G. Huet. The undecidability of unification in third order logic. Information and Control, 22(3):257\u2013267, 1973.","journal-title":"Information and Control"},{"key":"17_CR10","unstructured":"G. Huet. R\u00e9solution d\u2019\u00e9quations dans les langages d\u2019ordre 1, 2,..., \u03c9. Th\u00e8se de Doctorat d\u2019Etat, Universit\u00e9 Paris 7, 1976."},{"key":"17_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1007\/3-540-61464-8_63","volume-title":"Rewriting Techniques and Applications, RTA\u201996","author":"J. Levy","year":"1996","unstructured":"J. Levy. Linear second-order unification. In H. Ganzinger, editor, Rewriting Techniques and Applications, RTA\u201996, volume 1103 of Lecture Notes in Computer Science, pages 332\u2013346. Springer-Verlag, 1996."},{"issue":"1","key":"17_CR12","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1093\/jigpal\/11.1.51","volume":"11","author":"R. Loader","year":"2002","unstructured":"R. Loader. Higher order \u03b2 matching is undecidable. Logic Journal of the IGPL, 11(1): 51\u201368, 2002.","journal-title":"Logic Journal of the IGPL"},{"key":"17_CR13","unstructured":"V. Padovani. Filtrage d\u2019ordre sup\u00e9rieure. Th\u00e8se de Doctorat, Universit\u00e9 de Paris 7, 1996."},{"issue":"2","key":"17_CR14","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1137\/S0097539791218202","volume":"24","author":"P. Kilpel\u00e4inen","year":"1995","unstructured":"P. Kilpel\u00e4inen. Ordered and unordered tree inclusion. SIAM. J. Comput., 24(2): 340\u2013356, 1995.","journal-title":"SIAM. J. Comput."},{"key":"17_CR15","unstructured":"M. Schmidt-Schau\u00df and J. Stuber. On the complexity of linear and stratified context matching problems. Rapport de recherche A01-R-411, LORIA, December 2001."}],"container-title":["Lecture Notes in Computer Science","Rewriting Techniques and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44881-0_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,15]],"date-time":"2019-02-15T23:12:33Z","timestamp":1550272353000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44881-0_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540402541","9783540448815"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-44881-0_17","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}