Document Open Access Logo

A Strategy for Dynamic Programs: Start over and Muddle Through

Authors Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, Thomas Zeume

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.98.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

Samir Datta
Anish Mukherjee
Thomas Schwentick
Nils Vortmeier
Thomas Zeume

Cite As Get BibTex

Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. A Strategy for Dynamic Programs: Start over and Muddle Through. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 98:1-98:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.98

Abstract

A strategy for constructing dynamic programs is introduced that utilises periodic computation of auxiliary data from scratch and the ability to maintain a query for a limited number of change steps. It is established that if some program can maintain a query for log n change steps after an AC^1-computable initialisation, it can be maintained by a first-order dynamic program as well, i.e., in DynFO. As an application, it is shown that decision and optimisation problems defined by monadic second-order (MSO) and guarded second-order logic (GSO) formulas are in DynFO, if only change sequences that produce graphs of bounded treewidth are allowed. To establish this result, Feferman-Vaught-type composition theorems for MSO and GSO are established that might be useful in their own right.

Subject Classification

Keywords
  • dynamic complexity
  • treewidth
  • monadic second order logic

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Patricia Bouyer, Vincent Jugé, and Nicolas Markey. Dynamic complexity of parity games with bounded tree-width. CoRR, abs/1610.00571, 2016. URL: http://arxiv.org/abs/1610.00571.
  2. Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, and Thomas Zeume. Reachability is in DynFO. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, volume 9135 of Lecture Notes in Computer Science, pages 159-170. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47666-6_13.
  3. Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, and Thomas Zeume. Reachability is in DynFO. CoRR, abs/1502.07467, 2015. URL: http://arxiv.org/abs/1502.07467.
  4. Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. A strategy for dynamic programs: Start over and muddle through. CoRR, abs/1704.07998, 2017. URL: http://arxiv.org/abs/1704.07998.
  5. Guozhu Dong, Jianwen Su, and Rodney W. Topor. Nonrecursive incremental evaluation of datalog queries. Ann. Math. Artif. Intell., 14(2-4):187-223, 1995. URL: http://dx.doi.org/10.1007/BF01530820.
  6. Michael Elberfeld, Martin Grohe, and Till Tantau. Where first-order and monadic second-order logic coincide. ACM Trans. Comput. Log., 17(4):25:1-25:18, 2016. URL: http://dx.doi.org/10.1145/2946799.
  7. Michael Elberfeld, Andreas Jakoby, and Till Tantau. Logspace versions of the theorems of Bodlaender and Courcelle. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 143-152. IEEE Computer Society, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.21.
  8. Wouter Gelade, Marcel Marquardt, and Thomas Schwentick. The dynamic complexity of formal languages. ACM Trans. Comput. Log., 13(3):19, 2012. URL: http://dx.doi.org/10.1145/2287718.2287719.
  9. Neil Immerman. Descriptive complexity. Graduate texts in computer science. Springer, 1999. Google Scholar
  10. Leonid Libkin. Elements of Finite Model Theory. Springer, 2004. Google Scholar
  11. Sushant Patnaik and Neil Immerman. Dyn-FO: A parallel, dynamic complexity class. J. Comput. Syst. Sci., 55(2):199-209, 1997. URL: http://dx.doi.org/10.1006/jcss.1997.1520.
  12. Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. Dynamic complexity under definable changes. In 20th International Conference on Database Theory, ICDT 2017, March 21-24, 2017, Venice, Italy, pages 19:1-19:18, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICDT.2017.19.
  13. Thomas Schwentick and Thomas Zeume. Dynamic complexity: recent updates. SIGLOG News, 3(2):30-52, 2016. URL: http://dx.doi.org/10.1145/2948896.2948899.
  14. Saharon Shelah. The monadic theory of order. Annals of Mathematics, pages 379-419, 1975. URL: http://dx.doi.org/10.2307/1971037.
  15. Heribert Vollmer. Introduction to Circuit Complexity - A Uniform Approach. Texts in Theoretical Computer Science. An EATCS Series. Springer, 1999. Google Scholar
  16. Volker Weber and Thomas Schwentick. Dynamic complexity theory revisited. Theory Comput. Syst., 40(4):355-377, 2007. URL: http://dx.doi.org/10.1007/s00224-006-1312-0.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact