{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:14:25Z","timestamp":1767237265859},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2010,10,22]],"date-time":"2010-10-22T00:00:00Z","timestamp":1287705600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2011,8]]},"DOI":"10.1007\/s00224-010-9295-2","type":"journal-article","created":{"date-parts":[[2010,10,21]],"date-time":"2010-10-21T03:46:40Z","timestamp":1287632800000},"page":"283-305","source":"Crossref","is-referenced-by-count":8,"title":["Compressed Word Problems in HNN-extensions and\u00a0Amalgamated Products"],"prefix":"10.1007","volume":"49","author":[{"given":"Niko","family":"Haubold","sequence":"first","affiliation":[]},{"given":"Markus","family":"Lohrey","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,10,22]]},"reference":[{"key":"9295_CR1","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/978-0-387-09680-3_6","volume-title":"Proceeding of the 5th IFIP International Conference on Theoretical Computer Science (IFIP TCS 2008), Milan (Italy)","author":"A. Bertoni","year":"2008","unstructured":"Bertoni, A., Choffrut, C., Radicioni, R.: Literal shuffle of compressed words. In: Proceeding of the 5th IFIP International Conference on Theoretical Computer Science (IFIP TCS 2008), Milan (Italy), pp. 87\u2013100. Springer, Berlin (2008)"},{"key":"9295_CR2","doi-asserted-by":"crossref","first-page":"207","DOI":"10.2307\/1970103","volume":"70","author":"W.W. Boone","year":"1959","unstructured":"Boone, W.W.: The word problem. Ann. Math. (2) 70, 207\u2013265 (1959)","journal-title":"Ann. Math. (2)"},{"key":"9295_CR3","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/BF01455155","volume":"69","author":"M. Dehn","year":"1910","unstructured":"Dehn, M.: \u00dcber die Toplogie des dreidimensionalen Raumes. Math. Ann. 69, 137\u2013168 (1910). In German","journal-title":"Math. Ann."},{"key":"9295_CR4","volume-title":"Groups Acting on Graphs","author":"W. Dicks","year":"1989","unstructured":"Dicks, W., Dunwoody, M.J.: Groups Acting on Graphs. Cambridge University Press, Cambridge (1989)"},{"key":"9295_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1007\/3-540-61422-2_148","volume-title":"Proceedings of the 5th Scandinavian Workshop on Algorithm Theory (SWAT 1996), Reykjav\u00edk (Iceland)","author":"L. Gasieniec","year":"1996","unstructured":"Gasieniec, L., Karpinski, M., Plandowski, W., Rytter, W.: Efficient algorithms for Lempel-Ziv encoding (extended abstract). In: Karlsson, R.G., Lingas, A. (eds.) Proceedings of the 5th Scandinavian Workshop on Algorithm Theory (SWAT 1996), Reykjav\u00edk (Iceland). Lecture Notes in Computer Science, vol. 1097, pp. 392\u2013403. Springer, Berlin (1996)"},{"key":"9295_CR6","unstructured":"Hagenah, C.: Gleichungen mit regul\u00e4ren Randbedingungen \u00fcber freien Gruppen. PhD thesis, University of Stuttgart, Institut f\u00fcr Informatik (2000)"},{"key":"9295_CR7","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1112\/jlms\/s1-24.4.247","volume":"24","author":"G. Higman","year":"1949","unstructured":"Higman, G., Neumann, B.H., Neumann, H.: Embedding theorems for groups. J. Lond. Math. Soc. (2) 24, 247\u2013254 (1949)","journal-title":"J. Lond. Math. Soc. (2)"},{"key":"9295_CR8","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1093\/qmath\/14.1.254","volume":"14","author":"J.M. Howie","year":"1963","unstructured":"Howie, J.M.: Embedding theorems for semigroups. Q. J. Math. Oxford (2) 14, 254\u2013258 (1963)","journal-title":"Q. J. Math. Oxford (2)"},{"issue":"2","key":"9295_CR9","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1016\/S0021-8693(03)00167-4","volume":"264","author":"I. Kapovich","year":"2003","unstructured":"Kapovich, I., Myasnikov, A., Schupp, P., Shpilrain, V.: Generic-case complexity, decision problems in group theory, and random walks. J. Algebra 264(2), 665\u2013694 (2003)","journal-title":"J. Algebra"},{"key":"9295_CR10","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching (CPM 2007), London (Canada)","author":"Y. Lifshits","year":"2007","unstructured":"Lifshits, Y.: Processing compressed texts: A tractability border. In: Ma, B., Zhang, K. (eds.) Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching (CPM 2007), London (Canada). Lecture Notes in Computer Science, vol. 4580. Springer, Berlin (2007)"},{"issue":"5","key":"9295_CR11","doi-asserted-by":"crossref","first-page":"1210","DOI":"10.1137\/S0097539704445950","volume":"35","author":"M. Lohrey","year":"2006","unstructured":"Lohrey, M.: Word problems and membership problems on compressed words. SIAM J. Comput. 35(5), 1210\u20131240 (2006)","journal-title":"SIAM J. Comput."},{"key":"9295_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/978-3-540-74510-5_26","volume-title":"Proceedings of Computer Science in Russia (CSR 2007), Ekaterinburg (Russia)","author":"M. Lohrey","year":"2007","unstructured":"Lohrey, M., Schleimer, S.: Efficient computation in groups via compression. In: Proceedings of Computer Science in Russia (CSR 2007), Ekaterinburg (Russia). Lecture Notes in Computer Science, vol.\u00a04649, pp. 249\u2013258. Springer, Berlin (2007)"},{"key":"9295_CR13","series-title":"Lecture Notes in Computer Science","first-page":"681","volume-title":"Proceedings of the 33st International Colloquium on Automata, Languages and Programming (ICALP 2006), Venice (Italy)","author":"M. Lohrey","year":"2006","unstructured":"Lohrey, M., S\u00e9nizergues, G.: Theories of HNN-extensions and amalgamated products. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) Proceedings of the 33st International Colloquium on Automata, Languages and Programming (ICALP 2006), Venice (Italy). Lecture Notes in Computer Science, vol. 4052, pp. 681\u2013692. Springer, Berlin (2006)"},{"issue":"1","key":"9295_CR14","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1142\/S021819670800438X","volume":"18","author":"M. Lohrey","year":"2008","unstructured":"Lohrey, M., S\u00e9nizergues, G.: Rational subsets in HNN-extensions and amalgamated products. Int. J. Algebra Comput. 18(1), 111\u2013163 (2008)","journal-title":"Int. J. Algebra Comput."},{"key":"9295_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61896-3","volume-title":"Combinatorial Group Theory","author":"R.C. Lyndon","year":"1977","unstructured":"Lyndon, R.C., Schupp, P.E.: Combinatorial Group Theory. Springer, Berlin (1977)"},{"issue":"3","key":"9295_CR16","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1142\/S021819671000542X","volume":"20","author":"J. Macdonald","year":"2010","unstructured":"Macdonald, J.: Compressed words and automorphisms in fully residually free groups. Int. J. Algebra Comput. 20(3), 343\u2013355 (2010)","journal-title":"Int. J. Algebra Comput."},{"key":"9295_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-63220-4_45","volume-title":"Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching (CPM 97), Aarhus (Denmark)","author":"M. Miyazaki","year":"1997","unstructured":"Miyazaki, M., Shinohara, A., Takeda, M.: An improved pattern matching algorithm for strings in terms of straight-line programs. In: Apostolico, A., Hein, J. (eds.) Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching (CPM 97), Aarhus (Denmark). Lecture Notes in Computer Science, pp. 1\u201311. Springer, Berlin (1997)"},{"key":"9295_CR18","volume-title":"Group-based Cryptography","author":"A. Myasnikov","year":"2008","unstructured":"Myasnikov, A., Shpilrain, V., Ushakov, A.: Group-based Cryptography. Birkh\u00e4user, Boston (2008)"},{"key":"9295_CR19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1090\/trans2\/009\/01","volume":"9","author":"P.S. Novikov","year":"1958","unstructured":"Novikov, P.S.: On the algorithmic unsolvability of the word problem in group theory. Trans. Am. Math. Soc. II. Ser. 9, 1\u2013122 (1958)","journal-title":"Trans. Am. Math. Soc. II. Ser."},{"key":"9295_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1007\/BFb0049431","volume-title":"Second Annual European Symposium on Algorithms (ESA\u201994), Utrecht (The Netherlands)","author":"W. Plandowski","year":"1994","unstructured":"Plandowski, W.: Testing equivalence of morphisms on context-free languages. In: van Leeuwen, J. (ed.) Second Annual European Symposium on Algorithms (ESA\u201994), Utrecht (The Netherlands). Lecture Notes in Computer Science, vol. 855, pp. 460\u2013470. Springer, Berlin (1994)"},{"key":"9295_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1007\/BFb0055097","volume-title":"Proceedings of the 25th International Colloquium on Automata, Languages and Programming (ICALP 1998)","author":"W. Plandowski","year":"1998","unstructured":"Plandowski, W., Rytter, W.: Application of Lempel-Ziv encodings to the solution of word equations. In: Proceedings of the 25th International Colloquium on Automata, Languages and Programming (ICALP 1998). Lecture Notes in Computer Science, vol. 1443, pp. 731\u2013742. Springer, Berlin (1998)"},{"key":"9295_CR22","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1007\/978-3-642-60207-8_23","volume-title":"Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa","author":"W. Plandowski","year":"1999","unstructured":"Plandowski, W., Rytter, W.: Complexity of language recognition problems for compressed words. In: Karhum\u00e4ki, J., Maurer, H.A., Paun, G., Rozenberg, G. (eds.) Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa, pp. 262\u2013272. Springer, Berlin (1999)"},{"issue":"4","key":"9295_CR23","doi-asserted-by":"crossref","first-page":"741","DOI":"10.4171\/CMH\/142","volume":"83","author":"S. Schleimer","year":"2008","unstructured":"Schleimer, S.: Polynomial-time word problems. Comment. Math. Helv. 83(4), 741\u2013765 (2008)","journal-title":"Comment. Math. Helv."},{"key":"9295_CR24","series-title":"Yale Mathematical Monographs","volume-title":"Group Theory and Three-Dimensional Manifolds","author":"J.R. Stallings","year":"1971","unstructured":"Stallings, J.R.: Group Theory and Three-Dimensional Manifolds. Yale Mathematical Monographs, vol.\u00a04. Yale University Press, New Haven (1971)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-010-9295-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-010-9295-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-010-9295-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:54:22Z","timestamp":1558684462000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-010-9295-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10,22]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,8]]}},"alternative-id":["9295"],"URL":"https:\/\/doi.org\/10.1007\/s00224-010-9295-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10,22]]}}}