{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,27]],"date-time":"2026-05-27T21:01:44Z","timestamp":1779915704738,"version":"3.53.1"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T00:00:00Z","timestamp":1558656000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T00:00:00Z","timestamp":1558656000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Softw Tools Technol Transfer"],"published-print":{"date-parts":[[2020,10]]},"DOI":"10.1007\/s10009-019-00520-8","type":"journal-article","created":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T12:03:22Z","timestamp":1558699402000},"page":"523-539","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Approximate reduction of finite automata for high-speed network intrusion detection"],"prefix":"10.1007","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0300-9727","authenticated-orcid":false,"given":"Milan","family":"\u010ce\u0161ka","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vojt\u011bch","family":"Havlena","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6957-1651","authenticated-orcid":false,"given":"Luk\u00e1\u0161","family":"Hol\u00edk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3038-5875","authenticated-orcid":false,"given":"Ond\u0159ej","family":"Leng\u00e1l","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2746-8792","authenticated-orcid":false,"given":"Tom\u00e1\u0161","family":"Vojnar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,5,24]]},"reference":[{"issue":"2","key":"520_CR1","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","volume":"75","author":"D Angluin","year":"1987","unstructured":"Angluin, D.: Learning regular sets from queries and counterexamples. Inf. Comput. 75(2), 87\u2013106 (1987). \nhttps:\/\/doi.org\/10.1016\/0890-5401(87)90052-6","journal-title":"Inf. Comput."},{"key":"520_CR2","doi-asserted-by":"crossref","unstructured":"Baier, C., Kiefer, S., Klein, J., Kl\u00fcppelholz, S., M\u00fcller, D., Worrell, J.: Markov chains and unambiguous B\u00fcchi automata. In: CAV\u201916, pp. 23\u201342. Springer (2016)","DOI":"10.1007\/978-3-319-41528-4_2"},{"key":"520_CR3","doi-asserted-by":"crossref","unstructured":"Becchi, M., Crowley, P.: A hybrid finite automaton for practical deep packet inspection. In: CoNEXT\u201907, p.\u00a01. ACM (2007)","DOI":"10.1145\/1364654.1364656"},{"key":"520_CR4","doi-asserted-by":"crossref","unstructured":"Becchi, M., Crowley, P.: An improved algorithm to accelerate regular expression evaluation. In: ANCS\u201907, pp. 145\u2013154. ACM (2007)","DOI":"10.1145\/1323548.1323573"},{"key":"520_CR5","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 the 5th ACM\/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS \u201909, pp. 30\u201339. ACM (2009)","DOI":"10.1145\/1882486.1882495"},{"key":"520_CR6","unstructured":"Benedikt, M., Lenhardt, R., Worrell, J.: Model checking Markov chains against unambiguous B\u00fcchi automata. CoRR \narXiv:1405.4560v2\n\n (2016)"},{"issue":"2","key":"520_CR7","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":"520_CR8","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: ISCA\u201906, pp. 191\u2013202. IEEE Computer Society (2006)","DOI":"10.1145\/1150019.1136500"},{"issue":"2","key":"520_CR9","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."},{"key":"520_CR10","doi-asserted-by":"crossref","unstructured":"Carrasco, R.C., Oncina, J.: Learning stochastic regular grammars by means of a state merging method. In: Proceedings of the Second International Colloquium on Grammatical Inference and Applications, ICGI \u201994, pp. 139\u2013152. Springer (1994)","DOI":"10.1007\/3-540-58473-0_144"},{"key":"520_CR11","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. In: Figshare (2018). \nhttps:\/\/doi.org\/10.6084\/m9.figshare.5907055","DOI":"10.6084\/m9.figshare.5907055"},{"key":"520_CR12","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. In: Proceedings of TACAS\u201918, LNCS, vol. 10806. Springer (2018)","DOI":"10.1007\/s10009-019-00520-8"},{"issue":"3","key":"520_CR13","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."},{"key":"520_CR14","doi-asserted-by":"crossref","unstructured":"Clark, C.R., Schimmel, D.E.: Efficient reconfigurable logic circuits for matching complex network intrusion detection patterns. In: FPL\u201903, Lecture Notes in Computer Science, vol. 2778, pp. 956\u2013959. Springer (2003)","DOI":"10.1007\/978-3-540-45234-8_94"},{"key":"520_CR15","doi-asserted-by":"crossref","unstructured":"Clemente, L.: B\u00fcchi automata can have smaller quotients. In: ICALP\u201911, Lecture Notes in Computer Science, vol. 6756, pp. 258\u2013270. Springer (2011)","DOI":"10.1007\/978-3-642-22012-8_20"},{"key":"520_CR16","doi-asserted-by":"publisher","unstructured":"Csanky, L.: Fast parallel matrix inversion algorithms. In: 16th Annual Symposium on Foundations of Computer Science, pp. 11\u201312 (1975). \nhttps:\/\/doi.org\/10.1109\/SFCS.1975.14","DOI":"10.1109\/SFCS.1975.14"},{"key":"520_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00234-2","volume-title":"Encyclopedia of Distances","author":"MM Deza","year":"2009","unstructured":"Deza, M.M., Deza, E.: Encyclopedia of Distances. Springer, Berlin (2009)"},{"key":"520_CR18","doi-asserted-by":"crossref","unstructured":"Etessami, K.: A hierarchy of polynomial-time computable simulations for automata. In: CONCUR 2002\u2014Concurrency Theory, 13th International Conference, Brno, Czech Republic, August 20-23, 2002, Proceedings, Lecture Notes in Computer Science, vol. 2421, pp. 131\u2013144. Springer (2002)","DOI":"10.1007\/3-540-45694-5_10"},{"key":"520_CR19","doi-asserted-by":"publisher","unstructured":"Fortune, S., Wyllie, J.: Parallelism in random access machines. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC \u201978, pp. 114\u2013118. ACM, New York, NY, USA (1978). \nhttps:\/\/doi.org\/10.1145\/800133.804339","DOI":"10.1145\/800133.804339"},{"key":"520_CR20","doi-asserted-by":"crossref","unstructured":"Gange, G., Ganty, P., Stuckey, P.J.: Fixing the state budget: approximation of regular languages with small DFAs. In: ATVA\u201917, Lecture Notes in Computer Science, vol. 10482, pp. 67\u201383. Springer (2017)","DOI":"10.1007\/978-3-319-68167-2_5"},{"key":"520_CR21","doi-asserted-by":"crossref","unstructured":"Gawrychowski, P., Jez, A.: Hyper-minimisation made efficient. In: MFCS\u201909, Lecture Notes in Computer Science, vol. 5734, pp. 356\u2013368. Springer (2009)","DOI":"10.1007\/978-3-642-03816-7_31"},{"key":"520_CR22","doi-asserted-by":"publisher","unstructured":"Hartmanns, A., Wendler, P.: TACAS 2018 artifact evaluation VM. In: Figshare (2018). \nhttps:\/\/doi.org\/10.6084\/m9.figshare.5896615","DOI":"10.6084\/m9.figshare.5896615"},{"key":"520_CR23","doi-asserted-by":"publisher","DOI":"10.1201\/b16113","volume-title":"Handbook of Linear Algebra","author":"L Hogben","year":"2013","unstructured":"Hogben, L.: Handbook of Linear Algebra, 2nd edn. CRC Press, Boca Raton (2013)","edition":"2"},{"key":"520_CR24","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E.: An N log N algorithm for minimizing states in a finite automaton. Technical report (1971)","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"key":"520_CR25","unstructured":"Hutchings, B.L., Franklin, R., Carver, D.: Assisting network intrusion detection with reconfigurable hardware. In: FCCM\u201902, pp. 111\u2013120. IEEE Computer Society (2002)"},{"issue":"6","key":"520_CR26","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":"520_CR27","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: 2009 12th Euromicro Conference on Digital System Design, Architectures, Methods and Tools, pp. 823\u2013829 (2009)","DOI":"10.1109\/DSD.2009.149"},{"key":"520_CR28","doi-asserted-by":"crossref","unstructured":"Ko\u0159enek, J., Kobiersk\u00fd, P.: Intrusion detection system intended for multigigabit networks. In: 2007 IEEE Design and Diagnostics of Electronic Circuits and Systems, pp. 1\u20134 (2007)","DOI":"10.1109\/DDECS.2007.4295313"},{"key":"520_CR29","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: ANCS\u201907, pp. 155\u2013164. ACM (2007)","DOI":"10.1145\/1323548.1323574"},{"key":"520_CR30","doi-asserted-by":"crossref","unstructured":"Kumar, S., Dharmapurikar, S., Yu, F., Crowley, P., Turner, J.S.: Algorithms to accelerate multiple regular expressions matching for deep packet inspection. In: SIGCOMM\u201906, pp. 339\u2013350. ACM (2006)","DOI":"10.1145\/1151659.1159952"},{"key":"520_CR31","doi-asserted-by":"crossref","unstructured":"Kumar, S., Turner, J.S., Williams, J.: Advanced algorithms for fast and scalable deep packet inspection. In: ANCS\u201906, pp. 81\u201392. ACM (2006)","DOI":"10.1145\/1185347.1185359"},{"issue":"2","key":"520_CR32","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":"520_CR33","doi-asserted-by":"crossref","unstructured":"Luchaup, D., De\u00a0Carli, L., Jha, S., Bach, E.: Deep packet inspection with DFA-trees and parametrized language overapproximation. In: INFOCOM\u201914, pp. 531\u2013539. IEEE (2014)","DOI":"10.1109\/INFOCOM.2014.6847977"},{"issue":"3","key":"520_CR34","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":"520_CR35","doi-asserted-by":"crossref","unstructured":"Maletti, A., Quernheim, D.: Optimal hyper-minimization. CoRR \narXiv:1104.3007\n\n (2011)","DOI":"10.1142\/S0129054111009094"},{"key":"520_CR36","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, D., Ko\u0159enek, J., Pu\u0161, V.: High-speed regular expression matching with pipelined automata. In: 2016 International Conference on Field-Programmable Technology (FPT), pp. 93\u2013100 (2016)","DOI":"10.1109\/FPT.2016.7929431"},{"key":"520_CR37","doi-asserted-by":"crossref","unstructured":"Mayr, R., Clemente, L.: Advanced automata minimization. In: POPL\u201913, Transactions on Computer Logic, pp. 63\u201374. ACM (2013)","DOI":"10.1145\/2480359.2429079"},{"key":"520_CR38","unstructured":"Mayr, R., et\u00a0al.: Reduce: A tool for minimizing nondeterministic finite-word and B\u00fcchi automata. \nhttp:\/\/languageinclusion.org\/doku.php?id=tools\n\n (2017). Accessed 30 Sept 2017"},{"key":"520_CR39","doi-asserted-by":"crossref","unstructured":"Mitra, A., Najjar, W.A., Bhuyan, L.N.: Compiling PCRE to FPGA for accelerating SNORT IDS. In: ANCS\u201907, pp. 127\u2013136. ACM (2007)","DOI":"10.1145\/1323548.1323571"},{"key":"520_CR40","doi-asserted-by":"crossref","unstructured":"Mohri, M.: A disambiguation algorithm for finite automata and functional transducers. In: CIAA\u201912, pp. 265\u2013277. Springer (2012)","DOI":"10.1007\/978-3-642-31606-7_23"},{"key":"520_CR41","doi-asserted-by":"crossref","unstructured":"Mohri, M.: Edit-distance of weighted automata. In: CIAA\u201902, Lecture Notes in Computer Science, vol. 2608, pp. 1\u201323. Springer (2002)","DOI":"10.1007\/3-540-44977-9_1"},{"issue":"6","key":"520_CR42","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."},{"key":"520_CR43","unstructured":"Papadimitriou, C.M.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"520_CR44","unstructured":"Parker, A.J., Yancey, K.B., Yancey, M.P.: Regular language distance and entropy. CoRR \narXiv:1602.07715\n\n (2016)"},{"key":"520_CR45","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: Symposium On Architecture For Networking And Communications Systems pp. 95\u201396 (2011)","DOI":"10.1109\/ANCS.2011.25"},{"key":"520_CR46","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/S0019-9958(61)80020-X","volume":"4","author":"M Sh\u00fctzenberger","year":"1961","unstructured":"Sh\u00fctzenberger, M.: On the definition of a family of automata. Inf. Control 4, 245\u2013270 (1961)","journal-title":"Inf. Control"},{"key":"520_CR47","unstructured":"Sidhu, R.P.S., Prasanna, V.K.: Fast regular expression matching using FPGAs. In: FCCM\u201901, pp. 227\u2013238. IEEE Computer Society (2001)"},{"issue":"4","key":"520_CR48","doi-asserted-by":"publisher","first-page":"1482","DOI":"10.1007\/BF02104747","volume":"29","author":"VI Solodovnikov","year":"1985","unstructured":"Solodovnikov, V.I.: Upper bounds on the complexity of solving systems of linear equations. J. Sov. Math. 29(4), 1482\u20131501 (1985)","journal-title":"J. Sov. Math."},{"key":"520_CR49","doi-asserted-by":"crossref","unstructured":"Tan, L., Sherwood, T.: A high throughput string matching architecture for intrusion detection and prevention. In: ISCA\u201905, pp. 112\u2013122. IEEE Computer Society (2005)","DOI":"10.1145\/1080695.1069981"},{"key":"520_CR50","unstructured":"The Snort Team: Snort. \nhttp:\/\/www.snort.org\n\n. Accessed 30 Sept 2017"},{"key":"520_CR51","doi-asserted-by":"publisher","unstructured":"Thollard, F., Clark, A.: Learning stochastic deterministic regular languages. In: G.\u00a0Paliouras, Y.\u00a0Sakakibara (eds.) Grammatical Inference: Algorithms and Applications: 7th International Colloquium, ICGI 2004, Athens, Greece, October 11\u201313, 2004. Proceedings, pp. 248\u2013259. Springer Berlin Heidelberg, Berlin, Heidelberg (2004). \nhttps:\/\/doi.org\/10.1007\/978-3-540-30195-0_22","DOI":"10.1007\/978-3-540-30195-0_22"},{"key":"520_CR52","unstructured":"Vardi, M.Y.: Automatic verification of probabilistic concurrent finite state programs. In: SFCS \u201985, pp. 327\u2013338. IEEE"},{"key":"520_CR53","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: ANCS\u201906, pp. 93\u2013102. ACM (2006)","DOI":"10.1145\/1185347.1185360"}],"container-title":["International Journal on Software Tools for Technology Transfer"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10009-019-00520-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10009-019-00520-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10009-019-00520-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,28]],"date-time":"2020-09-28T07:10:20Z","timestamp":1601277020000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10009-019-00520-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,24]]},"references-count":53,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["520"],"URL":"https:\/\/doi.org\/10.1007\/s10009-019-00520-8","relation":{},"ISSN":["1433-2779","1433-2787"],"issn-type":[{"value":"1433-2779","type":"print"},{"value":"1433-2787","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,24]]},"assertion":[{"value":"24 May 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}