research-article

Dynamic complexity: recent updates

Authors:

Thomas Schwentick,

Thomas ZeumeAuthors Info & Claims

ACM SIGLOG News, Volume 3, Issue 2

Pages 30 - 52

https://doi.org/10.1145/2948896.2948899

Published: 31 May 2016 Publication History

Abstract

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.

References

[1]

Sanjeev Arora and Boaz Barak. 2009. Computational Complexity - A Modern Approach. Cambridge University Press.

Digital Library

[2]

David A. Mix Barrington, Neil Immerman, and Howard Straubing. 1990. On Uniformity within NC<sup>1</sup>. J. Comput. Syst. Sci. 41, 3 (1990), 274--306.

Digital Library

[3]

Jin-yi Cai. 1990. Lower Bounds for Constant-Depth Circuits in the Presence of Help Bits. Inf. Process. Lett. 36, 2 (1990), 79--83.

Digital Library

[4]

Stephen A. Cook. 1985. A Taxonomy of Problems with Fast Parallel Algorithms. Information and Control 64, 1--3 (1985), 2--21.

Digital Library

[5]

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. 30

[6]

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.

[7]

Camil Demetrescu and Giuseppe F. Italiano. 2008. Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure. Algorithmica 51, 4 (2008), 387--427.

Digital Library

[8]

Guozhu Dong, Leonid Libkin, and Limsoon Wong. 2003. Incremental recomputation in local languages. Inf. Comput. 181, 2 (2003), 88--98.

Digital Library

[9]

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.

Digital Library

[10]

Guozhu Dong and Jianwen Su. 1998. Arity Bounds in First-Order Incremental Evaluation and Definition of Polynomial Time Database Queries. J. Comput. Syst. Sci. 57, 3 (1998), 289--308.

Digital Library

[11]

Guozhu Dong and Rodney W. Topor. 1992. Incremental Evaluation of Datalog Queries. In Database Theory - ICDT'92, 4th International Conference. 282--296.

Digital Library

[12]

Kousha Etessami. 1998. Dynamic Tree Isomorphism via First-Order Updates. In Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS 1998. 235--243.

Digital Library

[13]

Gudmund Skovbjerg Frandsen and Peter Frands Frandsen. 2009. Dynamic matrix rank. Theor. Comput. Sci. 410, 41 (2009), 4085--4093.

Digital Library

[14]

Wouter Gelade, Marcel Marquardt, and Thomas Schwentick. 2012. The dynamic complexity of formal languages. ACM Trans. Comput. Log. 13, 3 (2012), 19.

Digital Library

[15]

Erich Grädel and Sebastian Siebertz. 2012. Dynamic definability. In 15th International Conference on Database Theory, ICDT 2012. 236--248.

Digital Library

[16]

William Hesse. 2003a. The dynamic complexity of transitive closure is in DynTC<sup>0</sup>. Theor. Comput. Sci. 296, 3 (2003), 473--485.

Digital Library

[17]

William Hesse. 2003b. Dynamic Computational Complexity. Ph.D. Dissertation. University of Massachusetts, Amherst.

Digital Library

[18]

Roger A Horn and Charles R Johnson. 2012. Matrix analysis. Cambridge university press.

Digital Library

[19]

Neil Immerman. 1999. Descriptive Complexity. Springer.

[20]

Detlef Kähler and Thomas Wilke. 2003. Program Complexity of Dynamic LTL Model Checking. In Computer Science Logic, CSL 2003. 271--284.

[21]

Bastian Laubner. 2011. The structure of graphs and new logics for the characterization of Polynomial Time. Ph.D. Dissertation. Humboldt University of Berlin. http://edoc.hu-berlin.de/dissertationen/laubner-bastian-2011-02-23/PDF/laubner.pdf

[22]

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

[23]

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.

Digital Library

[24]

Leonid Libkin. 2004. Elements of Finite Model Theory. Springer.

Digital Library

[25]

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.

[26]

Peter Bro Miltersen, Sairam Subramanian, Jeffrey Scott Vitter, and Roberto Tamassia. 1994. Complexity Models for Incremental Computation. Theor. Comput. Sci. 130, 1 (1994), 203--236.

Digital Library

[27]

Pablo Muñoz, Nils Vortmeier, and Thomas Zeume. 2016. Dynamic graph queries. (2016). To appear in Proc. 19th International Conference on Database Theory (ICDT 2016).

[28]

Sushant Patnaik and Neil Immerman. 1994. Dyn-FO: A Parallel, Dynamic Complexity Class. In Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS 1994. 210--221.

Digital Library

[29]

Sushant Patnaik and Neil Immerman. 1997. Dyn-FO: A Parallel, Dynamic Complexity Class. J. Comput. Syst. Sci. 55, 2 (1997), 199--209.

Digital Library

[30]

Liam Roditty and Uri Zwick. 2008. Improved Dynamic Reachability Algorithms for Directed Graphs. SIAM J. Comput. 37, 5 (2008), 1455--1471.

Digital Library

[31]

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.

[32]

Heribert Vollmer. 1999. Introduction to circuit complexity: a uniform approach. Springer.

Digital Library

[33]

Nils Vortmeier. 2013. Komplexitätstheorie verlaufsunabhängiger dynamischer Programme. Master's thesis. TU Dortmund University.

[34]

Volker Weber and Thomas Schwentick. 2007. Dynamic Complexity Theory Revisited. Theory Comput. Syst. 40, 4 (2007), 355--377.

Digital Library

[35]

Thomas Zeume. 2014. The Dynamic Descriptive Complexity of k-Clique. In Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014. 547--558.

[36]

Thomas Zeume. 2015. Small Dynamic Complexity Classes. Ph.D. Dissertation. TU Dortmund University.

[37]

Thomas Zeume and Thomas Schwentick. 2014. Dynamic Conjunctive Queries. In Proc. 17th International Conference on Database Theory (ICDT 2014). 38--49.

[38]

Thomas Zeume and Thomas Schwentick. 2015. On the quantifier-free dynamic complexity of Reachability. Inf. Comput. 240 (2015), 108--129.

Digital Library

Cited By

Kara ANgo HNikolic MOlteanu DZhang H(2020)Maintaining Triangle Queries under UpdatesACM Transactions on Database Systems10.1145/339637545:3(1-46)Online publication date: 26-Aug-2020
https://dl.acm.org/doi/10.1145/3396375
Schwentick TVortmeier NZeume T(2018)Dynamic Complexity under Definable ChangesACM Transactions on Database Systems10.1145/324104043:3(1-38)Online publication date: 9-Oct-2018
https://dl.acm.org/doi/10.1145/3241040
Berkholz CKeppeler JSchweikardt N(2018)Answering FO+MOD Queries under Updates on Bounded Degree DatabasesACM Transactions on Database Systems10.1145/323205643:2(1-32)Online publication date: 22-Aug-2018
https://dl.acm.org/doi/10.1145/3232056
Show More Cited By

Recommendations

Whole-program dynamic software updating
Mathematical characterizations and computational complexity of anti-slide puzzles
Abstract
For a given set of pieces and a frame, an anti-slide puzzle asks us to arrange the pieces so that none of the pieces can slide in the frame. Since the first anti-slide puzzle that consists of dozens of cuboid pieces in 3D was invented, ...
Dynamic Data Warehousing (abstract)
DaWaK '99: Proceedings of the First International Conference on Data Warehousing and Knowledge Discovery

Data warehouses and on-line analytical processing (OLAP) tools have become essential elements of decision support systems. Traditionally, data warehouses are refreshed periodically (for example, nightly) by extracting, transforming, cleaning and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGLOG News

ACM SIGLOG News Volume 3, Issue 2

April 2016

55 pages

EISSN:2372-3491

DOI:10.1145/2948896

Editor:
Andrzej Murawski
University of Warwick

Issue’s Table of Contents

Copyright © 2016 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 May 2016

Published in SIGLOG Volume 3, Issue 2

Check for updates

Qualifiers

Research-article

Funding Sources

DFG

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
126
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kara ANgo HNikolic MOlteanu DZhang H(2020)Maintaining Triangle Queries under UpdatesACM Transactions on Database Systems10.1145/339637545:3(1-46)Online publication date: 26-Aug-2020
https://dl.acm.org/doi/10.1145/3396375
Schwentick TVortmeier NZeume T(2018)Dynamic Complexity under Definable ChangesACM Transactions on Database Systems10.1145/324104043:3(1-38)Online publication date: 9-Oct-2018
https://dl.acm.org/doi/10.1145/3241040
Berkholz CKeppeler JSchweikardt N(2018)Answering FO+MOD Queries under Updates on Bounded Degree DatabasesACM Transactions on Database Systems10.1145/323205643:2(1-32)Online publication date: 22-Aug-2018
https://dl.acm.org/doi/10.1145/3232056
Datta SKulkarni RMukherjee ASchwentick TZeume T(2018)Reachability Is in DynFOJournal of the ACM10.1145/321268565:5(1-24)Online publication date: 29-Aug-2018
https://dl.acm.org/doi/10.1145/3212685
Berkholz CKeppeler JSchweikardt NSallinger EVan den Bussche JGeerts F(2017)Answering Conjunctive Queries under UpdatesProceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3034786.3034789(303-318)Online publication date: 9-May-2017
https://dl.acm.org/doi/10.1145/3034786.3034789

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents