{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T08:45:25Z","timestamp":1780994725445,"version":"3.54.1"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030341749","type":"print"},{"value":"9783030341756","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-34175-6_24","type":"book-chapter","created":{"date-parts":[[2019,11,18]],"date-time":"2019-11-18T00:01:29Z","timestamp":1574035289000},"page":"468-489","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Succinct Determinisation of Counting Automata via Sphere Construction"],"prefix":"10.1007","author":[{"given":"Luk\u00e1\u0161","family":"Hol\u00edk","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ond\u0159ej","family":"Leng\u00e1l","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Olli","family":"Saarikivi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lenka","family":"Turo\u0148ov\u00e1","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Margus","family":"Veanes","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tom\u00e1\u0161","family":"Vojnar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,11,18]]},"reference":[{"key":"24_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-3-540-85361-9_9","volume-title":"CONCUR 2008 - Concurrency Theory","author":"PA Abdulla","year":"2008","unstructured":"Abdulla, P.A., Krcal, P., Yi, W.: R-automata. In: van Breugel, F., Chechik, M. (eds.) CONCUR 2008. LNCS, vol. 5201, pp. 67\u201381. Springer, Heidelberg (2008). \nhttps:\/\/doi.org\/10.1007\/978-3-540-85361-9_9"},{"issue":"5","key":"24_CR2","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/s10009-008-0064-3","volume":"10","author":"S\u00e9bastien Bardin","year":"2008","unstructured":"Bardin, S., Finkel, A., Leroux, J., Petrucci, L.: FAST: acceleration from theory to practice. STTT 10(5) (2008)","journal-title":"International Journal on Software Tools for Technology Transfer"},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"B\u00f6rklund, E., Martens, W., Timm, T.: Efficient incremental evaluation of succinct regular expressions. In: Proceedings of CIKM 2015, ACM (2015)","DOI":"10.1145\/2806416.2806434"},{"key":"24_CR4","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/j.ic.2014.12.001","volume":"241","author":"H Chen","year":"2015","unstructured":"Chen, H., Lu, P.: Checking determinism of regular expressions with counting. Inf. Comput. 241, 302\u2013320 (2015)","journal-title":"Inf. Comput."},{"key":"24_CR5","doi-asserted-by":"crossref","unstructured":"Cheng, K., Krishnakumar, A.S.: Automatic functional test generation using the extended finite state machine model. In: Proceedings of DAC 1993, ACM Press (1993)","DOI":"10.1145\/157485.164585"},{"key":"24_CR6","doi-asserted-by":"crossref","unstructured":"D\u2019Antoni, L., Veanes, M.: Minimization of symbolic automata. In: Proceedings of POPL 2014, ACM (2014)","DOI":"10.1145\/2535838.2535849"},{"key":"24_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/3-540-55179-4_25","volume-title":"Computer Aided Verification","author":"DL Dill","year":"1992","unstructured":"Dill, D.L., Hu, A.J., Wong-Toi, H.: Checking for language inclusion using simulation preorders. In: Larsen, K.G., Skou, A. (eds.) CAV 1991. LNCS, vol. 575, pp. 255\u2013265. Springer, Heidelberg (1992). \nhttps:\/\/doi.org\/10.1007\/3-540-55179-4_25"},{"key":"24_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/11965893_19","volume-title":"Database Theory \u2013 ICDT 2007","author":"W Gelade","year":"2006","unstructured":"Gelade, W., Martens, W., Neven, F.: Optimizing schema languages for XML: numerical constraints and interleaving. In: Schwentick, T., Suciu, D. (eds.) ICDT 2007. LNCS, vol. 4353, pp. 269\u2013283. Springer, Heidelberg (2006). \nhttps:\/\/doi.org\/10.1007\/11965893_19"},{"key":"24_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-642-03816-7_32","volume-title":"Mathematical Foundations of Computer Science 2009","author":"W Gelade","year":"2009","unstructured":"Gelade, W., Gyssens, M., Martens, W.: Regular expressions with counting: weak versus strong determinism. In: Kr\u00e1lovi\u010d, R., Niwi\u0144ski, D. (eds.) MFCS 2009. LNCS, vol. 5734, pp. 369\u2013381. Springer, Heidelberg (2009). \nhttps:\/\/doi.org\/10.1007\/978-3-642-03816-7_32"},{"key":"24_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/978-3-540-70844-5_17","volume-title":"Implementation and Applications of Automata","author":"R Glabbeek van","year":"2008","unstructured":"van Glabbeek, R., Ploeger, B.: Five Determinisation algorithms. In: Ibarra, O.H., Ravikumar, B. (eds.) CIAA 2008. LNCS, vol. 5148, pp. 161\u2013170. Springer, Heidelberg (2008). \nhttps:\/\/doi.org\/10.1007\/978-3-540-70844-5_17"},{"key":"24_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/978-3-642-39799-8_2","volume-title":"Computer Aided Verification","author":"M Heizmann","year":"2013","unstructured":"Heizmann, M., Hoenicke, J., Podelski, A.: Software model checking for people who love automata. In: Sharygina, N., Veith, H. (eds.) CAV 2013. LNCS, vol. 8044, pp. 36\u201352. Springer, Heidelberg (2013). \nhttps:\/\/doi.org\/10.1007\/978-3-642-39799-8_2"},{"key":"24_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/3-540-60630-0_5","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"JG Henriksen","year":"1995","unstructured":"Henriksen, J.G., et al.: Mona: monadic second-order logic in practice. In: Brinksma, E., Cleaveland, W.R., Larsen, K.G., Margaria, T., Steffen, B. (eds.) TACAS 1995. LNCS, vol. 1019, pp. 89\u2013110. Springer, Heidelberg (1995). \nhttps:\/\/doi.org\/10.1007\/3-540-60630-0_5"},{"key":"24_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/978-3-642-03466-4_15","volume-title":"Theoretical Aspects of Computing - ICTAC 2009","author":"D Hovland","year":"2009","unstructured":"Hovland, D.: Regular expressions with numerical constraints and automata with counters. In: Leucker, M., Morgan, C. (eds.) ICTAC 2009. LNCS, vol. 5684, pp. 231\u2013245. Springer, Heidelberg (2009). \nhttps:\/\/doi.org\/10.1007\/978-3-642-03466-4_15"},{"key":"24_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1007\/978-3-642-28332-1_27","volume-title":"Language and Automata Theory and Applications","author":"D Hovland","year":"2012","unstructured":"Hovland, D.: The membership problem for regular expressions with unordered concatenation and numerical constraints. In: Dediu, A.-H., Mart\u00edn-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 313\u2013324. Springer, Heidelberg (2012). \nhttps:\/\/doi.org\/10.1007\/978-3-642-28332-1_27"},{"issue":"6","key":"24_CR15","doi-asserted-by":"publisher","first-page":"890","DOI":"10.1016\/j.ic.2006.12.003","volume":"205","author":"P Kilpel\u00e4inen","year":"2007","unstructured":"Kilpel\u00e4inen, P., Tuhkanen, R.: One-unambiguity of regular expressions with numeric occurrence indicators. Inf. Comput. 205(6), 890\u2013916 (2007)","journal-title":"Inf. Comput."},{"key":"24_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/978-3-642-28756-5_7","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"O Leng\u00e1l","year":"2012","unstructured":"Leng\u00e1l, O., \u0160im\u00e1\u010dek, J., Vojnar, T.: VATA: a library for efficient manipulation of non-deterministic tree automata. In: Flanagan, C., K\u00f6nig, B. (eds.) TACAS 2012. LNCS, vol. 7214, pp. 79\u201394. Springer, Heidelberg (2012). \nhttps:\/\/doi.org\/10.1007\/978-3-642-28756-5_7"},{"key":"24_CR17","unstructured":"Roesch, M., et al.: Snort: A Network Intrusion Detection and Prevention System. \nhttp:\/\/www.snort.org"},{"key":"24_CR18","unstructured":"Microsoft Automata Library: Automata and Transducer Library for .NET. \nhttps:\/\/github.com\/AutomataDotNet\/Automata"},{"key":"24_CR19","unstructured":"OWASP Foundation and Checkmarx: Regular Expression Denial of Service: ReDoS (2017)"},{"key":"24_CR20","unstructured":"RegExLib.com: The Internet\u2019s First Regular Expression Library. \nhttp:\/\/regexlib.com\/"},{"key":"24_CR21","unstructured":"Sommer, R., et al.: The Bro Network Security Monitor. \nhttp:\/\/www.bro.org"},{"key":"24_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/BFb0028752","volume-title":"Computer Aided Verification","author":"TR Shiple","year":"1998","unstructured":"Shiple, T.R., Kukula, J.H., Ranjan, R.K.: A comparison of Presburger engines for EFSM reachability. In: Hu, A.J., Vardi, M.Y. (eds.) CAV 1998. LNCS, vol. 1427, pp. 280\u2013292. Springer, Heidelberg (1998). \nhttps:\/\/doi.org\/10.1007\/BFb0028752"},{"key":"24_CR23","doi-asserted-by":"crossref","unstructured":"Smith, R., Estan, C., Jha, S.: XFA: faster signature matching with extended automata. In: Proceedings of SSP 2008, IEEE (2008)","DOI":"10.1109\/SP.2008.14"},{"key":"24_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/978-3-540-89862-7_15","volume-title":"Information Systems Security","author":"R Smith","year":"2008","unstructured":"Smith, R., Estan, C., Jha, S., Siahaan, I.: Fast signature matching using extended finite automaton (XFA). In: Sekar, R., Pujari, A.K. (eds.) ICISS 2008. LNCS, vol. 5352, pp. 158\u2013172. Springer, Heidelberg (2008). \nhttps:\/\/doi.org\/10.1007\/978-3-540-89862-7_15"},{"key":"24_CR25","unstructured":"Sperberg-McQueen, M.: Notes on Finite State Automata with Counters. \nhttps:\/\/www.w3.org\/XML\/2004\/05\/msm-cfa.html\n\n. Accessed 08 Aug 2018"},{"key":"24_CR26","unstructured":"The Sagan Team: The Sagan Log Analysis Engine. \nhttps:\/\/quadrantsec.com\/sagan_log_analysis_engine\/"},{"issue":"6","key":"24_CR27","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1145\/363347.363387","volume":"11","author":"K Thompson","year":"1968","unstructured":"Thompson, K.: Programming techniques: regular expression search algorithm. Commun. ACM 11(6), 419\u2013422 (1968)","journal-title":"Commun. ACM"},{"key":"24_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/978-3-319-89963-3_9","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"M \u010ce\u0161ka","year":"2018","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: Beyer, D., Huisman, M. (eds.) TACAS 2018. LNCS, vol. 10806, pp. 155\u2013175. Springer, Cham (2018). \nhttps:\/\/doi.org\/10.1007\/978-3-319-89963-3_9"},{"key":"24_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/978-3-642-15512-3_4","volume-title":"Recent Advances in Intrusion Detection","author":"L Yang","year":"2010","unstructured":"Yang, L., Karim, R., Ganapathy, V., Smith, R.: Improving NFA-based signature matching using ordered binary decision diagrams. In: Jha, S., Sommer, R., Kreibich, C. (eds.) RAID 2010. LNCS, vol. 6307, pp. 58\u201378. Springer, Heidelberg (2010). \nhttps:\/\/doi.org\/10.1007\/978-3-642-15512-3_4"}],"container-title":["Lecture Notes in Computer Science","Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-34175-6_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,11,18]],"date-time":"2019-11-18T00:07:58Z","timestamp":1574035678000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-34175-6_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030341749","9783030341756"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-34175-6_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"18 November 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"APLAS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Asian Symposium on Programming Languages and Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Nusa Dua, Bali","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Indonesia","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 December 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 December 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"aplas2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/conf.researchr.org\/home\/aplas-2019","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}