{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:44:53Z","timestamp":1740109493490,"version":"3.37.3"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T00:00:00Z","timestamp":1694563200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T00:00:00Z","timestamp":1694563200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Power circuits have been introduced in 2012 by Myasnikov, Ushakov and Won as a data structure for non-elementarily compressed integers supporting the arithmetic operations addition and <jats:inline-formula><jats:alternatives><jats:tex-math>$$(x,y) \\mapsto x\\cdot 2^y$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>x<\/mml:mi>\n                      <mml:mo>,<\/mml:mo>\n                      <mml:mi>y<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>\u21a6<\/mml:mo>\n                    <mml:mi>x<\/mml:mi>\n                    <mml:mo>\u00b7<\/mml:mo>\n                    <mml:msup>\n                      <mml:mn>2<\/mml:mn>\n                      <mml:mi>y<\/mml:mi>\n                    <\/mml:msup>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The same authors applied power circuits to give a polynomial time solution to the word problem of the Baumslag group, which has a non-elementary Dehn function.<\/jats:p><jats:p>In this work, we examine power circuits and the word problem of the\nBaumslag group under parallel complexity aspects. In particular, we\nestablish that the word problem of the Baumslag group can be solved\nin <jats:bold>NC<\/jats:bold><jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textemdash$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mo>\u2014<\/mml:mo>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>even though one of the essential steps is to compare two\nintegers given by power circuits and this, in general, is shown to\nbe <jats:bold>P<\/jats:bold>-complete. The key observation is that the depth of the\noccurring power circuits is logarithmic and such power circuits can\nbe compared in <jats:bold>NC<\/jats:bold>.<\/jats:p>","DOI":"10.1007\/s00037-023-00244-x","type":"journal-article","created":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T18:02:03Z","timestamp":1694628123000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parallel algorithms for power circuits and the word problem of the Baumslag group"],"prefix":"10.1007","volume":"32","author":[{"given":"Caroline","family":"Mattes","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Armin","family":"Wei\u00df","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,13]]},"reference":[{"key":"244_CR1","doi-asserted-by":"publisher","unstructured":"Carme \u00c0lvarez & Birgit Jenner (1993). A Very Hard log-Space Counting Class. Theor. Comput. Sci. 107(1), 3\u201330. URL https:\/\/doi.org\/10.1016\/0304-3975(93)90252-O.","DOI":"10.1016\/0304-3975(93)90252-O"},{"key":"244_CR2","doi-asserted-by":"crossref","unstructured":"Sanjeev Arora & Boaz Barak (2009). Computational Complexity - A Modern Approach. Cambridge University Press. ISBN 0521424267.","DOI":"10.1017\/CBO9780511804090"},{"key":"244_CR3","doi-asserted-by":"publisher","unstructured":"Owen Baker (2020). The conjugacy problem for Higman\u2019s group. Internat. J. Algebra Comput. 30(6), 1211\u20131235. URL https:\/\/doi.org\/10.1142\/S0218196720500393.","DOI":"10.1142\/S0218196720500393"},{"key":"244_CR4","doi-asserted-by":"publisher","unstructured":"Laurent Bartholdi, Michael Figelius, Markus Lohrey & Armin Wei\u00df (2023). Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete CompressedWord Problems. ACM Trans. Comput. Theory 14(3-4). ISSN 1942-3454. URL https:\/\/doi.org\/10.1145\/3569708.","DOI":"10.1145\/3569708"},{"key":"244_CR5","doi-asserted-by":"publisher","unstructured":"G. Baumslag, A. G. Myasnikov & V. Shpilrain (2002). Open problems in combinatorial group theory. Second Edition. In Combinatorial and geometric group theory, volume 296 of Contemporary Mathematics, 1\u201338. American Mathematical Society. URL https:\/\/doi.org\/10.1090\/conm\/296\/05067.","DOI":"10.1090\/conm\/296\/05067"},{"key":"244_CR6","doi-asserted-by":"publisher","unstructured":"Gilbert Baumslag (1969). A non-cyclic one-relator group all of whose finite quotients are cyclic. Journal of the Australian Mathematical Society 10(3-4), 497\u2013498. URL https:\/\/doi.org\/10.1017\/S1446788700007783.","DOI":"10.1017\/S1446788700007783"},{"key":"244_CR7","doi-asserted-by":"publisher","unstructured":"W. W. Boone (1959). The Word Problem. Ann. of Math. 70(2), 207\u2013265. URL https:\/\/doi.org\/10.2307\/1970103.","DOI":"10.2307\/1970103"},{"key":"244_CR8","doi-asserted-by":"publisher","unstructured":"John L. Britton (1963). The word problem. Ann. of Math. 77, 16\u201332. URL https:\/\/doi.org\/10.2307\/1970200.","DOI":"10.2307\/1970200"},{"key":"244_CR9","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest & Clifford Stein (2009). Introduction to Algorithms. The MIT Press, 3rd edition. ISBN 0262033844."},{"key":"244_CR10","doi-asserted-by":"publisher","unstructured":"Max Dehn (1911). Ueber unendliche diskontinuierliche Gruppen. Math. Ann. 71, 116\u2013144. URL https:\/\/doi.org\/10.1007\/BF01456932.","DOI":"10.1007\/BF01456932"},{"key":"244_CR11","doi-asserted-by":"publisher","unstructured":"Volker Diekert, J\u00fcrn Laun & Alexander Ushakov (2013). Efficient algorithms for highly compressed data: The word problem in Higman\u2019s group is in P. International Journal of Algebra and Computation 22(8). URL https:\/\/doi.org\/10.1142\/S0218196712400085.","DOI":"10.1142\/S0218196712400085"},{"key":"244_CR12","doi-asserted-by":"publisher","unstructured":"Volker Diekert, Alexei G. Myasnikov & Armin Wei\u00df (2016). Conjugacy in Baumslag\u2019s group, generic case complexity, and division in power circuits. Algorithmica 74, 961\u2013988. URL https:\/\/doi.org\/10.1007\/s00453-016-0117-z.","DOI":"10.1007\/s00453-016-0117-z"},{"key":"244_CR13","doi-asserted-by":"publisher","unstructured":"Will Dison, Eduard Einstein & Timothy R. Riley (2018). Taming the hydra: The word problem and extreme integer compression. Int. J. Algebra Comput. 28(7), 1299\u20131381. URL https:\/\/doi.org\/10.1142\/S0218196718500583.","DOI":"10.1142\/S0218196718500583"},{"key":"244_CR14","unstructured":"S. M. Gersten (1991). Isodiametric and isoperimetric inequalities in group extensions. Preprint."},{"key":"244_CR15","doi-asserted-by":"publisher","unstructured":"U. G\u00fcntzer & M. Paul (1987). Jump interpolation search trees and symmetric binary numbers. Information Processing Letters 26(4), 193\u2013204. URL https:\/\/doi.org\/10.1016\/0020-0190(87)90005-6.","DOI":"10.1016\/0020-0190(87)90005-6"},{"key":"244_CR16","doi-asserted-by":"publisher","unstructured":"Graham Higman (1951). A finitely generated infinite simple group. J. London Math. Soc. 26, 61\u201364. URL https:\/\/doi.org\/10.1112\/jlms\/s1-26.1.61.","DOI":"10.1112\/jlms\/s1-26.1.61"},{"key":"244_CR17","doi-asserted-by":"publisher","unstructured":"Jonathan Jedwab & Chris Mitchell (1989). Minimum weight modified signed-digit representations and fast exponentiation. Electronics Letters 25, 1171\u20131172. URL https:\/\/doi.org\/10.1049\/el:19890785.","DOI":"10.1049\/el:19890785"},{"key":"244_CR18","doi-asserted-by":"publisher","unstructured":"I. Kapovich, A. G. Miasnikov, P. Schupp & V. Shpilrain (2003). Generic-case complexity, decision problems in group theory and random walks. Journal of Algebra 264, 665\u2013694. URL https:\/\/doi.org\/10.1016\/S0021-8693(03)00167-4.","DOI":"10.1016\/S0021-8693(03)00167-4"},{"key":"244_CR19","unstructured":"Jonathan Kausch (2017). The parallel complexity of certain algorithmic problems in group theory. Dissertation, Institut f\u00a8ur Formale Methoden der Informatik, Universit\u00a8at Stuttgart. URL http:\/\/dx.doi.org\/10.18419\/opus-9152."},{"key":"244_CR20","doi-asserted-by":"publisher","unstructured":"Daniel K\u00f6nig & Markus Lohrey (2018). Evaluation of Circuits Over Nilpotent and Polycyclic Groups. Algorithmica 80(5), 1459\u20131492. URL https:\/\/doi.org\/10.1007\/s00453-017-0343-z.","DOI":"10.1007\/s00453-017-0343-z"},{"key":"244_CR21","doi-asserted-by":"publisher","unstructured":"J\u00fcrn Laun (2014). Efficient Algorithms for Highly Compressed Data: The Word Problem in Generalized Higman Groups Is in P. Theory Comput. Syst. 55(4), 742\u2013770. URL https:\/\/doi.org\/10.1007\/s00224-013-9509-5.","DOI":"10.1007\/s00224-013-9509-5"},{"key":"244_CR22","doi-asserted-by":"crossref","unstructured":"J. Lehnert & P. Schweitzer (2007). The co-word problem for the Higman-Thompson group is context-free. Bull. London Math. Soc. 39, 235\u2013241. URL http:\/\/blms.oxfordjournals.org\/content\/39\/2\/235.abstract.","DOI":"10.1112\/blms\/bdl043"},{"key":"244_CR23","doi-asserted-by":"publisher","unstructured":"Richard J. Lipton & Yechezkel Zalcstein (1977). Word Problems Solvable in Logspace. J. ACM 24, 522\u2013526. URL https:\/\/doi.org\/10.1145\/322017.322031.","DOI":"10.1145\/322017.322031"},{"key":"244_CR24","doi-asserted-by":"publisher","unstructured":"Markus Lohrey (2005). Decidability and complexity in automatic monoids. International Journal of Foundations of Computer Science 16(4), 707\u2013722. URL https:\/\/doi.org\/10.1007\/978-3-540-30550-7_26.","DOI":"10.1007\/978-3-540-30550-7_26"},{"key":"244_CR25","doi-asserted-by":"publisher","unstructured":"Markus Lohrey (2014). The Compressed Word Problem for Groups. Springer Briefs in Mathematics. Springer. URL https:\/\/doi.org\/10.1007\/978-1-4939-0748-9.","DOI":"10.1007\/978-1-4939-0748-9"},{"key":"244_CR26","doi-asserted-by":"crossref","unstructured":"Roger Lyndon & Paul Schupp (2001). Combinatorial Group Theory. Classics in Mathematics. Springer. ISBN 978-3-540-41158-1. First edition 1977.","DOI":"10.1007\/978-3-642-61896-3_1"},{"key":"244_CR27","doi-asserted-by":"crossref","unstructured":"Wilhelm Magnus (1932). Das Identit\u00e4tsproblem f\u00fcr Gruppen mit einer definierenden Relation. Mathematische Annalen 106, 295\u2013307. URL https:\/\/doi.org\/10.1007\/BF01455888.","DOI":"10.1007\/BF01455888"},{"key":"244_CR28","unstructured":"Wilhelm Magnus, Abraham Karrass & Donald Solitar (2004). Combinatorial Group Theory. Dover. ISBN 0486438309."},{"key":"244_CR29","doi-asserted-by":"publisher","unstructured":"Caroline Mattes & Armin Wei\u00df (2021). Parallel Algorithms for Power Circuits and the Word Problem of the Baumslag Group. In 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, volume 202 of LIPIcs, 74:1\u201374:24. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00a8ur Informatik. URL https:\/\/doi.org\/10.4230\/LIPIcs.MFCS.2021.74.","DOI":"10.4230\/LIPIcs.MFCS.2021.74"},{"key":"244_CR30","doi-asserted-by":"publisher","unstructured":"Caroline Mattes & Armin Wei\u00df (2022). Improved Parallel Algorithms for Generalized Baumslag Groups. In LATIN 2022: Theoretical Informatics, 658\u2013675. Springer International. URL https:\/\/doi.org\/10.1007\/978-3-031-20624-5_40.","DOI":"10.1007\/978-3-031-20624-5_40"},{"key":"244_CR31","doi-asserted-by":"publisher","unstructured":"Alexei Miasnikov & Andrey Nikolaev (2020). On parameterized complexity of the word search problem in the Baumslag-Gersten group. In ISSAC \u201920: International Symposium on Symbolic and Algebraic Computation, 2020, 360\u2013363. URL https:\/\/doi.org\/10.1145\/3373207.3404042.","DOI":"10.1145\/3373207.3404042"},{"key":"244_CR32","doi-asserted-by":"publisher","unstructured":"Alexei G. Myasnikov, Alexander Ushakov & Dong-Wook Won (2011). The Word Problem in the Baumslag group with a nonelementary Dehn function is polynomial time decidable. Journal of Algebra 345, 324\u2013342. URL https:\/\/doi.org\/10.1016\/j.jalgebra.2011.07.024","DOI":"10.1016\/j.jalgebra.2011.07.024"},{"key":"244_CR33","doi-asserted-by":"publisher","unstructured":"Alexei G. Myasnikov, Alexander Ushakov & Dong-Wook Won (2012). Power Circuits, exponential Algebra, and Time Complexity. International Journal of Algebra and Computation 22(6), 3\u201353. URL https:\/\/doi.org\/10.1142\/S0218196712500476.","DOI":"10.1142\/S0218196712500476"},{"key":"244_CR34","unstructured":"Alexei G. Myasnikov & Sasha Ushakov (2004\u20132013). Cryptography And Groups (CRAG). Software Library. URL http:\/\/www.stevens.edu\/algebraic\/downloads.php."},{"key":"244_CR35","doi-asserted-by":"publisher","unstructured":"P. S. Novikov (1955). On the algorithmic unsolvability of the word problem in group theory. Trudy Mat. Inst. Steklov 1\u2013143. URL https:\/\/doi.org\/10.2307\/2964487. In Russian.","DOI":"10.2307\/2964487"},{"key":"244_CR36","unstructured":"A. N. Platonov (2004). Isoparametric function of the Baumslag-Gersten group. Vestnik Moskov. Univ. Ser. I Mat. Mekh. 3, 12\u201317. URL https:\/\/www.mathnet.ru\/php\/archive.phtml?wshow=paper&jrnid=vmumm &paperid=1241 &option_lang=eng. Russian. Engl. transl. Moscow Univ. Math. Bull. 59 (3) (2004), 12\u201317."},{"key":"244_CR37","doi-asserted-by":"publisher","unstructured":"George W. Reitwiesner (1960). Binary Arithmetic. volume 1 of Advances in Computers, 231\u2013308. Elsevier. URL https:\/\/doi.org\/10.1016\/S0065-2458(08)60610-5.","DOI":"10.1016\/S0065-2458(08)60610-5"},{"key":"244_CR38","unstructured":"David Robinson (1993). Parallel Algorithms for Group Word Problems. Ph.D. thesis, University of California, San Diego. URL https:\/\/dl.acm.org\/doi\/10.5555\/165413."},{"key":"244_CR39","doi-asserted-by":"publisher","unstructured":"Mark V. Sapir, Jean-Camille Birget & Eliyahu Rips (2002). Isoperimetric and Isodiametric Functions of Groups. Ann. Math. 156(2), 345\u2013466. URL https:\/\/doi.org\/10.2307\/3597195.","DOI":"10.2307\/3597195"},{"key":"244_CR40","unstructured":"A. L. Semenov (1983). Logical theories of one-place functions on the natural number series. Izv. Akad. Nauk SSSR Ser. Mat. 47(3), 623\u2013658. URL https:\/\/www.mathnet.ru\/php\/archive.phtml?wshow=paper&jrnid=im&paperid=1415&option_lang=eng."},{"key":"244_CR41","unstructured":"J. O. Shallit (1993). A Primer on Balanced Binary Representations. Technical report. URL https:\/\/cs.uwaterloo.ca\/~shallit\/Papers\/bbr.pdf."},{"key":"244_CR42","unstructured":"Hans-Ulrich Simon (1979). Word problems for groups and contextfree recognition. In Proceedings of Fundamentals of Computation Theory (FCT\u201979), Berlin\/Wendisch-Rietz (GDR), 417\u2013422. Akademie-Verlag."},{"key":"244_CR43","doi-asserted-by":"publisher","unstructured":"Stephen D. Travers (2006). The complexity of membership problems for circuits over sets of integers. Theor. Comput. Sci. 369(1-3), 211\u2013229. URL https:\/\/doi.org\/10.1016\/j.tcs.2006.08.017.","DOI":"10.1016\/j.tcs.2006.08.017"},{"key":"244_CR44","doi-asserted-by":"crossref","unstructured":"Heribert Vollmer (1999). Introduction to Circuit Complexity. Springer, Berlin. ISBN 3540643109.","DOI":"10.1007\/978-3-662-03927-4"},{"key":"244_CR45","unstructured":"ArminWei\u00df (2015). On the Complexity of Conjugacy in Amalgamated Products and HNN Extensions. Dissertation, Institut f\u00fcr Formale Methoden der Informatik, Universit\u00e4t Stuttgart. URL http:\/\/dx.doi.org\/10.18419\/opus-3538."},{"key":"244_CR46","doi-asserted-by":"crossref","unstructured":"Armin Wei\u00df (2016). A Logspace Solution to the Word and Conjugacy problem of Generalized Baumslag-Solitar Groups. In Algebra and Computer Science, volume 677 of Contemporary Mathematics, 185\u2013212. American Mathematical Society. URL https:\/\/doi.org\/10.1090\/conm\/677\/13628.","DOI":"10.1090\/conm\/677\/13628"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00244-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-023-00244-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-023-00244-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,26]],"date-time":"2023-12-26T19:04:07Z","timestamp":1703617447000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-023-00244-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,13]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["244"],"URL":"https:\/\/doi.org\/10.1007\/s00037-023-00244-x","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2023,9,13]]},"assertion":[{"value":"6 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 September 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"10"}}