{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T09:32:15Z","timestamp":1743067935301,"version":"3.40.3"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030865924"},{"type":"electronic","value":"9783030865931"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-86593-1_26","type":"book-chapter","created":{"date-parts":[[2021,9,11]],"date-time":"2021-09-11T20:26:28Z","timestamp":1631391988000},"page":"371-384","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Complexity of Word Problems for\u00a0HNN-Extensions"],"prefix":"10.1007","author":[{"given":"Markus","family":"Lohrey","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,9,9]]},"reference":[{"issue":"1","key":"26_CR1","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/BF02950718","volume":"4","author":"E Artin","year":"1925","unstructured":"Artin, E.: Theorie der Z\u00f6pfe. Abh. Math. Semin. Univ. Hambg. 4(1), 47\u201372 (1925)","journal-title":"Abh. Math. Semin. Univ. Hambg."},{"issue":"1\u20132","key":"26_CR2","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0304-3975(84)90024-0","volume":"32","author":"J Avenhaus","year":"1984","unstructured":"Avenhaus, J., Madlener, K.: The Nielsen reduction and P-complete problems in free groups. Theoret. Comput. Sci. 32(1\u20132), 61\u201376 (1984)","journal-title":"Theoret. Comput. Sci."},{"key":"26_CR3","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/BF02566077","volume":"53","author":"R Bieri","year":"1978","unstructured":"Bieri, R., Strebel, R.: Almost finitely presented soluble groups. Commentarii Mathematici Helvetici 53, 258\u2013278 (1978)","journal-title":"Commentarii Mathematici Helvetici"},{"key":"26_CR4","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-27596-7","volume-title":"Combinatorics of Coxeter Groups","author":"A Bj\u00f6rner","year":"2005","unstructured":"Bj\u00f6rner, A., Brenti, F.: Combinatorics of Coxeter Groups. Graduate Texts in Mathematics, vol. 231. Springer, New York (2005). https:\/\/doi.org\/10.1007\/3-540-27596-7"},{"key":"26_CR5","doi-asserted-by":"publisher","first-page":"207","DOI":"10.2307\/1970103","volume":"70","author":"WW Boone","year":"1959","unstructured":"Boone, W.W.: The word problem. Ann. Math. Second Series 70, 207\u2013265 (1959)","journal-title":"Ann. Math. Second Series"},{"issue":"1","key":"26_CR6","doi-asserted-by":"publisher","first-page":"16","DOI":"10.2307\/1970200","volume":"77","author":"JL Britton","year":"1963","unstructured":"Britton, J.L.: The word problem. Ann. Math. 77(1), 16\u201332 (1963)","journal-title":"Ann. Math."},{"key":"26_CR7","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s10711-007-9148-6","volume":"125","author":"R Charney","year":"2007","unstructured":"Charney, R.: An introduction to right-angled Artin groups. Geom. Dedicata. 125, 141\u2013158 (2007). https:\/\/doi.org\/10.1007\/s10711-007-9148-6","journal-title":"Geom. Dedicata."},{"key":"26_CR8","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/BF01456932","volume":"71","author":"M Dehn","year":"1911","unstructured":"Dehn, M.: \u00dcber unendliche diskontinuierliche Gruppen. Math. Ann. 71, 116\u2013144 (1911)","journal-title":"Math. Ann."},{"key":"26_CR9","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/BF01456725","volume":"72","author":"M Dehn","year":"1912","unstructured":"Dehn, M.: Transformation der Kurven auf zweiseitigen Fl\u00e4chen. Math. Ann. 72, 413\u2013421 (1912)","journal-title":"Math. Ann."},{"key":"26_CR10","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/j.jsc.2015.11.009","volume":"75","author":"V Diekert","year":"2016","unstructured":"Diekert, V., Kausch, J.: Logspace computations in graph products. J. Symb. Comput. 75, 94\u2013109 (2016)","journal-title":"J. Symb. Comput."},{"key":"26_CR11","doi-asserted-by":"crossref","unstructured":"Epstein, D.B.A., Cannon, J.W., Holt, D.F., Levy, S.V.F., Paterson, M.S., Thurston, W.P.: Word Processing in Groups. Jones and Bartlett (1992)","DOI":"10.1201\/9781439865699"},{"issue":"2","key":"26_CR12","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1142\/S0218196706002986","volume":"16","author":"DBA Epstein","year":"2006","unstructured":"Epstein, D.B.A., Holt, D.F.: The linearity of the conjugacy problem in word-hyperbolic groups. Internat. J. Algebra Comput. 16(2), 287\u2013306 (2006)","journal-title":"Internat. J. Algebra Comput."},{"key":"26_CR13","series-title":"Mathematical Sciences Research Institute Publications","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-1-4613-9586-7_3","volume-title":"Essays in Group Theory","author":"M Gromov","year":"1987","unstructured":"Gromov, M.: Hyperbolic groups. In: Gersten, S.M. (ed.) Essays in Group Theory. Mathematical Sciences Research Institute Publications, vol. 8, pp. 75\u2013263. Springer, Heidelberg (1987). https:\/\/doi.org\/10.1007\/978-1-4613-9586-7_3"},{"key":"26_CR14","unstructured":"Hagenah, C.: Gleichungen mit regul\u00e4ren Randbedingungen \u00fcber freien Gruppen. Ph.D. thesis, University of Stuttgart (2000)"},{"issue":"2","key":"26_CR15","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/s00224-010-9295-2","volume":"49","author":"N Haubold","year":"2011","unstructured":"Haubold, N., Lohrey, M.: Compressed word problems in HNN-extensions and amalgamated products. Theory Comput. Syst. 49(2), 283\u2013305 (2011). https:\/\/doi.org\/10.1007\/s00224-010-9295-2","journal-title":"Theory Comput. Syst."},{"key":"26_CR16","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1142\/S0218196700000078","volume":"10","author":"D Holt","year":"2000","unstructured":"Holt, D.: Word-hyperbolic groups have real-time word problem. Internat. J. Algebra Comput. 10, 221\u2013228 (2000)","journal-title":"Internat. J. Algebra Comput."},{"key":"26_CR17","unstructured":"Holt, D.F., Lohrey, M., Schleimer, S.: Compressed decision problems in hyperbolic groups. In: 36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, Berlin, Germany, 13\u201316 March 2019, LIPIcs, vol. 126, pp. 37:1\u201337:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). http:\/\/www.dagstuhl.de\/dagpub\/978-3-95977-100-9"},{"issue":"3","key":"26_CR18","doi-asserted-by":"publisher","first-page":"522","DOI":"10.1145\/322017.322031","volume":"24","author":"RJ Lipton","year":"1977","unstructured":"Lipton, R.J., Zalcstein, Y.: Word problems solvable in logspace. J. ACM 24(3), 522\u2013526 (1977)","journal-title":"J. ACM"},{"issue":"4","key":"26_CR19","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1142\/S0129054105003248","volume":"16","author":"M Lohrey","year":"2005","unstructured":"Lohrey, M.: Decidability and complexity in automatic monoids. Int. J. Found. Comput. Sci. 16(4), 707\u2013722 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"26_CR20","series-title":"Springer Briefs in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-0748-9","volume-title":"The Compressed Word Problem for Groups","author":"M Lohrey","year":"2014","unstructured":"Lohrey, M.: The Compressed Word Problem for Groups. Springer Briefs in Mathematics, Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-1-4939-0748-9"},{"key":"26_CR21","unstructured":"Lohrey, M.: Complexity of word problems for HNN-extensions. CoRR abs\/2107.01630 (2021). https:\/\/arxiv.org\/abs\/2107.01630"},{"issue":"1","key":"26_CR22","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01455888","volume":"106","author":"W Magnus","year":"1932","unstructured":"Magnus, W.: Das Identit\u00e4tsproblem f\u00fcr Gruppen mit einer definierenden Relation. Math. Ann. 106(1), 295\u2013307 (1932). https:\/\/doi.org\/10.1007\/BF01455888","journal-title":"Math. Ann."},{"key":"26_CR23","unstructured":"Mattes, C., Wei\u00df, A.: Parallel algorithms for power circuits and the word problem of the Baumslag group. CoRR abs\/2102.09921 (2021). https:\/\/arxiv.org\/abs\/2102.09921"},{"issue":"2","key":"26_CR24","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1142\/S0218196704001712","volume":"14","author":"A Minasyan","year":"2004","unstructured":"Minasyan, A.: On products of quasiconvex subgroups in hyperbolic groups. Int. J. Algebra Comput. 14(2), 173\u2013195 (2004)","journal-title":"Int. J. Algebra Comput."},{"issue":"2","key":"26_CR25","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1112\/jlms\/jdu034","volume":"90","author":"A Myasnikov","year":"2014","unstructured":"Myasnikov, A., Nikolaev, A.: Verbal subgroups of hyperbolic groups have infinite width. J. Lond. Math. Soc. 90(2), 573\u2013591 (2014)","journal-title":"J. Lond. Math. Soc."},{"key":"26_CR26","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1090\/S0025-5718-2014-02880-9","volume":"84","author":"A Myasnikov","year":"2015","unstructured":"Myasnikov, A., Nikolaev, A., Ushakov, A.: Knapsack problems in groups. Math. Comput. 84, 987\u20131016 (2015)","journal-title":"Math. Comput."},{"issue":"1","key":"26_CR27","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1016\/j.jalgebra.2011.07.024","volume":"345","author":"A Myasnikov","year":"2011","unstructured":"Myasnikov, A., Ushakov, A., Won, D.W.: The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable. J. Algebra 345(1), 324\u2013342 (2011)","journal-title":"J. Algebra"},{"key":"26_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1090\/trans2\/009\/01","volume":"9","author":"PS Novikov","year":"1958","unstructured":"Novikov, P.S.: On the algorithmic unsolvability of the word problem in group theory. Am. Math. Soc. Transl. II. Ser. 9, 1\u2013122 (1958)","journal-title":"Am. Math. Soc. Transl. II. Ser."},{"key":"26_CR29","first-page":"341","volume":"95","author":"MO Rabin","year":"1960","unstructured":"Rabin, M.O.: Computable algebra, general theory and theory of computable fields. Trans. Am. Math. Soc. 95, 341\u2013360 (1960)","journal-title":"Trans. Am. Math. Soc."},{"key":"26_CR30","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1112\/blms\/14.1.45","volume":"14","author":"E Rips","year":"1982","unstructured":"Rips, E.: Subgroups of small cancellation groups. Bull. Lond. Math. Soc. 14, 45\u201347 (1982)","journal-title":"Bull. Lond. Math. Soc."},{"key":"26_CR31","unstructured":"Simon, H.U.: Word problems for groups and contextfree recognition. In: Proceedings of Fundamentals of Computation Theory, FCT 1979, pp. 417\u2013422. Akademie-Verlag (1979)"},{"key":"26_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-4372-4","volume-title":"Classical Topology and Combinatorial Group Theory","author":"J Stillwell","year":"1995","unstructured":"Stillwell, J.: Classical Topology and Combinatorial Group Theory, 2nd edn. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/978-1-4612-4372-4","edition":"2"},{"key":"26_CR33","first-page":"265","volume":"26","author":"S Waack","year":"1990","unstructured":"Waack, S.: The parallel complexity of some constructions in combinatorial group theory. J. Inf. Process. Cybern. EIK 26, 265\u2013281 (1990)","journal-title":"J. Inf. Process. Cybern. EIK"},{"key":"26_CR34","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BF01214771","volume":"170","author":"BAF Wehrfritz","year":"1980","unstructured":"Wehrfritz, B.A.F.: On finitely generated soluble linear groups. Math. Z. 170, 155\u2013167 (1980)","journal-title":"Math. Z."},{"key":"26_CR35","unstructured":"Wei\u00df, A.: On the complexity of conjugacy in amalgamated products and HNN extensions. Ph.D. thesis, University of Stuttgart (2015)"},{"key":"26_CR36","unstructured":"Wei\u00df, A.: A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups. In: Algebra and Computer Science. Contemporary Mathematics, vol. 677. American Mathematical Society (2016)"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-86593-1_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,11]],"date-time":"2021-09-11T20:32:37Z","timestamp":1631392357000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-86593-1_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030865924","9783030865931"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-86593-1_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"9 September 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FCT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Fundamentals of Computation Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Athens","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 September 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 September 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fct2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.corelab.ntua.gr\/fct2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"94","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"8.54","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference was held virtually due to the COVID-19 pandemic. There are papers of 2 invited talks also included.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}