{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T23:04:59Z","timestamp":1776726299381,"version":"3.51.2"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540422877","type":"print"},{"value":"9783540482246","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_45","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T02:29:04Z","timestamp":1193538544000},"page":"543-554","source":"Crossref","is-referenced-by-count":14,"title":["Solvability of Equations in Free Partially Commutative Groups Is decidable"],"prefix":"10.1007","author":[{"given":"Volker","family":"Diekert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anca","family":"Muscholl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"45_CR1","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF00993053","volume":"8","author":"A. V. Anisimov","year":"1979","unstructured":"A. V. Anisimov and D. E. Knuth. Inhomogeneous sorting. International Journal of Computer and Information Sciences, 8:255\u2013260, 1979.","journal-title":"International Journal of Computer and Information Sciences"},{"key":"45_CR2","first-page":"1188","volume":"269","author":"M. Benois","year":"1969","unstructured":"M. Benois. Parties rationelles du groupe libre. C. R. Acad. Sci. Paris, S\u00e9r. A, 269:1188\u20131190, 1969.","journal-title":"C. R. Acad. Sci. Paris, S\u00e9r. A"},{"key":"45_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-53031-2","volume-title":"Combinatorics on Traces","author":"V. Diekert","year":"1990","unstructured":"V. Diekert. Combinatorics on Traces. LNCS 454. Springer, 1990."},{"key":"45_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1007\/3-540-44693-1_15","volume-title":"Proc. 18th Ann. Symp. on Theor. Aspects of Comp. Sci. (STACS\u201901)","author":"V. Diekert","year":"2001","unstructured":"V. Diekert, C. Guti\u00e9rrez, and C. Hagenah. The existential theory of equations with rational constraints in free groups is PSPACE-complete. In Proc. 18th Ann. Symp. on Theor. Aspects of Comp. Sci. (STACS\u201901), LNCS 2010:170\u2013182, Springer, 2001."},{"key":"45_CR5","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0304-3975(98)00313-2","volume":"224","author":"V. Diekert","year":"1999","unstructured":"V. Diekert, Yu. Matiyasevich, and A. Muscholl. Solving word equations modulo partial commutations. Theoretical Computer Science, 224:215\u2013235, 1999. Special issue of LFCS\u201997.","journal-title":"Theoretical Computer Science"},{"key":"45_CR6","doi-asserted-by":"crossref","DOI":"10.1142\/2563","volume-title":"The Book of Traces","author":"V. Diekert","year":"1995","unstructured":"V. Diekert and G. Rozenberg, editors. The Book of Traces. World Scientific, Singapore, 1995."},{"key":"45_CR7","doi-asserted-by":"publisher","first-page":"407","DOI":"10.2307\/2046419","volume":"100","author":"C. Droms","year":"1987","unstructured":"C. Droms. Isomorphisms of graph groups. Proc. American Mathematical Society, 100:407\u2013408, 1987.","journal-title":"Proc. American Mathematical Society"},{"key":"45_CR8","doi-asserted-by":"crossref","unstructured":"C. Guti\u00e9rrez. Satisfiability of equations in free groups is in PSPACE. In Proc. 32nd Ann. ACM Symp. on Theory of Computing, STOC\u20192000, pp. 21\u201327. ACM Press 2000.","DOI":"10.1145\/335305.335308"},{"key":"45_CR9","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/S0304-3975(96)00321-0","volume":"191","author":"A. Ko\u015bcielski","year":"1998","unstructured":"A. Ko\u015bcielski and L. Pacholski. Makanin\u2019s algorithm is not primitive recursive. Theoretical Computer Science, 191:145\u2013156, 1998.","journal-title":"Theoretical Computer Science"},{"key":"45_CR10","doi-asserted-by":"crossref","unstructured":"D. Kozen. Lower bounds for natural proof systems. In Proc. 18th Ann. Symp. On Found. of Comp. Sci., FOCS\u201977, pp. 254\u2013266, IEEE Computer Society Press 1977.","DOI":"10.1109\/SFCS.1977.16"},{"key":"45_CR11","first-page":"147","volume":"103","author":"G. S. Makanin","year":"1977","unstructured":"G. S. Makanin. The problem of solvability of equations in a free semigroup. Math. Sbornik, 103:147\u2013236, 1977. English transl. in Math. USSR Sbornik 32 (1977).","journal-title":"Math. Sbornik"},{"key":"45_CR12","first-page":"1199","volume":"46","author":"G. S. Makanin","year":"1983","unstructured":"G. S. Makanin. Equations in a free group. Izv. Akad. Nauk SSR, Ser. Math. 46:1199\u20131273, 1983. English transl. in Math. USSR Izv. 21 (1983).","journal-title":"Izv. Akad. Nauk SSR, Ser. Math."},{"key":"45_CR13","first-page":"735","volume":"48","author":"G. S. Makanin","year":"1984","unstructured":"G. S. Makanin. Decidability of the universal and positive theories of a free group. Izv. Akad. Nauk SSSR, Ser. Mat. 48:735\u2013749, 1984. In Russian; English translation in: Math. USSR Izvestija, 25, 75-88, 1985.","journal-title":"Izv. Akad. Nauk SSSR, Ser. Mat."},{"key":"45_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1007\/3-540-63045-7_25","volume-title":"Proc. 4th Int. Symp. On Log. Found. of Comp. Sci. (LFCS\u201997)","author":"Yu. Matiyasevich","year":"1997","unstructured":"Yu. Matiyasevich. Some decision problems for traces. In Proc. 4th Int. Symp. On Log. Found. of Comp. Sci. (LFCS\u201997), LNCS 1234: 248\u2013257, Springer, 1997. Invited lecture."},{"key":"45_CR15","doi-asserted-by":"crossref","unstructured":"A. Mazurkiewicz. Concurrent program schemes and their interpretations. DAIMI Rep. PB 78, Aarhus University, Aarhus, 1977.","DOI":"10.7146\/dpb.v6i78.7691"},{"key":"45_CR16","series-title":"Lect Notes Comput Sci","first-page":"279","volume-title":"Petri Nets, Applications and Relationship to other Models of Concurrency","author":"A. Mazurkiewicz","year":"1987","unstructured":"A. Mazurkiewicz. Trace theory. In Petri Nets, Applications and Relationship to other Models of Concurrency, LNCS 255: 279\u2013324, Springer, 1987."},{"key":"45_CR17","first-page":"56","volume":"27","author":"E. Ochma\u0144ski","year":"1985","unstructured":"E. Ochma\u0144ski. Regular behaviour of concurrent systems. Bulletin of the European Association for Theoretical Computer Science (EATCS), 27:56\u201367, 1985.","journal-title":"Bulletin of the European Association for Theoretical Computer Science (EATCS)"},{"key":"45_CR18","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1142\/9789814261456_0006","volume-title":"The Book of Traces","author":"E. Ochma\u0144ski","year":"1995","unstructured":"E. Ochma\u0144ski. Recognizable trace languages. In The Book of Traces, Chapter 6: 167\u2013204. World Scientific, Singapore, 1995."},{"key":"45_CR19","doi-asserted-by":"crossref","unstructured":"W. Plandowski. Satisfiability of word equations with constants is in PSPACE. In Proc. 40th Ann. Symp. on Found. of Comp. Sci., FOCS\u201999, pages 495\u2013500. IEEE Computer Society Press 1999.","DOI":"10.1109\/SFFCS.1999.814622"},{"key":"45_CR20","series-title":"Lect Notes Comput Sci","first-page":"85","volume-title":"Word Equations and Related Topics","author":"K. U. Schulz","year":"1991","unstructured":"K. U. Schulz. Makanin\u2019s algorithm for word equations \u2014 Two improvements and a generalization. In Word Equations and Related Topics, LNCS 572: 85\u2013150, Springer 1991."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T22:27:54Z","timestamp":1556922474000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_45","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2001]]}}}