{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T10:47:54Z","timestamp":1758278874869},"reference-count":31,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2008,3]]},"abstract":"<jats:p>We consider the subgroup lpG<jats:sub>k,1<\/jats:sub>of length preserving elements of the Thompson\u2013Higman group G<jats:sub>k,1<\/jats:sub>and we show that all elements of G<jats:sub>k,1<\/jats:sub>have a unique lpG<jats:sub>k,1<\/jats:sub>\u00b7 F<jats:sub>k,1<\/jats:sub>factorization. This applies to the Thompson\u2013Higman group T<jats:sub>k,1<\/jats:sub>as well. We show that lpG<jats:sub>k,1<\/jats:sub>is a \"diagonal\" direct limit of finite symmetric groups, and that lpT<jats:sub>k,1<\/jats:sub>is a k<jats:sup>\u221e<\/jats:sup>Pr\u00fcfer group. We find an infinite generating set of lpG<jats:sub>k,1<\/jats:sub>which is related to reversible boolean circuits.<\/jats:p><jats:p>We further investigate connections between the Thompson\u2013Higman groups, circuits, and complexity. We show that elements of F<jats:sub>k,1<\/jats:sub>cannot be one-way functions. We show that describing an element of G<jats:sub>k,1<\/jats:sub>by a generalized bijective circuit is equivalent to describing the element by a word over a certain infinite generating set of G<jats:sub>k,1<\/jats:sub>; word length over these generators is equivalent to generalized bijective circuit size.<\/jats:p><jats:p>We give some coNP-completeness results for G<jats:sub>k,1<\/jats:sub>(e.g., the word problem when elements are given by circuits), and [Formula: see text]-completeness results (e.g., finding the lpG<jats:sub>k,1<\/jats:sub>\u00b7 F<jats:sub>k,1<\/jats:sub>factorization of an element of G<jats:sub>k,1<\/jats:sub>given by a circuit).<\/jats:p>","DOI":"10.1142\/s0218196708004457","type":"journal-article","created":{"date-parts":[[2008,3,20]],"date-time":"2008-03-20T09:29:16Z","timestamp":1206005356000},"page":"285-320","source":"Crossref","is-referenced-by-count":6,"title":["FACTORIZATIONS OF THE THOMPSON\u2013HIGMAN GROUPS, AND CIRCUIT COMPLEXITY"],"prefix":"10.1142","volume":"18","author":[{"given":"JEAN-CAMILLE","family":"BIRGET","sequence":"first","affiliation":[{"name":"Department of Computer Science, Rutgers University at Camden, Camden, NJ 08102, USA"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196704001980"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196706002822"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/BF01388519"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02698834"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1112\/S0024610799007905"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1081\/AGB-200047404"},{"key":"rf8","author":"Brin M.","journal-title":"J. Group Theory"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1142\/S021819670600286X"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01388451"},{"key":"rf11","author":"Burillo J.","journal-title":"Trans. AMS"},{"key":"rf12","first-page":"215","volume":"42","author":"Cannon J. W.","journal-title":"L'Enseignement Math\u00e9matique"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-03-03375-0"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpaa.2005.02.012"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01857727"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02564445"},{"key":"rf17","first-page":"viii+117 pages","volume":"130","author":"Guba V.","journal-title":"Mem. Amer. Math. Soc."},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-011-0329-9"},{"key":"rf19","volume-title":"Notes on Pure Mathematics","volume":"8","author":"Higman G.","year":"1974"},{"key":"rf20","volume-title":"Locally Finite Groups","author":"Kegel O. H.","year":"1973"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322232"},{"key":"rf22","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195088496.001.0001","volume-title":"Parallel Computing Using the Prefix Problem","author":"Lakshmivarahan S.","year":"1994"},{"key":"rf23","unstructured":"R.\u00a0McKenzie and R. J.\u00a0Thompson, Word Problems, eds. W. W.\u00a0Boone, F. B.\u00a0Cannonito and R. C.\u00a0Lyndon (North-Holland, 1973)\u00a0pp. 457\u2013478."},{"key":"rf24","first-page":"223","volume":"52","author":"Nekrashevych V. V.","journal-title":"J. Oper. Theory"},{"key":"rf25","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(84)90172-8"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2003.811448"},{"key":"rf27","first-page":"57","volume":"12","author":"Sz\u00e9p J.","journal-title":"Acta Sci. Math. Szeged"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71348-X"},{"key":"rf32","volume-title":"Handbook of Theoretical Computer Science","author":"van Leeuwen J.","year":"1990"},{"key":"rf33","volume-title":"The Complexity of Boolean Functions","author":"Wegener I.","year":"1987"},{"key":"rf34","first-page":"132","volume":"2","author":"Zalesskii A. E.","journal-title":"Algebra and Analysis"},{"key":"rf35","unstructured":"G.\u00a0Zappa, Atti Secondo Congresso Un. Mat. Ital. (Edizioni Cremonense, Roma, Bologna, 1940)\u00a0pp. 119\u2013125."}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196708004457","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,6]],"date-time":"2021-09-06T05:11:15Z","timestamp":1630905075000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196708004457"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3]]},"references-count":31,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,3]]}},"alternative-id":["10.1142\/S0218196708004457"],"URL":"https:\/\/doi.org\/10.1142\/s0218196708004457","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,3]]}}}