{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,20]],"date-time":"2025-07-20T04:11:34Z","timestamp":1752984694802,"version":"3.32.0"},"reference-count":16,"publisher":"World Scientific Pub Co Pte Ltd","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:p> We give a simple algorithm to solve the subgroup membership problem for virtually free groups given as a graph of finite groups. For a fixed virtually free group with a fixed generating set X, the subgroup membership problem is uniformly solvable in time [Formula: see text] where N is the sum of the word lengths of the inputs with respect to X. For practical purposes, this can be considered to be linear time. The algorithm is simple enough to work out small examples by hand and concrete examples are given to show how it can be used for computations in [Formula: see text] and [Formula: see text]. We also give fast algorithm to decide whether a finitely generated subgroup of a virtually free group is free. <\/jats:p>","DOI":"10.1142\/s0218196724500498","type":"journal-article","created":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T06:59:36Z","timestamp":1726210776000},"page":"1225-1252","source":"Crossref","is-referenced-by-count":1,"title":["A fast algorithm for Stallings foldings over virtually free groups"],"prefix":"10.1142","volume":"34","author":[{"given":"Samuel","family":"Cookson","sequence":"first","affiliation":[{"name":"New Brunswick Institute for Research, Data and Training (NB-IRDT), Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8848-2494","authenticated-orcid":false,"given":"Nicholas","family":"Touikan","sequence":"additional","affiliation":[{"name":"Department of Mathematics & Statistics, University of New Brunswick, Fredericton, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2024,12,31]]},"reference":[{"key":"S0218196724500498BIB001","doi-asserted-by":"publisher","DOI":"10.4171\/041"},{"key":"S0218196724500498BIB002","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2009","edition":"3"},{"key":"S0218196724500498BIB003","series-title":"Cambridge Studies in Advanced Mathematics","volume-title":"Groups Acting on Graphs","volume":"17","author":"Dicks W.","year":"1989"},{"key":"S0218196724500498BIB004","doi-asserted-by":"publisher","DOI":"10.1006\/jabr.2001.9033"},{"key":"S0218196724500498BIB005","doi-asserted-by":"publisher","DOI":"10.1142\/S021819670500213X"},{"key":"S0218196724500498BIB006","doi-asserted-by":"publisher","DOI":"10.1017\/S1446788700015445"},{"key":"S0218196724500498BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2017.05.037"},{"key":"S0218196724500498BIB008","first-page":"51:1","volume-title":"38th Int. Symp. Theoretical Aspects of Computer Science (STACS 2021)","author":"Lohrey M.","year":"2021"},{"key":"S0218196724500498BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61896-3"},{"key":"S0218196724500498BIB010","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196707003846"},{"key":"S0218196724500498BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90003-X"},{"key":"S0218196724500498BIB012","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107325449.007"},{"key":"S0218196724500498BIB013","doi-asserted-by":"publisher","DOI":"10.1515\/jgth-2015-0028"},{"key":"S0218196724500498BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/BF02095993"},{"key":"S0218196724500498BIB015","doi-asserted-by":"publisher","DOI":"10.1145\/321879.321884"},{"key":"S0218196724500498BIB016","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196706003396"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196724500498","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,2]],"date-time":"2025-01-02T06:31:53Z","timestamp":1735799513000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0218196724500498"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12]]},"references-count":16,"journal-issue":{"issue":"08","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["10.1142\/S0218196724500498"],"URL":"https:\/\/doi.org\/10.1142\/s0218196724500498","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"type":"print","value":"0218-1967"},{"type":"electronic","value":"1793-6500"}],"subject":[],"published":{"date-parts":[[2024,12]]}}}