{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:51:35Z","timestamp":1756000295833,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2022,9,5]],"date-time":"2022-09-05T00:00:00Z","timestamp":1662336000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,9,5]],"date-time":"2022-09-05T00:00:00Z","timestamp":1662336000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["677651"],"award-info":[{"award-number":["677651"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"anr","award":["ANR-16-CE40-0007"],"award-info":[{"award-number":["ANR-16-CE40-0007"]}]},{"DOI":"10.13039\/501100020884","name":"ANID","doi-asserted-by":"crossref","award":["Code ICN17_002","Code ICN17_002"],"award-info":[{"award-number":["Code ICN17_002","Code ICN17_002"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so through the lenses of parameterized dynamic data structures: we assume that the automaton is fixed and its size is the parameter, while the input word is revealed as in a stream, one symbol at a time following the natural order on positions. The goal is to design a dynamic data structure that can be efficiently updated upon revealing the next symbol, while maintaining the answer to the query on whether the word consisting of symbols revealed so far is accepted by the automaton. We provide complexity bounds for this dynamic acceptance problem for timed automata that process symbols interleaved with time spans. The main contribution is a dynamic data structure that maintains acceptance of a fixed one-clock timed automaton\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathcal {A}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>A<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with amortized update time\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$2^{{\\mathcal {O}}(|{\\mathcal {A}}|)}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mrow>\n                      <mml:mi>O<\/mml:mi>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mo>|<\/mml:mo>\n                      <mml:mi>A<\/mml:mi>\n                      <mml:mo>|<\/mml:mo>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> per input symbol. \n<\/jats:p>","DOI":"10.1007\/s00453-022-01025-8","type":"journal-article","created":{"date-parts":[[2022,9,5]],"date-time":"2022-09-05T08:04:10Z","timestamp":1662365050000},"page":"3223-3245","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Dynamic Data Structures for Timed Automata Acceptance"],"prefix":"10.1007","volume":"84","author":[{"given":"Alejandro","family":"Grez","sequence":"first","affiliation":[]},{"given":"Filip","family":"Mazowiecki","sequence":"additional","affiliation":[]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[]},{"given":"Gabriele","family":"Puppis","sequence":"additional","affiliation":[]},{"given":"Cristian","family":"Riveros","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,9,5]]},"reference":[{"issue":"4","key":"1025_CR1","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1145\/3395037","volume":"16","author":"J Alman","year":"2020","unstructured":"Alman, J., Mnich, M., Williams, V.V.: Dynamic parameterized problems and algorithms. ACM Trans. Algorithms 16(4), 45\u201314546 (2020). https:\/\/doi.org\/10.1145\/3395037","journal-title":"ACM Trans. Algorithms"},{"key":"1025_CR2","first-page":"146","volume":"26","author":"M Bannach","year":"2019","unstructured":"Bannach, M., Heinrich, Z., Reischuk, R., Tantau, T.: Dynamic kernels for hitting sets and set packing. Electronic Colloquium on Computational Complexity 26, 146 (2019)","journal-title":"Electronic Colloquium on Computational Complexity"},{"key":"1025_CR3","doi-asserted-by":"publisher","unstructured":"Chen, J., Czerwi\u0144ski, W., Disser, Y., Feldmann, A.E., Hermelin, D., Nadara, W., Pilipczuk, M., Pilipczuk, M., Sorge, M., Wr\u00f3blewski, B., Zych-Pawlewicz, A.: Efficient fully dynamic elimination forests with applications to detecting long paths and cycles. In: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, pp. 796\u2013809. SIAM, Virtual Conference (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.50","DOI":"10.1137\/1.9781611976465.50"},{"issue":"2","key":"1025_CR4","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0304-3975(94)90010-8","volume":"126","author":"R Alur","year":"1994","unstructured":"Alur, R., Dill, D.L.: A theory of timed automata. Theoret. Comput. Sci. 126(2), 183\u2013235 (1994). https:\/\/doi.org\/10.1016\/0304-3975(94)90010-8","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20132","key":"1025_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0020-0190(00)00075-2","volume":"75","author":"B B\u00e9rard","year":"2000","unstructured":"B\u00e9rard, B., Dufourd, C.: Timed automata and additive clock constraints. Inf. Process. Lett. 75(1\u20132), 1\u20137 (2000). https:\/\/doi.org\/10.1016\/S0020-0190(00)00075-2","journal-title":"Inf. Process. Lett."},{"key":"1025_CR6","doi-asserted-by":"publisher","unstructured":"Clemente, L., Lasota, S.: Timed pushdown automata revisited. In: 30th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, pp. 738\u2013749 (2015). https:\/\/doi.org\/10.1109\/LICS.2015.73","DOI":"10.1109\/LICS.2015.73"},{"key":"1025_CR7","doi-asserted-by":"publisher","unstructured":"Grez, A., Mazowiecki, F., Pilipczuk, M., Puppis, G., Riveros, C.: Dynamic data structures for timed automata acceptance. In: Golovach, P.A., Zehavi, M. (eds.) 16th International Symposium on Parameterized and Exact Computation, IPEC 2021. LIPIcs, vol. 214, pp. 20\u201312018. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Lisbon, Portugal (2021). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2021.20","DOI":"10.4230\/LIPIcs.IPEC.2021.20"},{"issue":"5","key":"1025_CR8","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. Log. Algebraic Methods Program. 78(5), 293\u2013303 (2009). https:\/\/doi.org\/10.1016\/j.jlap.2008.08.004","journal-title":"J. Log. Algebraic Methods Program."},{"key":"1025_CR9","doi-asserted-by":"publisher","unstructured":"Tripakis, S.: Fault diagnosis for timed automata. In: 7th International Symposium on Formal Techniques in Real-Time and Fault-Tolerant Systems, FTRTFT 2002, Oldenburg, Germany, pp. 205\u2013224 (2002). https:\/\/doi.org\/10.1007\/3-540-45739-9_14","DOI":"10.1007\/3-540-45739-9_14"},{"key":"1025_CR10","doi-asserted-by":"publisher","unstructured":"Bouyer, P., Jaziri, S., Markey, N.: Efficient timed diagnosis using automata with timed domains. In: Colombo, C., Leucker, M. (eds.) 18th International Conference on Runtime Verification, RV 2018. Lecture Notes in Computer Science, vol. 11237, pp. 205\u2013221. Springer, Limassol, Cyprus (2018). https:\/\/doi.org\/10.1007\/978-3-030-03769-7_12","DOI":"10.1007\/978-3-030-03769-7_12"},{"key":"1025_CR11","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/j.entcs.2004.01.029","volume":"113","author":"P Thati","year":"2005","unstructured":"Thati, P., Rosu, G.: Monitoring algorithms for metric temporal logic specifications. Electronic Notes in Theoretical Computer Science 113, 145\u2013162 (2005). https:\/\/doi.org\/10.1016\/j.entcs.2004.01.029","journal-title":"Electronic Notes in Theoretical Computer Science"},{"key":"1025_CR12","doi-asserted-by":"publisher","unstructured":"Babcock, B., Babu, S., Datar, M., Motwani, R., Widom, J.: Models and issues in data stream systems. In: Popa, L., Abiteboul, S., Kolaitis, P.G. (eds.) 21st ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS 2002, pp. 1\u201316. ACM, Madison, Wisconsin, USA (2002). https:\/\/doi.org\/10.1145\/543613.543615","DOI":"10.1145\/543613.543615"},{"issue":"6","key":"1025_CR13","doi-asserted-by":"publisher","first-page":"1794","DOI":"10.1137\/S0097539701398363","volume":"31","author":"M Datar","year":"2002","unstructured":"Datar, M., Gionis, A., Indyk, P., Motwani, R.: Maintaining stream statistics over sliding windows. SIAM J. Comput. 31(6), 1794\u20131813 (2002)","journal-title":"SIAM J. Comput."},{"key":"1025_CR14","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1090\/dimacs\/050\/05","volume":"50","author":"MR Henzinger","year":"1998","unstructured":"Henzinger, M.R., Raghavan, P., Rajagopalan, S.: Computing on data streams. External Memory Algorithms 50, 107\u2013118 (1998)","journal-title":"External Memory Algorithms"},{"key":"1025_CR15","doi-asserted-by":"publisher","unstructured":"Berkholz, C., Keppeler, J., Schweikardt, N.: Answering conjunctive queries under updates. In: Sallinger, E., den Bussche, J.V., Geerts, F. (eds.) 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, pp. 303\u2013318. ACM, Chicago, Illinois, USA (2017). https:\/\/doi.org\/10.1145\/3034786.3034789","DOI":"10.1145\/3034786.3034789"},{"issue":"1","key":"1025_CR16","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/3371316.3371325","volume":"48","author":"M Idris","year":"2019","unstructured":"Idris, M., Ugarte, M., Vansummeren, S., Voigt, H., Lehner, W.: Efficient query processing for dynamically changing datasets. ACM SIGMOD Rec. 48(1), 33\u201340 (2019)","journal-title":"ACM SIGMOD Rec."},{"key":"1025_CR17","doi-asserted-by":"publisher","unstructured":"II, P.M.L., Stearns, R.E., Hartmanis, J.: Memory bounds for recognition of context-free and context-sensitive languages. In: 6th Annual Symposium on Switching Circuit Theory and Logical Design, SWCT 1965, pp. 191\u2013202. IEEE Computer Society, Ann Arbor, Michigan, USA (1965). https:\/\/doi.org\/10.1109\/FOCS.1965.14","DOI":"10.1109\/FOCS.1965.14"},{"issue":"6","key":"1025_CR18","doi-asserted-by":"publisher","first-page":"1880","DOI":"10.1137\/130926122","volume":"43","author":"F Magniez","year":"2014","unstructured":"Magniez, F., Mathieu, C., Nayak, A.: Recognizing well-parenthesized expressions in the streaming model. SIAM J. Comput. 43(6), 1880\u20131905 (2014)","journal-title":"SIAM J. Comput."},{"key":"1025_CR19","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2012.12.028","volume":"494","author":"A Babu","year":"2013","unstructured":"Babu, A., Limaye, N., Radhakrishnan, J., Varma, G.: Streaming algorithms for language recognition problems. Theoret. Comput. Sci. 494, 13\u201323 (2013)","journal-title":"Theoret. Comput. Sci."},{"key":"1025_CR20","unstructured":"Ganardi, M., Hucke, D., Lohrey, M.: Querying regular languages over sliding windows. In: 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2016, Chennai, India, pp. 18\u201311814 (2016)"},{"key":"1025_CR21","doi-asserted-by":"publisher","unstructured":"Ganardi, M., Hucke, D., K\u00f6nig, D., Lohrey, M., Mamouras, K.: Automata theory on sliding windows. In: Niedermeier, R., Vall\u00e9e, B. (eds.) 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018. LIPIcs, vol. 96, pp. 31\u201313114. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Caen, France (2018). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2018.31","DOI":"10.4230\/LIPIcs.STACS.2018.31"},{"key":"1025_CR22","doi-asserted-by":"publisher","unstructured":"Ganardi, M.: Language recognition in the sliding window model. PhD thesis, Universit\u00e4t Siegen (2019). https:\/\/doi.org\/10.25819\/ubsi\/464. Institut f\u00fcr Theoretische Informatik","DOI":"10.25819\/ubsi\/464"},{"key":"1025_CR23","doi-asserted-by":"publisher","unstructured":"Tangwongsan, K., Hirzel, M., Schneider, S.: Low-latency sliding-window aggregation in worst-case constant time. In: 11th ACM International Conference on Distributed and Event-based Systems, DEBS 2017, pp. 66\u201377. ACM, Barcelona, Spain (2017). https:\/\/doi.org\/10.1145\/3093742.3093925","DOI":"10.1145\/3093742.3093925"},{"key":"1025_CR24","unstructured":"Shamos, M.I.: Computational geometry. PhD thesis, Yale University (1978)"},{"key":"1025_CR25","doi-asserted-by":"publisher","unstructured":"Grez, A., Riveros, C., Ugarte, M.: A formal framework for complex event processing. In: 22nd International Conference on Database Theory, ICDT 2019. LIPIcs, vol. 127, pp. 5\u20131518. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Lisbon, Portugal (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2019.5","DOI":"10.4230\/LIPIcs.ICDT.2019.5"},{"issue":"4","key":"1025_CR26","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/3485463","volume":"46","author":"A Grez","year":"2021","unstructured":"Grez, A., Riveros, C., Ugarte, M., Vansummeren, S.: A formal framework for complex event recognition. ACM Trans. Database Syst. 46(4), 16\u201311649 (2021)","journal-title":"ACM Trans. Database Syst."},{"key":"1025_CR27","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0925-7721(95)00022-2","volume":"5","author":"A Gajentaan","year":"1995","unstructured":"Gajentaan, A., Overmars, M.H.: On a class of $${O}(n^2)$$ problems in computational geometry. Comput. Geom. 5, 165\u2013185 (1995). https:\/\/doi.org\/10.1016\/0925-7721(95)00022-2","journal-title":"Comput. Geom."},{"issue":"4","key":"1025_CR28","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1016\/j.comgeo.2011.11.006","volume":"45","author":"A Gajentaan","year":"2012","unstructured":"Gajentaan, A., Overmars, M.H.: On a class of $${O}(n^2)$$ problems in computational geometry. Comput. Geom. 45(4), 140\u2013152 (2012). https:\/\/doi.org\/10.1016\/j.comgeo.2011.11.006","journal-title":"Comput. Geom."},{"issue":"4","key":"1025_CR29","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/3185378","volume":"65","author":"A Gr\u00f8nlund","year":"2018","unstructured":"Gr\u00f8nlund, A., Pettie, S.: Threesomes, degenerates, and love triangles. J. ACM 65(4), 22\u201312225 (2018). https:\/\/doi.org\/10.1145\/3185378","journal-title":"J. ACM"},{"key":"1025_CR30","doi-asserted-by":"publisher","unstructured":"Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, pp. 434\u2013443. IEEE Computer Society, Philadelphia, PA, USA (2014). https:\/\/doi.org\/10.1109\/FOCS.2014.53","DOI":"10.1109\/FOCS.2014.53"},{"key":"1025_CR31","doi-asserted-by":"publisher","unstructured":"Kopelowitz, T., Pettie, S., Porat, E.: Higher lower bounds from the 3SUM conjecture. In: 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, pp. 1272\u20131287. SIAM, Arlington, VA, USA (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch89","DOI":"10.1137\/1.9781611974331.ch89"},{"key":"1025_CR32","doi-asserted-by":"publisher","unstructured":"P\u0103tra\u015fcu, M.: Towards polynomial lower bounds for dynamic problems. In: 42nd ACM Symposium on Theory of Computing, STOC 2010, pp. 603\u2013610. ACM, Cambridge, Massachusetts, USA (2010). https:\/\/doi.org\/10.1145\/1806689.1806772","DOI":"10.1145\/1806689.1806772"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01025-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01025-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01025-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,25]],"date-time":"2022-10-25T12:28:06Z","timestamp":1666700886000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01025-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,5]]},"references-count":32,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["1025"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01025-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,9,5]]},"assertion":[{"value":"9 December 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 September 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interest"}}]}}