{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T22:09:20Z","timestamp":1648937360544},"reference-count":8,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p> The consequences of regular expression hashing as a means of finite state automaton reduction is explored, based on variations of Brzozowski's algorithm. In this approach, each hash collision results in the merging of the automaton's states, and it is subsequently shown that a super-automaton will always be constructed, regardless of the hash function used. Since direct adaptation of the classical Brzozowski algorithm leads to a non-deterministic super-automaton, a new algorithm is put forward for constructing a deterministic FA. Approaches are proposed for measuring the quality of a hash function. <\/jats:p><jats:p> These ideas are empirically tested on a large sample of relatively small regular expressions and their associated automata, as well as on a small sample of relatively large regular expressions. Differences in the quality of tested hash functions are observed. Possible reasons for this are mentioned, but future empirical work is required to investigate the matter. <\/jats:p>","DOI":"10.1142\/s0129054109007042","type":"journal-article","created":{"date-parts":[[2009,11,22]],"date-time":"2009-11-22T20:28:50Z","timestamp":1258921730000},"page":"1069-1086","source":"Crossref","is-referenced-by-count":0,"title":["ON REGULAR EXPRESSION HASHING TO REDUCE FA SIZE"],"prefix":"10.1142","volume":"20","author":[{"given":"WIKUS","family":"COETSER","sequence":"first","affiliation":[{"name":"Fastar Research Group, Department of Computer Science, University of Pretoria, Pretoria, Gauteng, South Africa"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DERRICK G.","family":"KOURIE","sequence":"additional","affiliation":[{"name":"Fastar Research Group, Department of Computer Science, University of Pretoria, Pretoria, Gauteng, South Africa"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"BRUCE W.","family":"WATSON","sequence":"additional","affiliation":[{"name":"Fastar Research Group, Department of Computer Science, University of Pretoria, Pretoria, Gauteng, South Africa"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"rf1","first-page":"85","volume":"19","author":"Watson B. W.","journal-title":"International Journal of Foundations of Computer Science"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"rf3","volume-title":"A Finite Automata & Regular Expression Playground","author":"Frishert M.","year":"2004"},{"key":"rf4","first-page":"49","author":"Watson B. W.","journal-title":"Journal of Natural Language Engineering"},{"key":"rf5","volume-title":"Discrete Mathematics with Applications","author":"Epp S. S.","year":"1995"},{"key":"rf6","volume-title":"A taxonomy of finite automata minimization algorithms","author":"Watson B. W.","year":"1994"},{"key":"rf7","volume-title":"Elementary Computability, Formal Languages and Automata","author":"McNaughton R.","year":"1981"},{"key":"rf8","volume-title":"Introduction to probability and statistics","author":"Mendenhall W.","year":"2006"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054109007042","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T08:36:07Z","timestamp":1565080567000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054109007042"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":8,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[2009,12]]}},"alternative-id":["10.1142\/S0129054109007042"],"URL":"https:\/\/doi.org\/10.1142\/s0129054109007042","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]}}}