{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T18:54:56Z","timestamp":1794336896080,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540637530","type":"print"},{"value":"9783540696421","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/bfb0017446","type":"book-chapter","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T02:22:46Z","timestamp":1132626166000},"page":"282-296","source":"Crossref","is-referenced-by-count":0,"title":["On the complexity of unification and disunification in commutative idempotent semigroups"],"prefix":"10.1007","author":[{"given":"Miki","family":"Hermann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Phokion G.","family":"Kolaitis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,10]]},"reference":[{"issue":"1","key":"22_CR1","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1016\/0743-1066(95)00146-8","volume":"27","author":"N. Arni","year":"1996","unstructured":"N. Arni, S. Greco, and D. Sacc\u00e1. Matching of bounded set terms in the logic language LDL++. J. Logic Prog., 27(1):73\u201387, 1996.","journal-title":"J. Logic Prog."},{"issue":"3","key":"22_CR2","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/0304-3975(88)90140-5","volume":"56","author":"F. Baader","year":"1988","unstructured":"F. Baader and W. B\u00fcttner. Unification in commutative idempotent monoids. Theoretical Comp. Sci., 56(3):345\u2013353, 1988.","journal-title":"Theoretical Comp. Sci."},{"key":"22_CR3","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/S0747-7171(87)80027-5","volume":"3","author":"D. Benanav","year":"1987","unstructured":"D. Benanav, D. Kapur, and P. Narendran. Complexity of matching problems. J. Symb. Comp., 3:203\u2013216, 1987.","journal-title":"J. Symb. Comp."},{"issue":"3","key":"22_CR4","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0022-0000(74)80046-2","volume":"9","author":"S.A. Cook","year":"1974","unstructured":"S.A. Cook. An observation on time-storage trade off. J. of Comp. and System Sci., 9(3):308\u2013316, 1974.","journal-title":"J. of Comp. and System Sci."},{"issue":"3","key":"22_CR5","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1016\/0743-1066(84)90014-1","volume":"1","author":"W.F. Dowling","year":"1984","unstructured":"W.F. Dowling and J.H. Gallier. Linear-time algorithms for testing the satis fiability of propositional Horn formulae. J. Logic Prog., 1(3):267\u2013284, 1984.","journal-title":"J. Logic Prog."},{"key":"22_CR6","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0743-1066(84)90022-0","volume":"1","author":"C. Dwork","year":"1984","unstructured":"C. Dwork, P.C. Kanellakis, and J.C. Mitchell. On the sequential nature of unification. J. Logic Prog., 1:35\u201350, 1984.","journal-title":"J. Logic Prog."},{"key":"22_CR7","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to parallel computation: P-completeness theory","author":"R. Greenlaw","year":"1995","unstructured":"R. Greenlaw, H.J. Hoover, and W.L. Ruzzo. Limits to parallel computation: P-completeness theory. Oxford University Press, New York, 1995."},{"key":"22_CR8","unstructured":"M.R. Garey and D.S. Johnson. Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman and Co, 1979."},{"issue":"3","key":"22_CR9","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1006\/jsco.1995.1054","volume":"20","author":"M. Hermann","year":"1995","unstructured":"M. Hermann and P.G. Kolaitis. The complexity of counting problems in equational matching. J. Symb. Comp., 20(3):343\u2013362, 1995.","journal-title":"J. Symb. Comp."},{"key":"22_CR10","doi-asserted-by":"crossref","unstructured":"M. Hermann and P.G. Kolaitis. Computational complexity of simultaneous elementary matching problems. In J. Wiedermann and P. H\u00e1jek, eds, Proc. 20th MFCS, Prague (Czech Republic), LNCS 969, pp 359\u2013370. Springer, 1995.","DOI":"10.1007\/3-540-60246-1_142"},{"issue":"1","key":"22_CR11","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(76)90068-2","volume":"3","author":"N.D. Jones","year":"1976","unstructured":"N.D. Jones and W.T. Laaser. Complete problems for deterministic polynomial time. Theoretical Comp. Sci., 3(1):105\u2013117, 1976.","journal-title":"Theoretical Comp. Sci."},{"key":"22_CR12","first-page":"67","volume-title":"Handbook of Theoretical Computer Science, Volume A","author":"D.S. Johnson","year":"1990","unstructured":"D.S. Johnson. A catalog of complexity classes. In J. van Leeuwen, ed, Handbook of Theoretical Computer Science, Volume A, chapter 2, pp 67\u2013161. North-Holland, Amsterdam, 1990."},{"key":"22_CR13","doi-asserted-by":"crossref","unstructured":"D. Kapur and P. Narendran. NP-completeness of the set unification and matching problems. In J.H. Siekmann, ed, Proc. 8th CADE, Oxford (England), LNCS 230, pp 489\u2013495. Springer, 1986.","DOI":"10.1007\/3-540-16780-3_113"},{"key":"22_CR14","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF00245463","volume":"9","author":"D. Kapur","year":"1992","unstructured":"D. Kapur and P. Narendran Complexity of unification problems with associative-commutative operators. J. of Autom. Reasoning, 9:261\u2013288, 1992.","journal-title":"J. of Autom. Reasoning"},{"issue":"1","key":"22_CR15","doi-asserted-by":"crossref","first-page":"49","DOI":"10.3233\/FI-1996-25105","volume":"25","author":"P. Narendran","year":"1996","unstructured":"P. Narendran. Unification modulo ACI+1+0. Fundamenta Informaticac, 25(1):49\u201357, 1996.","journal-title":"Fundamenta Informaticac"},{"key":"22_CR16","unstructured":"C.H. Papadimitriou. Computational complexity. Addison-Wesley, 1994."},{"issue":"1","key":"22_CR17","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1016\/0022-0000(84)90010-2","volume":"29","author":"D.A. Plaisted","year":"1984","unstructured":"D.A. Plaisted. Complete problems in the first-order predicate calculus. J. of Comp. and System Sci., 29(1):8\u201335, 1984.","journal-title":"J. of Comp. and System Sci."},{"issue":"1&2","key":"22_CR18","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0743-1066(92)90040-A","volume":"12","author":"O. Shmueli","year":"1992","unstructured":"O. Shmueli, S. Tsur, and C. Zaniolo. Compilation of set terms in the logic data language (LDL). J. Logic Prog., 12(1 & 2):89\u2013119, 1992.","journal-title":"J. Logic Prog."},{"key":"22_CR19","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"L.G. Valiant. The complexity of computing the permanent. Theoretical Comp. Sci., 8:189\u2013201, 1979.","journal-title":"Theoretical Comp. Sci."},{"issue":"3","key":"22_CR20","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"L.G. Valiant. The complexity of enumeration and reliability problems. SIAM J. on Comp., 8(3):410\u2013421, 1979.","journal-title":"SIAM J. on Comp."}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming-CP97"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0017446","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,19]],"date-time":"2021-07-19T23:48:07Z","timestamp":1626738487000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0017446"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540637530","9783540696421"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/bfb0017446","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/bfb0017424","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997]]}}}