{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T04:11:15Z","timestamp":1751602275881,"version":"3.41.0"},"publisher-location":"Cham","reference-count":45,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319899626"},{"type":"electronic","value":"9783319899633"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-89963-3_9","type":"book-chapter","created":{"date-parts":[[2018,4,13]],"date-time":"2018-04-13T18:53:00Z","timestamp":1523645580000},"page":"155-175","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Approximate Reduction of Finite Automata for High-Speed Network Intrusion Detection"],"prefix":"10.1007","author":[{"given":"Milan","family":"\u010ce\u0161ka","sequence":"first","affiliation":[]},{"given":"Vojt\u011bch","family":"Havlena","sequence":"additional","affiliation":[]},{"given":"Luk\u00e1\u0161","family":"Hol\u00edk","sequence":"additional","affiliation":[]},{"given":"Ond\u0159ej","family":"Leng\u00e1l","sequence":"additional","affiliation":[]},{"given":"Tom\u00e1\u0161","family":"Vojnar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,4,14]]},"reference":[{"key":"9_CR1","unstructured":"The Snort Team: Snort. http:\/\/www.snort.org"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Becchi, M., Wiseman, C., Crowley, P.: Evaluating regular expression matching engines on network and general purpose processors. In: Proceedings of ANCS 2009, pp. 30\u201339. ACM (2009)","DOI":"10.1145\/1882486.1882495"},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Ko\u0159enek, J., Kobiersk\u00fd, P.: Intrusion detection system intended for multigigabit networks. In: Proceedings of DDECS 2007. IEEE (2007)","DOI":"10.1109\/DDECS.2007.4295313"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Ka\u0161til, J., Ko\u0159enek, J., Leng\u00e1l, O.: Methodology for fast pattern matching by deterministic finite automaton with perfect hashing. In: Proceedings of DSD 2007, pp. 823\u2013829. IEEE (2009)","DOI":"10.1109\/DSD.2009.149"},{"key":"9_CR5","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, D., Ko\u0159enek, J., Pu\u0161, V.: High-speed regular expression matching with pipelined automata. In: Proceedings of FPT 2016, pp. 93\u2013100. IEEE (2016)","DOI":"10.1109\/FPT.2016.7929431"},{"issue":"4","key":"9_CR6","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1145\/1151659.1159952","volume":"36","author":"Sailesh Kumar","year":"2006","unstructured":"Kumar, S., Dharmapurikar, S., Yu, F., Crowley, P., Turner, J.S.: Algorithms to accelerate multiple regular expressions matching for deep packet inspection. In: Proceedings of SIGCOMM 2006, pp. 339\u2013350. ACM (2006)","journal-title":"ACM SIGCOMM Computer Communication Review"},{"key":"9_CR7","doi-asserted-by":"crossref","unstructured":"Tan, L., Sherwood, T.: A high throughput string matching architecture for intrusion detection and prevention. In: Proceedings of ISCA 2005, pp. 112\u2013122. IEEE (2005)","DOI":"10.1145\/1080695.1069981"},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"Kumar, S., Turner, J.S., Williams, J.: Advanced algorithms for fast and scalable deep packet inspection. In: Proceedings of ANCS 2006, pp. 81\u201392. ACM (2006)","DOI":"10.1145\/1185347.1185359"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Becchi, M., Crowley, P.: A hybrid finite automaton for practical deep packet inspection. In: Proceedings of CoNEXT 2007. ACM (2007)","DOI":"10.1145\/1364654.1364656"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Becchi, M., Crowley, P.: An improved algorithm to accelerate regular expression evaluation. In: Proceedings of ANCS 2007, pp. 145\u2013154. ACM (2007)","DOI":"10.1145\/1323548.1323573"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Kumar, S., Chandrasekaran, B., Turner, J.S., Varghese, G.: Curing regular expressions matching algorithms from insomnia, amnesia, and acalculia. In: Proceedings of ANCS 2007, 155\u2013164. ACM (2007)","DOI":"10.1145\/1323548.1323574"},{"key":"9_CR12","doi-asserted-by":"crossref","unstructured":"Yu, F., Chen, Z., Diao, Y., Lakshman, T.V., Katz, R.H.: Fast and memory-efficient regular expression matching for deep packet inspection. In: Proceedings of ANCS 2006, pp. 93\u2013102. ACM (2006)","DOI":"10.1145\/1185347.1185360"},{"issue":"2","key":"9_CR13","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1109\/TC.2011.231","volume":"62","author":"C Liu","year":"2013","unstructured":"Liu, C., Wu, J.: Fast deep packet inspection with a dual finite automata. IEEE Trans. Comput. 62(2), 310\u2013321 (2013)","journal-title":"IEEE Trans. Comput."},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Luchaup, D., De Carli, L., Jha, S., Bach, E.: Deep packet inspection with DFA-trees and parametrized language overapproximation. In: Proceedings of INFOCOM 2014, pp. 531\u2013539. IEEE (2014)","DOI":"10.1109\/INFOCOM.2014.6847977"},{"key":"9_CR15","unstructured":"Mitra, A., Najjar, W.A., Bhuyan, L.N.: Compiling PCRE to FPGA for accelerating SNORT IDS. In: Proceedings of ANCS 2007. ACM (2007) 127\u2013136"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"Brodie, B.C., Taylor, D.E., Cytron, R.K.: A scalable architecture for high-throughput regular-expression pattern matching. In: Proceedings of ISCA 2006, pp. 191\u2013202. IEEE (2006)","DOI":"10.1145\/1150019.1136500"},{"key":"9_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"956","DOI":"10.1007\/978-3-540-45234-8_94","volume-title":"Field Programmable Logic and Application","author":"CR Clark","year":"2003","unstructured":"Clark, C.R., Schimmel, D.E.: Efficient reconfigurable logic circuits for matching complex network intrusion detection patterns. In: Y. K. Cheung, P., Constantinides, G.A. (eds.) FPL 2003. LNCS, vol. 2778, pp. 956\u2013959. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-45234-8_94"},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"Hutchings, B.L., Franklin, R., Carver, D.: Assisting network intrusion detection with reconfigurable Hardware. In: Proceedings of FCCM 2002, pp. 111\u2013120. IEEE (2002)","DOI":"10.1109\/FPGA.2002.1106666"},{"key":"9_CR19","unstructured":"Sidhu, R.P.S., Prasanna, V.K.: Fast regular expression matching using FPGAs. In: Proceedings of FCCM 2001, pp. 227\u2013238. IEEE (2001)"},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"Pu\u0161, V., Tobola, J., Ko\u0161a\u0159, V., Ka\u0161til, J., Ko\u0159enek, J.: Netbench: framework for evaluation of packet processing algorithms. In: Proceedings of ANCS 2011, pp. 95\u201396. ACM\/IEEE (2011)","DOI":"10.1109\/ANCS.2011.25"},{"issue":"08","key":"9_CR21","doi-asserted-by":"publisher","first-page":"1877","DOI":"10.1142\/S0129054111009094","volume":"22","author":"ANDREAS MALETTI","year":"2011","unstructured":"Maletti, A., Quernheim, D.: Optimal Hyper-Minimization. CoRR abs\/1104.3007 (2011)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"9_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1007\/978-3-642-03816-7_31","volume-title":"Mathematical Foundations of Computer Science 2009","author":"P Gawrychowski","year":"2009","unstructured":"Gawrychowski, P., Je\u017c, A.: Hyper-minimisation made efficient. In: Kr\u00e1lovi\u010d, R., Niwi\u0144ski, D. (eds.) MFCS 2009. LNCS, vol. 5734, pp. 356\u2013368. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03816-7_31"},{"key":"9_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-319-68167-2_5","volume-title":"Automated Technology for Verification and Analysis","author":"G Gange","year":"2017","unstructured":"Gange, G., Ganty, P., Stuckey, P.J.: Fixing the state budget: approximation of regular languages with small DFAs. In: D\u2019Souza, D., Narayan Kumar, K. (eds.) ATVA 2017. LNCS, vol. 10482, pp. 67\u201383. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-68167-2_5"},{"key":"9_CR24","unstructured":"Parker, A.J., Yancey, K.B., Yancey, M.P.: Regular Language Distance and Entropy. CoRR abs\/1602.07715 (2016)"},{"key":"9_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-44977-9_1","volume-title":"Implementation and Application of Automata","author":"M Mohri","year":"2003","unstructured":"Mohri, M.: Edit-distance of weighted automata. In: Champarnaud, J.-M., Maurel, D. (eds.) CIAA 2002. LNCS, vol. 2608, pp. 1\u201323. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-44977-9_1"},{"issue":"3","key":"9_CR26","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/j.tcs.2004.03.070","volume":"327","author":"A Malcher","year":"2004","unstructured":"Malcher, A.: Minimizing finite automata is computationally hard. Theor. Comput. Sci. 327(3), 375\u2013390 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR27","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E.: An $${N}.log {N}$$ N . l o g N Algorithm for Minimizing States in a Finite Automaton. Technical report (1971)","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"issue":"6","key":"9_CR28","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1137\/0216062","volume":"16","author":"R Paige","year":"1987","unstructured":"Paige, R., Tarjan, R.E.: Three partition refinement algorithms. SIAM J. Comput. 16(6), 973\u2013989 (1987)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9_CR29","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1145\/635499.635502","volume":"4","author":"D Bustan","year":"2003","unstructured":"Bustan, D., Grumberg, O.: Simulation-based minimization. ACM Trans. Comput. Log. 4(2), 181\u2013206 (2003)","journal-title":"ACM Trans. Comput. Log."},{"issue":"3","key":"9_CR30","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.tcs.2004.02.048","volume":"327","author":"J Champarnaud","year":"2004","unstructured":"Champarnaud, J., Coulon, F.: NFA reduction algorithms by means of regular inequalities. Theor. Comput. Sci. 327(3), 241\u2013253 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9_CR31","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1145\/2480359.2429079","volume":"48","author":"Richard Mayr","year":"2013","unstructured":"Mayr, R., Clemente, L.: Advanced automata minimization. In: Proceedings of POPL 2013, pp. 63\u201374. ACM (2013)","journal-title":"ACM SIGPLAN Notices"},{"key":"9_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/3-540-45694-5_10","volume-title":"CONCUR 2002 \u2014 Concurrency Theory","author":"K Etessami","year":"2002","unstructured":"Etessami, K.: A hierarchy of polynomial-time computable simulations for automata. In: Brim, L., K\u0159et\u00ednsk\u00fd, M., Ku\u010dera, A., Jan\u010dar, P. (eds.) CONCUR 2002. LNCS, vol. 2421, pp. 131\u2013144. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45694-5_10"},{"key":"9_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/978-3-642-22012-8_20","volume-title":"Automata, Languages and Programming","author":"L Clemente","year":"2011","unstructured":"Clemente, L.: B\u00fcchi automata can have smaller quotients. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6756, pp. 258\u2013270. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22012-8_20"},{"key":"9_CR34","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: Automatic verification of probabilistic concurrent finite state programs. In: Proceedings of SFCS 1985, pp. 327\u2013338. IEEE (1985)","DOI":"10.1109\/SFCS.1985.12"},{"key":"9_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-3-319-41528-4_2","volume-title":"Computer Aided Verification","author":"C Baier","year":"2016","unstructured":"Baier, C., Kiefer, S., Klein, J., Kl\u00fcppelholz, S., M\u00fcller, D., Worrell, J.: Markov chains and unambiguous B\u00fcchi automata. In: Chaudhuri, S., Farzan, A. (eds.) CAV 2016. LNCS, vol. 9779, pp. 23\u201342. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-41528-4_2"},{"key":"9_CR36","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/978-3-319-41528-4_2","volume-title":"Computer Aided Verification","author":"Christel Baier","year":"2016","unstructured":"Baier, C., Kiefer, S., Klein, J., Kl\u00fcppelholz, S., M\u00fcller, D., Worrell, J.: Markov Chains and Unambiguous B\u00fcchi Automata. CoRR abs\/1605.00950 (2016)"},{"key":"9_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/978-3-642-31606-7_23","volume-title":"Implementation and Application of Automata","author":"M Mohri","year":"2012","unstructured":"Mohri, M.: A disambiguation algorithm for finite automata and functional transducers. In: Moreira, N., Reis, R. (eds.) CIAA 2012. LNCS, vol. 7381, pp. 265\u2013277. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31606-7_23"},{"issue":"6","key":"9_CR38","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1137\/0222067","volume":"22","author":"T Jiang","year":"1993","unstructured":"Jiang, T., Ravikumar, B.: Minimal NFA problems are hard. SIAM J. Comput. 22(6), 1117\u20131141 (1993)","journal-title":"SIAM J. Comput."},{"key":"9_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/3-540-58473-0_144","volume-title":"Grammatical Inference and Applications","author":"RC Carrasco","year":"1994","unstructured":"Carrasco, R.C., Oncina, J.: Learning stochastic regular grammars by means of a state merging method. In: Carrasco, R.C., Oncina, J. (eds.) ICGI 1994. LNCS, vol. 862, pp. 139\u2013152. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/3-540-58473-0_144"},{"key":"9_CR40","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/978-3-540-30195-0_22","volume-title":"Grammatical Inference: Algorithms and Applications","author":"F Thollard","year":"2004","unstructured":"Thollard, F., Clark, A.: Learning stochastic deterministic regular languages. In: Paliouras, G., Sakakibara, Y. (eds.) ICGI 2004. LNCS (LNAI), vol. 3264, pp. 248\u2013259. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-30195-0_22"},{"key":"9_CR41","unstructured":"Mayr, R., et al.: Reduce: A Tool for Minimizing Nondeterministic Finite-Word and B\u00fcchi Automata. http:\/\/languageinclusion.org\/doku.php?id=tools . Accessed 30 Sept 2017"},{"issue":"2","key":"9_CR42","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/s10009-011-0205-y","volume":"14","author":"A Bouajjani","year":"2012","unstructured":"Bouajjani, A., Habermehl, P., Rogalewicz, A., Vojnar, T.: Abstract regular (Tree) model checking. STTT 14(2), 167\u2013191 (2012)","journal-title":"STTT"},{"key":"9_CR43","doi-asserted-by":"crossref","unstructured":"\u010ce\u0161ka, M., Havlena, V., Hol\u00edk, L., Leng\u00e1l, O., Vojnar, T.: Approximate Reduction of Finite Automata for High-Speed Network Intrusion Detection. Technical report. CoRR abs\/1710.08647 (2017)","DOI":"10.1007\/978-3-319-89963-3_9"},{"key":"9_CR44","doi-asserted-by":"publisher","unstructured":"\u010ce\u0161ka, M., Havlena, V., Hol\u00edk, L., Leng\u00e1l, O., Vojnar, T.: Approximate Reduction of Finite Automata for High-Speed Network Intrusion Detection. Figshare (2018). https:\/\/doi.org\/10.6084\/m9.figshare.5907055.v1","DOI":"10.6084\/m9.figshare.5907055.v1"},{"key":"9_CR45","doi-asserted-by":"publisher","unstructured":"Hartmanns, A., Wendler, P.: TACAS 2018 Artifact Evaluation VM. Figshare (2018). https:\/\/doi.org\/10.6084\/m9.figshare.5896615","DOI":"10.6084\/m9.figshare.5896615"}],"container-title":["Lecture Notes in Computer Science","Tools and Algorithms for the Construction and Analysis of Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-89963-3_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T17:29:12Z","timestamp":1751563752000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-89963-3_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319899626","9783319899633"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-89963-3_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"14 April 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TACAS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Tools and Algorithms for the Construction and Analysis of Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Thessaloniki","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tacas2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.etaps.org\/index.php\/2018\/tacas","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}