{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T20:03:44Z","timestamp":1749499424305},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540432838"},{"type":"electronic","value":"9783540458418"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45841-7_41","type":"book-chapter","created":{"date-parts":[[2007,8,12]],"date-time":"2007-08-12T08:11:17Z","timestamp":1186906277000},"page":"501-512","source":"Crossref","is-referenced-by-count":3,"title":["Existential and Positive Theories of Equations in Graph Products"],"prefix":"10.1007","author":[{"given":"Volker","family":"Diekert","sequence":"first","affiliation":[]},{"given":"Markus","family":"Lohrey","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,2,21]]},"reference":[{"key":"41_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02088289","volume":"22","author":"IJ. J. Aalbersberg","year":"1989","unstructured":"IJ. J. Aalbersberg and H. J. Hoogeboom. Characterizations of the decidability of some problems for regular trace languages. Mathematical Systems Theory, 22:1\u201319, 1989.","journal-title":"Mathematical Systems Theory"},{"key":"41_CR2","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":"41_CR3","first-page":"1188","volume":"269","author":"M. Benois","year":"1969","unstructured":"M. Benois. Parties rationnelles du groupe libre. C. R. Acad. Sci. Paris, S\u00e9r. A, 269:1188\u20131190, 1969.","journal-title":"C. R. Acad. Sci."},{"key":"41_CR4","doi-asserted-by":"crossref","unstructured":"J. Berstel. Transductions and context-free languages. Teubner Studienb\u00fccher, Stuttgart, 1979.","DOI":"10.1007\/978-3-663-09367-1"},{"issue":"2","key":"41_CR5","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/s002330010075","volume":"63","author":"A. V. Costa da","year":"2001","unstructured":"A. V. da Costa. Graph products of monoids. Semigroup Forum, 63(2):247\u2013277, 2001.","journal-title":"Semigroup Forum"},{"key":"41_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1007\/3-540-44693-1_15","volume-title":"The existential theory of equations with rational constraints in free groups is PSPACE-complete","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 Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS 01), number 2010 in Lecture Notes in Computer Science, pages 170\u2013182. Springer, 2001."},{"key":"41_CR7","unstructured":"V. Diekert and M. Lohrey. A note on the existential theory of equations in plain groups. International Journal of Algebra and Computation, 2001. to apear."},{"key":"41_CR8","unstructured":"V. Diekert and M. Lohrey. Existential and positive theories of equations in graph products. Technical Report 2001\/10, University of Stuttgart, Germany, 2001."},{"issue":"1\u20132","key":"41_CR9","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, Y. Matiyasevich, and A. Muscholl. Solving word equations modulo partial commutations. Theoretical Computer Science, 224(1\u20132):215\u2013235, 1999.","journal-title":"Theoretical Computer Science"},{"key":"41_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"543","DOI":"10.1007\/3-540-48224-5_45","volume-title":"Solvability of equations in free partially commutative groups is decidable","author":"V. Diekert","year":"2001","unstructured":"V. Diekert and A. Muscholl. Solvability of equations in free partially commutative groups is decidable. In Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP 01), number 2076 in Lecture Notes in Computer Science, pages 543\u2013554. Springer, 2001."},{"key":"41_CR11","doi-asserted-by":"crossref","unstructured":"V. Diekert and G. Rozenberg, editors. The Book of Traces. World Scientific, 1995.","DOI":"10.1142\/2563"},{"issue":"2","key":"41_CR12","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1016\/0021-8693(87)90010-X","volume":"106","author":"C. Droms","year":"1985","unstructured":"C. Droms. Graph groups, coherence and three-manifolds. Journal of Algebra, 106(2):484\u2013489, 1985.","journal-title":"Journal of Algebra"},{"issue":"5","key":"41_CR13","first-page":"1067","volume":"36","author":"V. G. Durnev","year":"1995","unstructured":"V. G. Durnev. Undecidability of the positive \u212c\u22033-theory of a free semi-group. Sibirsky Matematicheskie Jurnal, 36(5):1067\u20131080, 1995.","journal-title":"Sibirsky Matematicheskie Jurnal"},{"key":"41_CR14","unstructured":"E. R. Green. Graph Products of Groups. PhD thesis, The University of Leeds, 1990."},{"key":"41_CR15","doi-asserted-by":"crossref","unstructured":"C. Guti\u00e9rrez. Satisfiability of equations in free groups is in PSPACE. In 32nd Annual ACM Symposium on Theory of Computing (STOC\u20192000), pages 21\u201327. ACM Press, 2000.","DOI":"10.1145\/335305.335308"},{"key":"41_CR16","doi-asserted-by":"publisher","first-page":"337","DOI":"10.2307\/1999388","volume":"279","author":"R. H. Haring-Smith","year":"1983","unstructured":"R. H. Haring-Smith. Groups and simple languages. Transactions of the American Mathematical Society, 279:337\u2013356, 1983.","journal-title":"Transactions of the American Mathematical Society"},{"key":"41_CR17","doi-asserted-by":"crossref","unstructured":"D. Kozen. Lower bounds for natural proof systems. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science, (FOCS 77), pages 254\u2013266. IEEE Computer Society Press, 1977.","DOI":"10.1109\/SFCS.1977.16"},{"key":"41_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.2001.3055","volume":"170","author":"M. Lohrey","year":"2001","unstructured":"M. Lohrey. Confluence problems for trace rewriting systems. Information and Computation, 170:1\u201325, 2001.","journal-title":"Information and Computation"},{"key":"41_CR19","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. (Russian); English translation in Math. USSR Sbornik 32 (1977).","journal-title":"Math. Sbornik"},{"key":"41_CR20","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. (Russian); English translation in Math. USSR Izv. 21 (1983).","journal-title":"Izv. Akad. Nauk SSR"},{"key":"41_CR21","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. (Russian); English translation in: Math. USSR Izvestija, 25, 75\u201388, 1985.","journal-title":"Izv. Akad. Nauk SSSR"},{"issue":"1","key":"41_CR22","first-page":"196","volume":"23","author":"S. S. Marchenkov","year":"1982","unstructured":"S. S. Marchenkov. Unsolvability of positive \u212c\u2203-theory of a free semi-group. Sibirsky Matematicheskie Jurnal, 23(1):196\u2013198, 1982.","journal-title":"Sibirsky Matematicheskie Jurnal"},{"issue":"4","key":"41_CR23","first-page":"25","volume":"5","author":"Y. I. Merzlyakov","year":"1966","unstructured":"Y. I. Merzlyakov. Positive formulas on free groups. Algebra i Logika Sem., 5(4):25\u201342, 1966. (Russian).","journal-title":"Algebra i Logika Sem."},{"key":"41_CR24","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":"41_CR25","doi-asserted-by":"crossref","unstructured":"W. Plandowski. Satisfiability of word equations with constants is in PSPACE. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS 99), pages 495\u2013500. IEEE Computer Society Press, 1999.","DOI":"10.1109\/SFFCS.1999.814622"},{"key":"41_CR26","first-page":"92","volume":"395","author":"M. Presburger","year":"1927","unstructured":"M. Presburger. \u00dcber die Vollst\u00e4ndigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. In Comptes Rendus du Premier Congr\u00e8s des Math\u00e9maticienes des Pays Slaves, pages 92\u2013101, 395, Warsaw, 1927.","journal-title":"Comptes Rendus du Premier Congr\u00e8s des Math\u00e9maticienes des Pays Slaves"},{"key":"41_CR27","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, number 572 in Lecture Notes in Computer Science, pages 85\u2013150. Springer, 1991."}],"container-title":["Lecture Notes in Computer Science","STACS 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45841-7_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T23:59:50Z","timestamp":1556755190000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45841-7_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540432838","9783540458418"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-45841-7_41","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}