{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T06:30:43Z","timestamp":1790749843859,"version":"4.1.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,5,31]],"date-time":"2016-05-31T00:00:00Z","timestamp":1464652800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DFG","award":["SCHW 678\/6-1"],"award-info":[{"award-number":["SCHW 678\/6-1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM SIGLOG News"],"published-print":{"date-parts":[[2016,5,31]]},"abstract":"<jats:p>In many data management scenarios the data is subject to frequent modifications, and it is often essential to react to those changes quickly. When a train is canceled on short notice, travelers need to find alternative connections as fast as possible. When a web server is temporarily not available, data packages have to be rerouted immediately.<\/jats:p>","DOI":"10.1145\/2948896.2948899","type":"journal-article","created":{"date-parts":[[2020,4,4]],"date-time":"2020-04-04T08:15:50Z","timestamp":1585988150000},"page":"30-52","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Dynamic complexity"],"prefix":"10.1145","volume":"3","author":[{"given":"Thomas","family":"Schwentick","sequence":"first","affiliation":[{"name":"TU Dortmund University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Zeume","sequence":"additional","affiliation":[{"name":"TU Dortmund University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2016,5,31]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Computational Complexity - A Modern Approach","author":"Arora Sanjeev","unstructured":"Sanjeev Arora and Boaz Barak . 2009. Computational Complexity - A Modern Approach . Cambridge University Press . Sanjeev Arora and Boaz Barak. 2009. Computational Complexity - A Modern Approach. Cambridge University Press."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90022-D"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90101-3"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80041-3"},{"key":"e_1_2_1_5_1","volume-title":"41st International Colloquium, ICALP","author":"Datta Samir","year":"2014","unstructured":"Samir Datta , William Hesse , and Raghav Kulkarni . 2014 . Dynamic Complexity of Directed Reachability and Other Problems. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Part I. 356--367. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-662-43948-7 30 10.1007\/978-3-662-43948-7 Samir Datta, William Hesse, and Raghav Kulkarni. 2014. Dynamic Complexity of Directed Reachability and Other Problems. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Part I. 356--367. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-662-43948-7 30"},{"key":"e_1_2_1_6_1","volume-title":"ICALP 2015, Proceedings, Part II. 159--170","author":"Datta Samir","year":"2015","unstructured":"Samir Datta , Raghav Kulkarni , Anish Mukherjee , Thomas Schwentick , and Thomas Zeume . 2015 . Reachability is in DynFO. In International Colloquium on Automata, Languages, and Programming , ICALP 2015, Proceedings, Part II. 159--170 . DOI:http:\/\/dx.doi.org\/10.1007\/978-3-662-47666-6_13 10.1007\/978-3-662-47666-6_13 Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, and Thomas Zeume. 2015. Reachability is in DynFO. In International Colloquium on Automata, Languages, and Programming, ICALP 2015, Proceedings, Part II. 159--170. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-662-47666-6_13"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118738.3118851"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00017-8"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the Fourth International Workshop on Database Programming Languages - Object Models and Languages. 295--308","author":"Dong Guozhu","year":"1993","unstructured":"Guozhu Dong and Jianwen Su . 1993 . 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. 295--308 . Guozhu Dong and Jianwen Su. 1993. 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. 295--308."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1565"},{"key":"e_1_2_1_11_1","volume-title":"4th International Conference. 282--296","author":"Dong Guozhu","unstructured":"Guozhu Dong and Rodney W. Topor . 1992. Incremental Evaluation of Datalog Queries. In Database Theory - ICDT'92 , 4th International Conference. 282--296 . DOI:http:\/\/dx.doi.org\/10.1007\/3-540-56039-4_48 10.1007\/3-540-56039-4_48 Guozhu Dong and Rodney W. Topor. 1992. Incremental Evaluation of Datalog Queries. In Database Theory - ICDT'92, 4th International Conference. 282--296. DOI:http:\/\/dx.doi.org\/10.1007\/3-540-56039-4_48"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275514"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.06.012"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2287718.2287719"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274601"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00740-5"},{"key":"e_1_2_1_18_1","volume-title":"Matrix analysis","author":"Horn Roger A","unstructured":"Roger A Horn and Charles R Johnson . 2012. Matrix analysis . Cambridge university press . Roger A Horn and Charles R Johnson. 2012. Matrix analysis. Cambridge university press."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Neil Immerman. 1999. Descriptive Complexity. Springer.  Neil Immerman. 1999. Descriptive Complexity . Springer.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"e_1_2_1_20_1","volume-title":"CSL","author":"K\u00e4hler Detlef","year":"2003","unstructured":"Detlef K\u00e4hler and Thomas Wilke . 2003 . Program Complexity of Dynamic LTL Model Checking. In Computer Science Logic , CSL 2003. 271--284. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-540-45220-1_23 10.1007\/978-3-540-45220-1_23 Detlef K\u00e4hler and Thomas Wilke. 2003. Program Complexity of Dynamic LTL Model Checking. In Computer Science Logic, CSL 2003. 271--284. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-540-45220-1_23"},{"key":"e_1_2_1_22_1","volume-title":"Simulating reachability using first-order logic with applications to verification of linked data structures. Logical Methods in Computer Science 5, 2","author":"Lev-Ami Tal","year":"2009","unstructured":"Tal Lev-Ami , Neil Immerman , Thomas W. Reps , Mooly Sagiv , Siddharth Srivastava , and Greta Yorsh . 2009. Simulating reachability using first-order logic with applications to verification of linked data structures. Logical Methods in Computer Science 5, 2 ( 2009 ). http:\/\/arxiv.org\/abs\/0904.4902 Tal Lev-Ami, Neil Immerman, Thomas W. Reps, Mooly Sagiv, Siddharth Srivastava, and Greta Yorsh. 2009. Simulating reachability using first-order logic with applications to verification of linked data structures. Logical Methods in Computer Science 5, 2 (2009). http:\/\/arxiv.org\/abs\/0904.4902"},{"key":"e_1_2_1_23_1","volume-title":"8th International Conference, VMCAI","author":"Lev-Ami Tal","year":"2007","unstructured":"Tal Lev-Ami , Mooly Sagiv , Neil Immerman , and Thomas W. Reps . 2007. Constructing Specialized Shape Analyses for Uniform Change. In Verification, Model Checking, and Abstract Interpretation , 8th International Conference, VMCAI 2007 . 215--233. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-540-69738-1_16 10.1007\/978-3-540-69738-1_16 Tal Lev-Ami, Mooly Sagiv, Neil Immerman, and Thomas W. Reps. 2007. Constructing Specialized Shape Analyses for Uniform Change. In Verification, Model Checking, and Abstract Interpretation, 8th International Conference, VMCAI 2007. 215--233. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-540-69738-1_16"},{"key":"e_1_2_1_24_1","volume-title":"Elements of Finite Model Theory","author":"Libkin Leonid","unstructured":"Leonid Libkin . 2004. Elements of Finite Model Theory . Springer . Leonid Libkin. 2004. Elements of Finite Model Theory. Springer."},{"key":"e_1_2_1_25_1","volume-title":"Cell probe complexity-a survey. (1999). Invited talk\/paper at Advances in Data Structures (Pre-conference workshop of FSTTCS'99)","author":"Miltersen Peter Bro","year":"1999","unstructured":"Peter Bro Miltersen . 1999. Cell probe complexity-a survey. (1999). Invited talk\/paper at Advances in Data Structures (Pre-conference workshop of FSTTCS'99) , 1999 . Never published, available at homepage. Peter Bro Miltersen. 1999. Cell probe complexity-a survey. (1999). Invited talk\/paper at Advances in Data Structures (Pre-conference workshop of FSTTCS'99), 1999. Never published, available at homepage."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90159-7"},{"key":"e_1_2_1_27_1","volume-title":"19th International Conference on Database Theory (ICDT","author":"Mu\u00f1oz Pablo","year":"2016","unstructured":"Pablo Mu\u00f1oz , Nils Vortmeier , and Thomas Zeume . 2016 . Dynamic graph queries. (2016). To appear in Proc . 19th International Conference on Database Theory (ICDT 2016). Pablo Mu\u00f1oz, Nils Vortmeier, and Thomas Zeume. 2016. Dynamic graph queries. (2016). To appear in Proc. 19th International Conference on Database Theory (ICDT 2016)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/182591.182614"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1520"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/060650271"},{"key":"e_1_2_1_31_1","volume-title":"Static Analysis for Logic-based Dynamic Programs. In 24th EACSL Annual Conference on Computer Science Logic, CSL 2015","author":"Schwentick Thomas","year":"2015","unstructured":"Thomas Schwentick , Nils Vortmeier , and Thomas Zeume . 2015 . Static Analysis for Logic-based Dynamic Programs. In 24th EACSL Annual Conference on Computer Science Logic, CSL 2015 . 308--324. DOI:http:\/\/dx.doi.org\/10.4230\/LIPIcs.CSL.2015.308 10.4230\/LIPIcs.CSL.2015.308 Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. 2015. Static Analysis for Logic-based Dynamic Programs. In 24th EACSL Annual Conference on Computer Science Logic, CSL 2015. 308--324. DOI:http:\/\/dx.doi.org\/10.4230\/LIPIcs.CSL.2015.308"},{"key":"e_1_2_1_32_1","volume-title":"Introduction to circuit complexity: a uniform approach","author":"Vollmer Heribert","unstructured":"Heribert Vollmer . 1999. Introduction to circuit complexity: a uniform approach . Springer . Heribert Vollmer. 1999. Introduction to circuit complexity: a uniform approach. Springer."},{"key":"e_1_2_1_33_1","volume-title":"Komplexit\u00e4tstheorie verlaufsunabh\u00e4ngiger dynamischer Programme. Master's thesis","author":"Vortmeier Nils","unstructured":"Nils Vortmeier . 2013. Komplexit\u00e4tstheorie verlaufsunabh\u00e4ngiger dynamischer Programme. Master's thesis . TU Dortmund University . Nils Vortmeier. 2013. Komplexit\u00e4tstheorie verlaufsunabh\u00e4ngiger dynamischer Programme. Master's thesis. TU Dortmund University."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1312-0"},{"key":"e_1_2_1_35_1","volume-title":"MFCS","author":"Zeume Thomas","year":"2014","unstructured":"Thomas Zeume . 2014 . The Dynamic Descriptive Complexity of k-Clique. In Mathematical Foundations of Computer Science 2014 - 39th International Symposium , MFCS 2014. 547--558. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-662-44522-8_46 10.1007\/978-3-662-44522-8_46 Thomas Zeume. 2014. The Dynamic Descriptive Complexity of k-Clique. In Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014. 547--558. DOI:http:\/\/dx.doi.org\/10.1007\/978-3-662-44522-8_46"},{"key":"e_1_2_1_37_1","volume-title":"Proc. 17th International Conference on Database Theory (ICDT 2014","author":"Zeume Thomas","year":"2014","unstructured":"Thomas Zeume and Thomas Schwentick . 2014 . Dynamic Conjunctive Queries . In Proc. 17th International Conference on Database Theory (ICDT 2014 ). 38--49. DOI:http:\/\/dx.doi.org\/10.5441\/002\/icdt.2014.08 10.5441\/002 Thomas Zeume and Thomas Schwentick. 2014. Dynamic Conjunctive Queries. In Proc. 17th International Conference on Database Theory (ICDT 2014). 38--49. DOI:http:\/\/dx.doi.org\/10.5441\/002\/icdt.2014.08"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.09.011"}],"container-title":["ACM SIGLOG News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2948896.2948899","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2948896.2948899","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:55:44Z","timestamp":1750222544000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2948896.2948899"}},"subtitle":["recent updates"],"short-title":[],"issued":{"date-parts":[[2016,5,31]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,5,31]]}},"alternative-id":["10.1145\/2948896.2948899"],"URL":"https:\/\/doi.org\/10.1145\/2948896.2948899","relation":{},"ISSN":["2372-3491"],"issn-type":[{"value":"2372-3491","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,31]]},"assertion":[{"value":"2016-05-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}