{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:51:35Z","timestamp":1742914295456,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030719944"},{"type":"electronic","value":"9783030719951"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,23]],"date-time":"2021-03-23T00:00:00Z","timestamp":1616457600000},"content-version":"vor","delay-in-days":81,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"abstract":"Abstract<\/jats:title>Which amount of parallel resources is needed for updating a query result after changing an input? In this work we study the amount of work required for dynamically answering membership and range queries for formal languages in parallel constant time with polynomially many processors. As a prerequisite, we propose a framework for specifying dynamic, parallel, constant-time programs that require small amounts of work. This framework is based on the dynamic descriptive complexity framework by Patnaik and Immerman.<\/jats:p>","DOI":"10.1007\/978-3-030-71995-1_25","type":"book-chapter","created":{"date-parts":[[2021,3,22]],"date-time":"2021-03-22T17:03:39Z","timestamp":1616432619000},"page":"490-509","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Work-sensitive Dynamic Complexity of Formal Languages"],"prefix":"10.1007","author":[{"given":"Jonas","family":"Schmidt","sequence":"first","affiliation":[]},{"given":"Thomas","family":"Schwentick","sequence":"additional","affiliation":[]},{"given":"Till","family":"Tantau","sequence":"additional","affiliation":[]},{"given":"Nils","family":"Vortmeier","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Zeume","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,3,23]]},"reference":[{"key":"25_CR1","doi-asserted-by":"publisher","unstructured":"Abboud, A., Backurs, A., Bringmann, K., K\u00fcnnemann, M.: Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve. In: Umans, C. (ed.) 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017. pp. 192\u2013203. IEEE Computer Society (2017). https:\/\/doi.org\/10.1109\/FOCS.2017.26","DOI":"10.1109\/FOCS.2017.26"},{"key":"25_CR2","unstructured":"Abboud, A., Backurs, A., Williams, V.V.: If the current clique algorithms are optimal, so is Valiant\u2019s parser. SIAM J. Comput. 47(6), 2527\u20132555 (2018)"},{"key":"25_CR3","doi-asserted-by":"publisher","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T.: Dynamic nested brackets. Inf. Comput. 193(2), 75\u201383 (2004). https:\/\/doi.org\/10.1016\/j.ic.2004.04.006, https:\/\/doi.org\/10.1016\/j.ic.2004.04.006","DOI":"10.1016\/j.ic.2004.04.006"},{"key":"25_CR4","doi-asserted-by":"publisher","unstructured":"B\u00f6rger, E.: Abstract state machines: a unifying view of models of computation and of system design frameworks. Ann. Pure Appl. Log. 133(1-3), 149\u2013171 (2005). https:\/\/doi.org\/10.1016\/j.apal.2004.10.007","DOI":"10.1016\/j.apal.2004.10.007"},{"key":"25_CR5","doi-asserted-by":"publisher","unstructured":"Datta, S., Kulkarni, R., Mukherjee, A., Schwentick, T., Zeume, T.: Reachability is in DynFO. J. ACM 65(5), 33:1\u201333:24 (2018). https:\/\/doi.org\/10.1145\/3212685","DOI":"10.1145\/3212685"},{"key":"25_CR6","doi-asserted-by":"crossref","unstructured":"Dong, G., Su, J.: First-order incremental evaluation of datalog queries. In: Database Programming Languages (DBPL-4), Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages, Manhattan, New York City, USA, 30 August - 1 September 1993. pp. 295\u2013308 (1993)","DOI":"10.1007\/978-1-4471-3564-7_17"},{"key":"25_CR7","doi-asserted-by":"publisher","unstructured":"Dong, G., Topor, R.W.: Incremental evaluation of datalog queries. In: Database Theory - ICDT\u201992, 4th International Conference, Berlin, Germany, October 14-16, 1992, Proceedings. pp. 282\u2013296 (1992). https:\/\/doi.org\/10.1007\/3-540-56039-4_48","DOI":"10.1007\/3-540-56039-4_48"},{"key":"25_CR8","doi-asserted-by":"publisher","unstructured":"Frandsen, G.S., Husfeldt, T., Miltersen, P.B., Rauhe, T., Skyum, S.: Dynamic algorithms for the Dyck languages. In: Akl, S.G., Dehne, F.K.H.A., Sack,J., Santoro, N. (eds.) Algorithms and Data Structures, 4th International Workshop, WADS \u201995, Kingston, Ontario, Canada, August 16-18, 1995, Proceedings. Lecture Notes in Computer Science, vol.\u00a0955, pp. 98\u2013108. Springer (1995). https:\/\/doi.org\/10.1007\/3-540-60220-8_54","DOI":"10.1007\/3-540-60220-8_54"},{"key":"25_CR9","doi-asserted-by":"publisher","unstructured":"Frandsen, G.S., Miltersen, P.B., Skyum, S.: Dynamic word problems. J. ACM 44(2), 257\u2013271 (1997). https:\/\/doi.org\/10.1145\/256303.256309","DOI":"10.1145\/256303.256309"},{"key":"25_CR10","unstructured":"Gall, F.L.: Powers of tensors and fast matrix multiplication. In: International Symposium on Symbolic and Algebraic Computation, ISSAC \u201914, Kobe, Japan, July 23-25, 2014. pp. 296\u2013303 (2014)"},{"key":"25_CR11","doi-asserted-by":"publisher","unstructured":"Gelade, W., Marquardt, M., Schwentick, T.: The dynamic complexity of formal languages. ACM Trans. Comput. Log. 13(3), 19 (2012). https:\/\/doi.org\/10.1145\/2287718.2287719","DOI":"10.1145\/2287718.2287719"},{"key":"25_CR12","doi-asserted-by":"publisher","unstructured":"Holm, J., de\u00a0Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM 48(4), 723\u2013760 (2001). https:\/\/doi.org\/10.1145\/502090.502095","DOI":"10.1145\/502090.502095"},{"key":"25_CR13","doi-asserted-by":"publisher","unstructured":"Holm, J., Rotenberg, E.: Fully-dynamic planarity testing in polylogarithmic time. In: Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., Chuzhoy, J. (eds.) Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020. pp. 167\u2013180. ACM (2020). https:\/\/doi.org\/10.1145\/3357713.3384249","DOI":"10.1145\/3357713.3384249"},{"key":"25_CR14","doi-asserted-by":"publisher","unstructured":"Immerman, N.: Descriptive complexity. Graduate texts in computer science, Springer (1999). https:\/\/doi.org\/10.1007\/978-1-4612-0539-5","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"25_CR15","unstructured":"Immerman, N.: Descriptive complexity. Springer Science & Business Media (2012)"},{"key":"25_CR16","unstructured":"J\u00e1J\u00e1, J.: An Introduction to Parallel Algorithms. Addison-Wesley (1992)"},{"key":"25_CR17","doi-asserted-by":"publisher","unstructured":"Libkin, L.: Elements of Finite Model Theory. Springer (2004). https:\/\/doi.org\/10.1007\/978-3-662-07003-1","DOI":"10.1007\/978-3-662-07003-1"},{"key":"25_CR18","unstructured":"McNaughton, R., Papert, S.: Counter-Free Automata. MIT Press (1971)"},{"key":"25_CR19","doi-asserted-by":"publisher","unstructured":"Miltersen, P.B., Subramanian, S., Vitter, J.S., Tamassia, R.: Complexity models for incremental computation. Theor. Comput. Sci. 130(1), 203\u2013236 (1994). https:\/\/doi.org\/10.1016\/0304-3975(94)90159-7","DOI":"10.1016\/0304-3975(94)90159-7"},{"key":"25_CR20","doi-asserted-by":"crossref","unstructured":"Patnaik, S., Immerman, N.: Dyn-FO: A parallel, dynamic complexity class. In: PODS. pp. 210\u2013221 (1994)","DOI":"10.1145\/182591.182614"},{"key":"25_CR21","unstructured":"Schmidt, J., Schwentick, T., Tantau, T., Vortmeier, N., Zeume, T.: Work-sensitive Dynamic Complexity of Formal Languages. CoRR abs\/2101.08735 (2021), https:\/\/arxiv.org\/abs\/2101.08735"},{"key":"25_CR22","doi-asserted-by":"publisher","unstructured":"Schwentick, T., Vortmeier, N., Zeume, T.: Sketches of dynamic complexity. SIGMOD Rec. 49(2), 18\u201329 (2020). https:\/\/doi.org\/10.1145\/3442322.3442325","DOI":"10.1145\/3442322.3442325"},{"key":"25_CR23","doi-asserted-by":"publisher","unstructured":"Schwentick, T., Zeume, T.: Dynamic Complexity: Recent Updates. SIGLOG News 3(2), 30\u201352 (2016). https:\/\/doi.org\/10.1145\/2948896.2948899","DOI":"10.1145\/2948896.2948899"},{"key":"25_CR24","doi-asserted-by":"publisher","unstructured":"Sherlekar, D.D., Pawagi, S., Ramakrishnan, I.V.: O(1) parallel time incremental graph algorithms. In: Maheshwari, S.N. (ed.) Foundations of Software Technology and Theoretical Computer Science, Fifth Conference, New Delhi, India, December 16-18, 1985, Proceedings. Lecture Notes in Computer Science, vol.\u00a0206, pp. 477\u2013495. Springer (1985). https:\/\/doi.org\/10.1007\/3-540-16042-6_27","DOI":"10.1007\/3-540-16042-6_27"},{"key":"25_CR25","doi-asserted-by":"crossref","unstructured":"Straubing, H.: Finite automata, formal logic, and circuit complexity. Birkhauser Verlag (1994)","DOI":"10.1007\/978-1-4612-0289-9"},{"key":"25_CR26","unstructured":"Vollmer, H.: Introduction to circuit complexity: a uniform approach. Springer Science & Business Media (2013)"},{"key":"25_CR27","doi-asserted-by":"publisher","unstructured":"Williams, V.V.: Multiplying matrices faster than Coppersmith-Winograd. In: Karloff, H.J., Pitassi, T. (eds.) Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012. pp. 887\u2013898. ACM (2012). https:\/\/doi.org\/10.1145\/2213977.2214056","DOI":"10.1145\/2213977.2214056"}],"container-title":["Lecture Notes in Computer Science","Foundations of Software Science and Computation Structures"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-71995-1_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,26]],"date-time":"2024-08-26T15:23:22Z","timestamp":1724685802000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-71995-1_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030719944","9783030719951"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-71995-1_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"23 March 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FOSSACS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Foundations of Software Science and Computation Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg City","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Luxembourg","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27 March 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 April 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"fossacs2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2021\/fossacs","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"88","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"32% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3,2","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference changed to an online format due to the COVID-19 pandemic","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}