{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,12]],"date-time":"2024-08-12T18:38:09Z","timestamp":1723487889461},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2004,5]]},"abstract":"We prove that satisfiability problem for word equations is in PSPACE.<\/jats:p>","DOI":"10.1145\/990308.990312","type":"journal-article","created":{"date-parts":[[2004,7,20]],"date-time":"2004-07-20T16:39:33Z","timestamp":1090341573000},"page":"483-496","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":76,"title":["Satisfiability of word equations with constants is in PSPACE"],"prefix":"10.1145","volume":"51","author":[{"given":"Wojciech","family":"Plandowski","sequence":"first","affiliation":[{"name":"Warsaw University, Warsaw, Poland"}]}],"member":"320","published-online":{"date-parts":[[2004,5]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Abdulrab H. 1987. Resolution d'equations sur le mots: Etude et implementation lisp de l'algorithme de Makanin. Ph.D. dissertation Universite de Rouen Rouen France. Abdulrab H. 1987. Resolution d'equations sur le mots: Etude et implementation lisp de l'algorithme de Makanin. Ph.D. dissertation Universite de Rouen Rouen France."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(89)80056-2"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of Symposium on the Theory of Computing (STOC'79)","author":"Angluin D.","year":"1979"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Baader F. and Snyder W. 2001. Unification theory. In Handbook of Automated Reasoning Vol. 1 J. Robinson and A. Voronkov Eds. Elsevier Science Publishers 447--533. Baader F. and Snyder W. 2001. Unification theory. In Handbook of Automated Reasoning Vol. 1 J. Robinson and A. Voronkov Eds. Elsevier Science Publishers 447--533.","DOI":"10.1016\/B978-044450813-3\/50010-2"},{"key":"e_1_2_1_5_1","volume-title":"Algebraic Aspects of Combinatorics on Words","author":"Diekert V."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS'98)","author":"Gutierrez C.","year":"1998"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/78935.78938"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/337244.337255"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/234533.234543"},{"key":"e_1_2_1_10_1","volume-title":"Encyclopedia of Mathematics and Its Applications","volume":"17","author":"Lothaire M.","year":"1983"},{"key":"e_1_2_1_11_1","first-page":"147","article-title":"The problem of solvability of equations in a free semigroup","volume":"103","author":"Makanin G.","year":"1977","journal-title":"Matematiceskij Sbornik"},{"key":"e_1_2_1_12_1","unstructured":"P\u00e9cuchet J. 1981. Equations avec constantes et algorithme de Makanin. Ph.D. dissertation Laboratoire d'informatique in Rouen Rouen France. P\u00e9cuchet J. 1981. Equations avec constantes et algorithme de Makanin. Ph.D. dissertation Laboratoire d'informatique in Rouen Rouen France."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the European Symposium of Algorithms (ESA'94)","volume":"855","author":"Plandowski W.","year":"1994"},{"key":"e_1_2_1_14_1","unstructured":"Plandowski W. 1996. The complexity of the morphism equivalence problem for context-free languages. Ph.D. dissertation Warsaw University Warsaw Poland. Plandowski W. 1996. The complexity of the morphism equivalence problem for context-free languages. Ph.D. dissertation Warsaw University Warsaw Poland."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the Symposium on the Theory of Computing (STOC'99)","author":"Plandowski W.","year":"1999"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Plandowski W. and \n \n \n Rytter W\n \n \n . \n 1998\n . Application of lempel-ziv encodings to the solution of word equations. In Proceedings of the International Colloquium on Automata Languages and Programming (ICALP'98) Lecture Notes in Computer Science Vol. \n 1443\n . \n Springer-Verlag New York 731--742. Plandowski W. and Rytter W. 1998. Application of lempel-ziv encodings to the solution of word equations. In Proceedings of the International Colloquium on Automata Languages and Programming (ICALP'98) Lecture Notes in Computer Science Vol. 1443. Springer-Verlag New York 731--742.","DOI":"10.1007\/BFb0055097"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Symposium on the Theory of Computing (STOC'02)","author":"Schaefer M."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-55124-7","volume-title":"Proceedings of the International Workshop on Word Equations and Related Topics (IWWERT'90)","volume":"572","author":"Schulz K.","year":"1992"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/990308.990312","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,3]],"date-time":"2023-01-03T11:37:02Z","timestamp":1672745822000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/990308.990312"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,5]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2004,5]]}},"alternative-id":["10.1145\/990308.990312"],"URL":"https:\/\/doi.org\/10.1145\/990308.990312","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,5]]},"assertion":[{"value":"2004-05-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}