{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,30]],"date-time":"2026-01-30T05:18:41Z","timestamp":1769750321097,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662496732","type":"print"},{"value":"9783662496749","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-662-49674-9_54","type":"book-chapter","created":{"date-parts":[[2016,4,8]],"date-time":"2016-04-08T18:49:00Z","timestamp":1460141340000},"page":"868-884","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Runtime Monitoring with Union-Find Structures"],"prefix":"10.1007","author":[{"given":"Normann","family":"Decker","sequence":"first","affiliation":[]},{"given":"Jannis","family":"Harder","sequence":"additional","affiliation":[]},{"given":"Torben","family":"Scheffel","sequence":"additional","affiliation":[]},{"given":"Malte","family":"Schmitz","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Thoma","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,4,9]]},"reference":[{"key":"54_CR1","doi-asserted-by":"crossref","unstructured":"Allan, C., Avgustinov, P., Christensen, A.S., Hendren, L.J., Kuzins, S., Lhot\u00e1k, O., de Moor, O., Sereni, D., Sittampalam, G., Tibble, J.: Adding trace matching with free variables to AspectJ. In: Proceedings of Object-Oriented Programming, Systems, Languages, and Applications 2005, pp. 345\u2013364. ACM (2005)","DOI":"10.1145\/1103845.1094839"},{"key":"54_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1007\/11523468_7","volume-title":"Automata, Languages and Programming","author":"S Alstrup","year":"2005","unstructured":"Alstrup, S., Li G\u00f8rtz, I., Rauhe, T., Thorup, M., Zwick, U.: Union-find with constant time deletions. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 78\u201389. Springer, Heidelberg (2005)"},{"issue":"1","key":"54_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2636922","volume":"11","author":"S Alstrup","year":"2014","unstructured":"Alstrup, S., Thorup, M., G\u00f8rtz, I.L., Rauhe, T., Zwick, U.: Union-find with constant time deletions. ACM Trans. Algorithms 11(1), 1\u201328 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"54_CR4","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)"},{"key":"54_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/978-3-540-24622-0_5","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"H Barringer","year":"2004","unstructured":"Barringer, H., Goldberg, A., Havelund, K., Sen, K.: Rule-based runtime verification. In: Steffen, B., Levi, G. (eds.) VMCAI 2004. LNCS, vol. 2937, pp. 44\u201357. Springer, Heidelberg (2004)"},{"key":"54_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/978-3-642-21437-0_7","volume-title":"FM 2011: Formal Methods","author":"H Barringer","year":"2011","unstructured":"Barringer, H., Havelund, K.: TraceContract: a scala DSL for trace analysis. In: Butler, M., Schulte, W. (eds.) FM 2011. LNCS, vol. 6664, pp. 57\u201372. Springer, Heidelberg (2011)"},{"key":"54_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-540-77395-5_10","volume-title":"Runtime Verification","author":"H Barringer","year":"2007","unstructured":"Barringer, H., Rydeheard, D.E., Havelund, K.: Rule systems for run-time monitoring: from Eagle to RuleR. In: Sokolsky, O., Ta\u015f\u0131ran, S. (eds.) RV 2007. LNCS, vol. 4839, pp. 111\u2013125. Springer, Heidelberg (2007)"},{"key":"54_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-14295-6_1","volume-title":"Computer Aided Verification","author":"D Basin","year":"2010","unstructured":"Basin, D., Klaedtke, F., M\u00fcller, S.: Policy monitoring in first-order temporal logic. In: Touili, T., Cook, B., Jackson, P. (eds.) CAV 2010. LNCS, vol. 6174, pp. 1\u201318. Springer, Heidelberg (2010)"},{"issue":"2","key":"54_CR9","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1145\/2699444","volume":"62","author":"DA Basin","year":"2015","unstructured":"Basin, D.A., Klaedtke, F., M\u00fcller, S., Zalinescu, E.: Monitoring metric first-order temporal properties. J. ACM 62(2), 15 (2015)","journal-title":"J. ACM"},{"key":"54_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-3-642-40787-1_4","volume-title":"Runtime Verification","author":"A Bauer","year":"2013","unstructured":"Bauer, A., K\u00fcster, J.-C., Vegliach, G.: From propositional to first-order monitoring. In: Legay, A., Bensalem, S. (eds.) RV 2013. LNCS, vol. 8174, pp. 59\u201375. Springer, Heidelberg (2013)"},{"key":"54_CR11","doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M., Lasota, S.: An extension of data automata that captures XPath. Logical Methods Comput. Sci. 8(1) (2012)","DOI":"10.2168\/LMCS-8(1:5)2012"},{"key":"54_CR12","doi-asserted-by":"crossref","unstructured":"D\u2019Angelo, B., Sankaranarayanan, S., S\u00e1nchez, C., Robinson, W., Finkbeiner, B., Sipma, H.B., Mehrotra, S., Manna, Z.: LOLA: runtime monitoring of synchronous systems. In: Proceedings of Temporal Representation and Reasoning 2005, pp. 166\u2013174. IEEE Computer Society (2005)","DOI":"10.1109\/TIME.2005.26"},{"key":"54_CR13","doi-asserted-by":"crossref","unstructured":"Decker, N., Leucker, M., Thoma, D.: Monitoring modulo theories. Int. J. Softw. Tools Technol. Transfer 1\u201321 (2015)","DOI":"10.1007\/s10009-015-0380-3"},{"key":"54_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/978-3-319-23820-3_27","volume-title":"Runtime Verification","author":"Y Falcone","year":"2015","unstructured":"Falcone, Y., Nickovic, D., Reger, G., Thoma, D.: Second international competition on runtime verification. In: Bartocci, E., et al. (eds.) RV 2015. LNCS, vol. 9333, pp. 405\u2013422. Springer, Heidelberg (2015). doi: 10.1007\/978-3-319-23820-3_27"},{"issue":"2","key":"54_CR15","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s10009-014-0309-2","volume":"17","author":"K Havelund","year":"2015","unstructured":"Havelund, K.: Rule-based runtime verification revisited. STTT 17(2), 143\u2013170 (2015)","journal-title":"STTT"},{"key":"54_CR16","unstructured":"Kaplan, H., Shafrir, N., Tarjan, R.E.: Union-find with deletions. In: Proceedings of Symposium on Discrete Algorithms 2002, pp. 19\u201328. ACM\/SIAM (2002)"},{"issue":"3","key":"54_CR17","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s10009-011-0198-6","volume":"14","author":"PO Meredith","year":"2012","unstructured":"Meredith, P.O., Jin, D., Griffith, D., Chen, F., Rosu, G.: An overview of the MOP runtime verification framework. STTT 14(3), 249\u2013289 (2012)","journal-title":"STTT"},{"key":"54_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1007\/978-3-662-46681-0_55","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"G Reger","year":"2015","unstructured":"Reger, G., Cruz, H.C., Rydeheard, D.: MarQ: monitoring at runtime with QEA. In: Baier, C., Tinelli, C. (eds.) TACAS 2015. LNCS, vol. 9035, pp. 596\u2013610. Springer, Heidelberg (2015)"},{"issue":"1","key":"54_CR19","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2168\/LMCS-8(1:9)2012","volume":"8","author":"G Rosu","year":"2012","unstructured":"Rosu, G., Chen, F.: Semantics and algorithms for parametric monitoring. Logical Methods Comput. Sci. 8(1), 1\u201347 (2012)","journal-title":"Logical Methods Comput. Sci."},{"issue":"4","key":"54_CR20","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.entcs.2006.02.007","volume":"144","author":"V Stolz","year":"2006","unstructured":"Stolz, V., Bodden, E.: Temporal assertions using AspectJ. Electr. Notes Theor. Comput. Sci. 144(4), 109\u2013124 (2006)","journal-title":"Electr. Notes Theor. Comput. Sci."},{"key":"54_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/3-540-60915-6_6","volume-title":"Logics for Concurrency","author":"MY Vardi","year":"1996","unstructured":"Vardi, M.Y.: An automata-theoretic approach to linear temporal logic. In: Moller, F., Birtwistle, G. (eds.) Logics for Concurrency. LNCS, vol. 1043, pp. 238\u2013266. Springer, Heidelberg (1996)"}],"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-662-49674-9_54","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T08:28:18Z","timestamp":1748852898000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-49674-9_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662496732","9783662496749"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-49674-9_54","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"9 April 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}