{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T03:14:55Z","timestamp":1762917295908},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540255963"},{"type":"electronic","value":"9783540320333"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-32033-3_18","type":"book-chapter","created":{"date-parts":[[2010,9,27]],"date-time":"2010-09-27T20:20:02Z","timestamp":1285618802000},"page":"235-249","source":"Crossref","is-referenced-by-count":11,"title":["Higher-Order Matching in the Linear Lambda Calculus in the Absence of Constants Is NP-Complete"],"prefix":"10.1007","author":[{"given":"Ryo","family":"Yoshinaka","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/10721975_9","volume-title":"Rewriting Techniques and Applications","author":"P. Groote de","year":"2000","unstructured":"de Groote, P.: Linear higher-order matching is NP-complete. In: Bachmair, L. (ed.) RTA 2000. LNCS, vol.\u00a01833, pp. 127\u2013140. Springer, Heidelberg (2000)"},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"de Groote, P.: Towards abstract categorial grammars. In: Association for Computational Linguistics, 39th Annual Meeting and 10th Conference of the European Chapter, Proceedings of the Conference, pp. 148\u2013155 (2001)","DOI":"10.3115\/1073012.1073045"},{"key":"18_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/3-540-45610-4_24","volume-title":"Rewriting Techniques and Applications","author":"D. Dougherty","year":"2002","unstructured":"Dougherty, D., Wierzbicki, T.: A decidable variant of higher order matching. In: Tison, S. (ed.) RTA 2002. LNCS, vol.\u00a02378, pp. 340\u2013351. Springer, Heidelberg (2002)"},{"key":"18_CR4","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0168-0072(94)90083-3","volume":"69","author":"G. Dowek","year":"1994","unstructured":"Dowek, G.: Third order matching is decidable. Annals of Pure and Applied Logic\u00a069, 135\u2013155 (1994)","journal-title":"Annals of Pure and Applied Logic"},{"key":"18_CR5","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0304-3975(81)90040-2","volume":"13","author":"W.D. Goldfarb","year":"1981","unstructured":"Goldfarb, W.D.: The undecidability of the second-order unification problem. Theoretical Computer Science\u00a013, 225\u2013230 (1981)","journal-title":"Theoretical Computer Science"},{"key":"18_CR6","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/BF00264598","volume":"11","author":"G. Huet","year":"1978","unstructured":"Huet, G., Lang, B.: Proving and applying program transformations expressed with second order patterns. Acta Informatica\u00a011, 31\u201355 (1978)","journal-title":"Acta Informatica"},{"issue":"2","key":"18_CR7","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1137\/S0097539791218202","volume":"24","author":"P. Kilpel\u00e4inen","year":"1995","unstructured":"Kilpel\u00e4inen, P., Mannila, H.: Ordered and unordered tree inclusion. SIAM Journal of Computing\u00a024(2), 340\u2013356 (1995)","journal-title":"SIAM Journal of Computing"},{"key":"18_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1007\/3-540-61464-8_63","volume-title":"Rewriting Techniques and Applications","author":"J. Levy","year":"1996","unstructured":"Levy, J.: Linear second-order unification. In: Ganzinger, H. (ed.) RTA 1996. LNCS, vol.\u00a01103, pp. 332\u2013346. Springer, Heidelberg (1996)"},{"issue":"1","key":"18_CR9","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1093\/jigpal\/11.1.51","volume":"11","author":"R. Loader","year":"2003","unstructured":"Loader, R.: Higher order \u03b2 matching is undecidable. Logic Journal of the IGPL\u00a011(1), 51\u201368 (2003)","journal-title":"Logic Journal of the IGPL"},{"issue":"3","key":"18_CR10","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1017\/S0960129500003108","volume":"10","author":"V. Padovani","year":"2000","unstructured":"Padovani, V.: Decidability of fourth-order matching. Mathematical Structures in Computer Science\u00a010(3), 361\u2013372 (2000)","journal-title":"Mathematical Structures in Computer Science"},{"key":"18_CR11","unstructured":"Pogodalla, S.: Using and extending ACG technology: Endowing categorial grammars with an underspecified semantic representation. In: Proceedings of Categorial Grammars 2004, Montpellier, June 2004, pp. 197\u2013209 (2004)"},{"key":"18_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/3-540-44881-0_17","volume-title":"Rewriting Techniques and Applications","author":"S. Salvati","year":"2003","unstructured":"Salvati, S., de Groote, P.: On the complexity of higher-order matching in the linear \u03bb-calculus. In: Nieuwenhuis, R. (ed.) RTA 2003. LNCS, vol.\u00a02706, pp. 234\u2013245. Springer, Heidelberg (2003)"}],"container-title":["Lecture Notes in Computer Science","Term Rewriting and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-32033-3_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,2]],"date-time":"2021-05-02T23:45:33Z","timestamp":1619999133000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-32033-3_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540255963","9783540320333"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-32033-3_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}