{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,6]],"date-time":"2025-11-06T20:05:05Z","timestamp":1762459505238,"version":"3.41.0"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319601335"},{"type":"electronic","value":"9783319601342"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","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":[[2017]]},"DOI":"10.1007\/978-3-319-60134-2_1","type":"book-chapter","created":{"date-parts":[[2017,5,27]],"date-time":"2017-05-27T12:53:09Z","timestamp":1495889589000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["On the Complexity of Determinizing Monitors"],"prefix":"10.1007","author":[{"given":"Luca","family":"Aceto","sequence":"first","affiliation":[]},{"given":"Antonis","family":"Achilleos","sequence":"additional","affiliation":[]},{"given":"Adrian","family":"Francalanza","sequence":"additional","affiliation":[]},{"given":"Anna","family":"Ing\u00f3lfsd\u00f3ttir","sequence":"additional","affiliation":[]},{"given":"S\u00e6var \u00d6rn","family":"Kjartansson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,28]]},"reference":[{"key":"1_CR1","unstructured":"Aceto, L., Achilleos, A., Francalanza, A., Ing\u00f3lfsd\u00f3ttir, A., Kjartansson, S.\u00d6.: Determinizing monitors for HML with recursion. arXiv preprint arXiv:1611.10212 (2016)"},{"key":"1_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/978-3-642-32759-9_9","volume-title":"FM 2012: Formal Methods","author":"H Barringer","year":"2012","unstructured":"Barringer, H., Falcone, Y., Havelund, K., Reger, G., Rydeheard, D.: Quantified event automata: towards expressive and efficient runtime monitors. In: Giannakopoulou, D., M\u00e9ry, D. (eds.) FM 2012. LNCS, vol. 7436, pp. 68\u201384. Springer, Heidelberg (2012). doi:10.1007\/978-3-642-32759-9_9"},{"issue":"3","key":"1_CR3","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/s10703-015-0226-3","volume":"46","author":"S Berkovich","year":"2015","unstructured":"Berkovich, S., Bonakdarpour, B., Fischmeister, S.: Runtime verification with minimal intrusion through parallelism. Formal Methods Syst. Des. 46(3), 317\u2013348 (2015)","journal-title":"Formal Methods Syst. Des."},{"issue":"1","key":"1_CR4","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1016\/j.jcss.2011.03.001","volume":"78","author":"H Bj\u00f6rklund","year":"2012","unstructured":"Bj\u00f6rklund, H., Martens, W.: The tractability frontier for NFA minimization. J. Comput. Syst. Sci. 78(1), 198\u2013210 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-642-38592-6_5","volume-title":"Formal Techniques for Distributed Systems","author":"L Bocchi","year":"2013","unstructured":"Bocchi, L., Chen, T.-C., Demangeon, R., Honda, K., Yoshida, N.: Monitoring networks through multiparty session types. In: Beyer, D., Boreale, M. (eds.) FMOODS\/FORTE -2013. LNCS, vol. 7892, pp. 50\u201365. Springer, Heidelberg (2013). doi:10.1007\/978-3-642-38592-6_5"},{"key":"1_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-319-33693-0_12","volume-title":"Integrated Formal Methods","author":"I Cassar","year":"2016","unstructured":"Cassar, I., Francalanza, A.: On implementing a monitor-oriented programming framework for actor systems. In: \u00c1brah\u00e1m, E., Huisman, M. (eds.) IFM 2016. LNCS, vol. 9681, pp. 176\u2013192. Springer, Cham (2016). doi:10.1007\/978-3-319-33693-0_12"},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(86)90142-8","volume":"47","author":"M Chrobak","year":"1986","unstructured":"Chrobak, M.: Finite automata and unary languages. Theor. Comput. Sci. 47, 149\u2013158 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"1_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/11513988_36","volume-title":"Computer Aided Verification","author":"M dAmorim","year":"2005","unstructured":"dAmorim, M., Ro\u015fu, G.: Efficient monitoring of $$\\omega $$-languages. In: Etessami, K., Rajamani, S.K. (eds.) CAV 2005. LNCS, vol. 3576, pp. 364\u2013378. Springer, Heidelberg (2005). doi:10.1007\/11513988_36"},{"key":"1_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1007\/978-3-319-11164-3_9","volume-title":"Runtime Verification","author":"P Fraigniaud","year":"2014","unstructured":"Fraigniaud, P., Rajsbaum, S., Travers, C.: On the number of opinions needed for fault-tolerant run-time monitoring in distributed systems. In: Bonakdarpour, B., Smolka, S.A. (eds.) RV 2014. LNCS, vol. 8734, pp. 92\u2013107. Springer, Cham (2014). doi:10.1007\/978-3-319-11164-3_9"},{"key":"1_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/978-3-662-49630-5_9","volume-title":"Foundations of Software Science and Computation Structures","author":"A Francalanza","year":"2016","unstructured":"Francalanza, A.: A theory of monitors. In: Jacobs, B., L\u00f6ding, C. (eds.) FoSSaCS 2016. LNCS, vol. 9634, pp. 145\u2013161. Springer, Heidelberg (2016). doi:10.1007\/978-3-662-49630-5_9"},{"key":"1_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/978-3-319-23820-3_5","volume-title":"Runtime Verification","author":"A Francalanza","year":"2015","unstructured":"Francalanza, A., Aceto, L., Ingolfsdottir, A.: On verifying hennessy-milner logic with recursion at runtime. In: Bartocci, E., Majumdar, R. (eds.) RV 2015. LNCS, vol. 9333, pp. 71\u201386. Springer, Cham (2015). doi:10.1007\/978-3-319-23820-3_5"},{"issue":"6","key":"1_CR12","doi-asserted-by":"publisher","first-page":"908","DOI":"10.1016\/j.jcss.2006.11.002","volume":"73","author":"G Gramlich","year":"2007","unstructured":"Gramlich, G., Schnitger, G.: Minimizing NFA\u2019s and regular expressions. J. Comput. Syst. Sci. 73(6), 908\u2013923 (2007)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-540-73208-2_21","volume-title":"Developments in Language Theory","author":"H Gruber","year":"2007","unstructured":"Gruber, H., Holzer, M.: Inapproximability of nondeterministic state and transition complexity assuming P $$\\ne $$ NP. In: Harju, T., Karhum\u00e4ki, J., Lepist\u00f6, A. (eds.) DLT 2007. LNCS, vol. 4588, pp. 205\u2013216. Springer, Heidelberg (2007). doi:10.1007\/978-3-540-73208-2_21"},{"issue":"6","key":"1_CR14","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."},{"issue":"3","key":"1_CR15","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/0304-3975(82)90125-6","volume":"27","author":"D Kozen","year":"1983","unstructured":"Kozen, D.: Results on the propositional $$\\mu $$-calculus. Theor. Comput. Sci. 27(3), 333\u2013354 (1983)","journal-title":"Theor. Comput. Sci."},{"issue":"2&3","key":"1_CR16","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1016\/0304-3975(90)90038-J","volume":"72","author":"KG Larsen","year":"1990","unstructured":"Larsen, K.G.: Proof systems for satisfiability in Hennessy-Milner logic with recursion. Theor. Comput. Sci. 72(2&3), 265\u2013288 (1990)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"1_CR17","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/j.jlap.2008.08.004","volume":"78","author":"M Leucker","year":"2009","unstructured":"Leucker, M., Schallhart, C.: A brief account of runtime verification. J. Logic Algebraic Program. 78(5), 293\u2013303 (2009)","journal-title":"J. Logic Algebraic Program."},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"Luo, Q., Ro\u015fu, G.: EnforceMOP: a runtime property enforcement system for multithreaded programs. In: International Symposium on Software Testing and Analysis, New York, USA, pp. 156\u2013166 (2013)","DOI":"10.1145\/2483760.2483766"},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: 12th Annual Symposium on Switching and Automata Theory (1971)","DOI":"10.1109\/SWAT.1971.11"},{"volume-title":"A Calculus of Communicating Systems","year":"1980","key":"1_CR20","unstructured":"Milner, R. (ed.): A Calculus of Communicating Systems. Springer, Heidelberg (1980)"},{"issue":"2","key":"1_CR21","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"MO Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3(2), 114\u2013125 (1959)","journal-title":"IBM J. Res. Dev."},{"key":"1_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1007\/3-540-58027-1_25","volume-title":"Mathematical Foundations of Programming Semantics","author":"A Rabinovich","year":"1994","unstructured":"Rabinovich, A.: A complete axiomatisation for trace congruence of finite state behaviors. In: Brookes, S., Main, M., Melton, A., Mislove, M., Schmidt, D. (eds.) MFPS 1993. LNCS, vol. 802, pp. 530\u2013543. Springer, Heidelberg (1994). doi:10.1007\/3-540-58027-1_25"},{"issue":"1","key":"1_CR23","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1145\/353323.353382","volume":"3","author":"FB Schneider","year":"2000","unstructured":"Schneider, F.B.: Enforceable security policies. ACM Trans. Inf. Syst. Secur. (TISSEC) 3(1), 30\u201350 (2000)","journal-title":"ACM Trans. Inf. Syst. Secur. (TISSEC)"},{"key":"1_CR24","doi-asserted-by":"crossref","unstructured":"Sen, K., Vardhan, A., Agha, G., Ro\u015fu, G.: Efficient decentralized monitoring of safety in distributed systems. In: International Conference on Software Engineering, pp. 418\u2013427 (2004)","DOI":"10.1109\/ICSE.2004.1317464"},{"key":"1_CR25","unstructured":"Sipser, M.: Introduction to the Theory of Computation, Computer Science. PWS Publishing Company (1997)"},{"issue":"1","key":"1_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1994.1092","volume":"115","author":"MY Vardi","year":"1994","unstructured":"Vardi, M.Y., Wolper, P.: Reasoning about infinite computations. Inf. Comput. 115(1), 1\u201337 (1994)","journal-title":"Inf. Comput."},{"key":"1_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1007\/978-3-319-46982-9_24","volume-title":"Runtime Verification","author":"Y Yamagata","year":"2016","unstructured":"Yamagata, Y., Artho, C., Hagiya, M., Inoue, J., Ma, L., Tanabe, Y., Yamamoto, M.: Runtime monitoring for concurrent systems. In: Falcone, Y., S\u00e1nchez, C. (eds.) RV 2016. LNCS, vol. 10012, pp. 386\u2013403. Springer, Cham (2016). doi:10.1007\/978-3-319-46982-9_24"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-60134-2_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:40:26Z","timestamp":1750279226000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-60134-2_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319601335","9783319601342"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-60134-2_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"28 May 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Implementation and Application of Automata","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Marne-la-Vall\u00e9e","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 June 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 June 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wia2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/ciaa17.univ-mlv.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}