{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T17:53:44Z","timestamp":1776880424893,"version":"3.51.2"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2008,9,30]],"date-time":"2008-09-30T00:00:00Z","timestamp":1222732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGCOMM Comput. Commun. Rev."],"published-print":{"date-parts":[[2008,9,30]]},"abstract":"<jats:p>Modern network devices need to perform deep packet inspection at high speed for security and application-specific services. Finite Automata (FAs) are used to implement regular expressions matching, but they require a large amount of memory. Many recent works have proposed improvements to address this issue.<\/jats:p>\n          <jats:p>This paper presents a new representation for deterministic finite automata (orthogonal to previous solutions), called Delta Finite Automata (\u03b4FA), which considerably reduces states and transitions and requires a transition per character only, thus allowing fast matching. Moreover, a new state encoding scheme is proposed and the comprehensive algorithm is tested for use in the packet classification area.<\/jats:p>","DOI":"10.1145\/1452335.1452339","type":"journal-article","created":{"date-parts":[[2008,10,22]],"date-time":"2008-10-22T12:25:40Z","timestamp":1224678340000},"page":"29-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":123,"title":["An improved DFA for fast regular expression matching"],"prefix":"10.1145","volume":"38","author":[{"given":"Domenico","family":"Ficara","sequence":"first","affiliation":[{"name":"University of Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefano","family":"Giordano","sequence":"additional","affiliation":[{"name":"University of Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gregorio","family":"Procissi","sequence":"additional","affiliation":[{"name":"University of Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabio","family":"Vitucci","sequence":"additional","affiliation":[{"name":"University of Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gianni","family":"Antichi","sequence":"additional","affiliation":[{"name":"University of Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea","family":"Di Pietro","sequence":"additional","affiliation":[{"name":"University of Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,9,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"key":"e_1_2_1_2_1","volume-title":"Compilers, principles, techniques, and tools","author":"Aho A.V.","year":"1985","unstructured":"A.V. Aho , R. Sethi , and J.D. Ullman . Compilers, principles, techniques, and tools . Addison Wesley , 1985 . A.V. Aho, R. Sethi, and J.D. Ullman. Compilers, principles, techniques, and tools. Addison Wesley, 1985."},{"key":"e_1_2_1_3_1","unstructured":"Bro: A system for Detecting Network Intruders in Real Time http:\/\/bro-ids.org\/.  Bro: A system for Detecting Network Intruders in Real Time http:\/\/bro-ids.org\/."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2007.128"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1364654.1364656"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1323548.1323573"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2006.7"},{"key":"e_1_2_1_8_1","unstructured":"Classbench A Packet Classification Benchmark http:\/\/www.arl.wustl.edu\/~det3\/ClassBench\/.  Classbench A Packet Classification Benchmark http:\/\/www.arl.wustl.edu\/~det3\/ClassBench\/."},{"key":"e_1_2_1_9_1","first-page":"118","volume-title":"Proc. of ICALP'79","author":"Commentz-Walter B.","unstructured":"B. Commentz-Walter . A string matching algorithm fast on the average . In Proc. of ICALP'79 , pages 118 -- 132 . Springer-Verlag . B. Commentz-Walter. A string matching algorithm fast on the average. In Proc. of ICALP'79, pages 118--132. Springer-Verlag."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/997150.997160"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316217"},{"key":"e_1_2_1_12_1","unstructured":"Intel Network Processors www.intel.com\/design\/network\/products\/npfamily\/.  Intel Network Processors www.intel.com\/design\/network\/products\/npfamily\/."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1323548.1323574"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159913.1159952"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1185347.1185359"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/285237.285283"},{"key":"e_1_2_1_17_1","unstructured":"Haoyu Song Evaluation of Packet Classification Algorithms www.arl.wustl.edu\/~hs1\/PClassEval.html.  Haoyu Song Evaluation of Packet Classification Algorithms www.arl.wustl.edu\/~hs1\/PClassEval.html."},{"key":"e_1_2_1_18_1","unstructured":"Michela Becchi regex tool http:\/\/regex.wustl.edu\/.  Michela Becchi regex tool http:\/\/regex.wustl.edu\/."},{"key":"e_1_2_1_19_1","volume-title":"Packet classification using multidimensional cutting. Technical report","author":"Singh S.","year":"2003","unstructured":"S. Singh , F. Baboescu , G. Varghese , and J. Wang . Packet classification using multidimensional cutting. Technical report , 2003 . S. Singh, F. Baboescu, G. Varghese, and J. Wang. Packet classification using multidimensional cutting. Technical report, 2003."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2008.14"},{"key":"e_1_2_1_21_1","volume-title":"University of Wisconsin","author":"Smith R.","year":"2007","unstructured":"R. Smith , C. Estan , and S. Jha . Xfas: Fast and compact signature matching. Technical report , University of Wisconsin , Madison , August 2007 . R. Smith, C. Estan, and S. Jha. Xfas: Fast and compact signature matching. Technical report, University of Wisconsin, Madison, August 2007."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/948109.948145"},{"key":"e_1_2_1_23_1","unstructured":"Snort: Lightweight Intrusion Detection for Networks http:\/\/www.snort.org\/.  Snort: Lightweight Intrusion Detection for Networks http:\/\/www.snort.org\/."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2004.1354682"},{"key":"e_1_2_1_25_1","volume-title":"Network Algorithmics,: An Interdisciplinary Approach to Designing Fast Networked Devices","author":"Varghese G.","year":"2004","unstructured":"G. Varghese . Network Algorithmics,: An Interdisciplinary Approach to Designing Fast Networked Devices . Morgan Kaufmann Publishers Inc ., San Francisco, CA, USA, 2004 . G. Varghese. Network Algorithmics,: An Interdisciplinary Approach to Designing Fast Networked Devices. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2004."},{"key":"e_1_2_1_26_1","unstructured":"J.W. Will Eatherton. An encoded version of reg-ex database from cisco systems provided for research purposes.  J.W. Will Eatherton. An encoded version of reg-ex database from cisco systems provided for research purposes."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1185347.1185360"}],"container-title":["ACM SIGCOMM Computer Communication Review"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1452335.1452339","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1452335.1452339","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:06Z","timestamp":1750253406000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1452335.1452339"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,9,30]]},"references-count":27,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2008,9,30]]}},"alternative-id":["10.1145\/1452335.1452339"],"URL":"https:\/\/doi.org\/10.1145\/1452335.1452339","relation":{},"ISSN":["0146-4833"],"issn-type":[{"value":"0146-4833","type":"print"}],"subject":[],"published":{"date-parts":[[2008,9,30]]},"assertion":[{"value":"2008-09-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}