{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:32:12Z","timestamp":1740133932400,"version":"3.37.3"},"reference-count":12,"publisher":"World Scientific Pub Co Pte Ltd","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,11]]},"abstract":"<jats:p> Glushkov automaton is an efficient structure for matching regular expressions. We present an [Formula: see text] bits space representation of Glushkov automata of regular expressions, where [Formula: see text] is the number of strings in the regular expression. The state transition runs in time [Formula: see text], where [Formula: see text] is the size of machine words, and [Formula: see text] is the number of states in the Glushkov automaton. For [Formula: see text], the time is [Formula: see text]. Our approach is based on two operations on words that retrieve and set bits on a specific set of positions of a word. We present implementations of these operations using bit-parallelism and a permutation network, which are simple and efficient. <\/jats:p>","DOI":"10.1142\/s0129054118500223","type":"journal-article","created":{"date-parts":[[2018,11,11]],"date-time":"2018-11-11T23:18:10Z","timestamp":1541978290000},"page":"1089-1105","source":"Crossref","is-referenced-by-count":0,"title":["Space-Efficient Representations for Glushkov Automata"],"prefix":"10.1142","volume":"29","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9606-2382","authenticated-orcid":false,"given":"Meng","family":"Zhang","sequence":"first","affiliation":[{"name":"College of Computer Science and Technology, Jilin University, Changchun, China"},{"name":"Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun, China"}]},{"given":"Yi","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Jilin Business and Technology College, Changchun, China"}]}],"member":"219","published-online":{"date-parts":[[2018,11,11]]},"reference":[{"key":"S0129054118500223BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00182-4"},{"key":"S0129054118500223BIB004","doi-asserted-by":"publisher","DOI":"10.1145\/135239.135243"},{"key":"S0129054118500223BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90088-5"},{"key":"S0129054118500223BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.08.042"},{"key":"S0129054118500223BIB011","doi-asserted-by":"publisher","DOI":"10.1070\/RM1961v016n05ABEH004112"},{"key":"S0129054118500223BIB012","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931"},{"key":"S0129054118500223BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00090-7"},{"key":"S0129054118500223BIB014","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1960.5221603"},{"key":"S0129054118500223BIB015","doi-asserted-by":"publisher","DOI":"10.1145\/128749.128755"},{"key":"S0129054118500223BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1120-3"},{"key":"S0129054118500223BIB019","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"S0129054118500223BIB020","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2016.07.003"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118500223","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T08:48:47Z","timestamp":1565167727000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118500223"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11]]},"references-count":12,"journal-issue":{"issue":"07","published-online":{"date-parts":[[2018,11,11]]},"published-print":{"date-parts":[[2018,11]]}},"alternative-id":["10.1142\/S0129054118500223"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118500223","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2018,11]]}}}