{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:02:31Z","timestamp":1725483751663},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540679011"},{"type":"electronic","value":"9783540446125"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44612-5_41","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T13:28:20Z","timestamp":1178371700000},"page":"456-466","source":"Crossref","is-referenced-by-count":1,"title":["Matching Modulo Associativity and Idempotency Is NP\u2014Complete"],"prefix":"10.1007","author":[{"given":"Ond\u0159ej","family":"Kl\u00edma","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ji\u0159\u00ed","family":"Srba","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,6,1]]},"reference":[{"key":"41_CR1","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/BF02328451","volume":"2","author":"F. Baader","year":"1986","unstructured":"Baader F.: The Theory of Idempotent Semigroups is of Unification Type Zero, J. of Automated Reasoning 2 (1986) 283\u2013286.","journal-title":"J. of Automated Reasoning"},{"key":"41_CR2","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/BF02575010","volume":"36","author":"F. Baader","year":"1987","unstructured":"Baader F.: Unification in Varieties of Idempotent Semigroups, Semigroup Forum 36 (1987) 127\u2013145.","journal-title":"Semigroup Forum"},{"key":"41_CR3","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1006\/jsco.1996.0009","volume":"21","author":"F. Baader","year":"1996","unstructured":"Baader F., Schulz K.U.: Unification in the Union of Disjoint Equational Theories: Combining Decision Procedures, J. Symbolic Computation 21 (1996) 211\u2013243.","journal-title":"J. Symbolic Computation"},{"key":"41_CR4","doi-asserted-by":"crossref","unstructured":"Baader F., Siekmann J.H.: Unification Theory, Handbook of Logic in Artificial Intelligence and Logic Programming (1993) Oxford University Press.","DOI":"10.1093\/oso\/9780198537465.003.0002"},{"key":"41_CR5","doi-asserted-by":"crossref","unstructured":"Book R., Otto F.: String-Rewriting Systems (1993) Springer-Verlag.","DOI":"10.1007\/978-1-4613-9771-7"},{"key":"41_CR6","unstructured":"\u010cern\u00e1 I., Kl\u00edma O., Srba J.: Pattern Equations and Equations with Stuttering, In Proceedings of SOFSEM\u201999, the 26th Seminar on Current Trends in Theory and Practice of Informatics (1999) 369\u2013378, Springer-Verlag."},{"key":"41_CR7","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1017\/S0305004100027341","volume":"48","author":"J.A. Green","year":"1952","unstructured":"Green J.A., Rees D.: On semigroups in which x r = x, Proc. Camb. Phil. Soc. 48 (1952) 35\u201340","journal-title":"Proc. Camb. Phil. Soc."},{"key":"41_CR8","unstructured":"Kl\u00edma O., Srba J.: Matching Modulo Associativity and Idempotency is NP-complete, Technical report RS-00-13, BRICS, Aarhus University (2000)."},{"key":"41_CR9","first-page":"3","volume":"64","author":"J. Ka\u010fourek","year":"1990","unstructured":"Ka\u010fourek J., Pol\u00e1k L.: On free semigroups satisfying x r = x, Simon Stevin 64, No. 1 (1990) 3\u201319","journal-title":"Simon Stevin"},{"key":"41_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1007\/3-540-16780-3_113","volume-title":"In Proceedings of CADE\u201986","author":"D. Kapur","year":"1986","unstructured":"Kapur D., Narendran P.: NP-completeness of the Set Unification and Matching Problems, In Proceedings of CADE\u201986, Springer LNCS volume 230 (1986) 489\u2013495, Springer-Verlag."},{"key":"41_CR11","unstructured":"Kope\u010dek I.: Automatic Segmentation into Syllable Segments, Proc. of First International Conference on Language Resources and Evaluation (1998) 1275\u20131279."},{"key":"41_CR12","unstructured":"Kope\u010dek I., Pala K.: Prosody Modelling for Syllable-Based Speech Synthesis, Proceedings of the IASTED International Conference on Artificial Intelligence and Soft Computing, Cancun (1998) 134\u2013137."},{"key":"41_CR13","unstructured":"Lothaire M.: Algebraic Combinatorics on Words, Preliminary version available at http:\/\/www-igm.univ-mlv.fr\/~berstel\/Lothaire\/index.html"},{"key":"41_CR14","unstructured":"Lothaire, M.: Combinatorics on Words, Volume 17 of Encyclopedia of Mathematics and its Applications (1983) Addison-Wesley."},{"issue":"2","key":"41_CR15","first-page":"147","volume":"103","author":"G. S. Makanin","year":"1977","unstructured":"Makanin, G. S.: The Problem of Solvability of Equations in a Free Semigroup, Mat. Sbornik. 103(2) (1977) 147\u2013236. (In Russian) English translation in: Math. USSR Sbornik 32 (1977) 129-198.","journal-title":"Mat. Sbornik"},{"key":"41_CR16","unstructured":"Papadimitriou, C.H.: Computational Complexity, Addison-Wesley Publishing Company (1994), Reading, Mass."},{"key":"41_CR17","doi-asserted-by":"crossref","unstructured":"Perrin D.: Equations in Words, In H. Ait-Kaci and M. Nivat, editors, Resolution of Equations in Algebraic Structures, Vol. 2 (1989) 275\u2013298, Academic Press.","DOI":"10.1016\/B978-0-12-046371-8.50015-8"},{"key":"41_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/3-540-55124-7_4","volume-title":"Proceedings of Word Equations and Related Topics, 1st International Workshop, IWW-ERT\u201990","author":"K. U. Schulz","year":"1992","unstructured":"Schulz, K. U.: Makanin\u2019s Algorithm for Word Equations: Two Improvements and a Generalization, In Schulz, K.-U. (ntEd.), Proceedings of Word Equations and Related Topics, 1st International Workshop, IWW-ERT\u201990, T\u00fcbingen, Germany, Vol. 572 of LNCS (1992) 85\u2013150, Berlin-Heidelberg-New York, Springer-Verlag."},{"key":"41_CR19","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/BF02328450","volume":"2","author":"M. Schmidt-Schauss","year":"1986","unstructured":"Schmidt-Schauss M.: Unification under Associativity and Idempotence is of Type Nullary, J. of Automated Reasoning 2 (1986) 277\u2013281.","journal-title":"J. of Automated Reasoning"},{"key":"41_CR20","doi-asserted-by":"crossref","unstructured":"Siekmann J., Szab\u00f3 P.: A Noetherian and Confluent Rewrite System for Idempotent Semigroups, Semigroup Forum 25 (1982).","DOI":"10.1007\/BF02573590"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44612-5_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,14]],"date-time":"2024-02-14T03:36:20Z","timestamp":1707881780000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44612-5_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679011","9783540446125"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-44612-5_41","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}