Static analysis for logic-based dynamic programs

DOI10.4230/LIPICS.CSL.2015.308MaRDI QIDQ5351965zbMATH OpenOpenAlexFDO

Authors Thomas Schwentick, Nils Vortmeier, Thomas Zeume

Publication date 31 August 2017

Full work available at URL https://arxiv.org/abs/1507.04537

zbMATH Keywords

algorithmic problemsconsistencydynamic descriptive complexityemptinesshistory independence

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Database theory (68P15) Descriptive complexity and finite models (68Q19)

Abstract: A dynamic program, as introduced by Patnaik and Immerman (1994), maintains the result of a fixed query for an input database which is subject to tuple insertions and deletions. It can use an auxiliary database whose relations are updated via first-order formulas upon modifications of the input database. This paper studies static analysis problems for dynamic programs and investigates, more specifically, the decidability of the following three questions. Is the answer relation of a given dynamic program always empty? Does a program actually maintain a query? Is the content of auxiliary relations independent of the modification sequence that lead to an input database? In general, all these problems can easily be seen to be undecidable for full first-order programs. Therefore the paper aims at pinpointing the exact decidability borderline for programs with restricted arity (of the input and/or auxiliary database) and restricted quantification.

Recommendations

• Dynamic complexity under definable changes
• A strategy for dynamic programs: start over and muddle through
• A strategy for dynamic programs: start over and muddle through
• Static analysis in Datalog extensions
• STACS 2005

Cited in

(9)

• Static analysis for state-space reductions preserving temporal logics
• scientific article; zbMATH DE number 4178742 (Why is no real title available?)
• scientific article; zbMATH DE number 4058916 (Why is no real title available?)
• scientific article; zbMATH DE number 1956566 (Why is no real title available?)
• scientific article; zbMATH DE number 1834571 (Why is no real title available?)
• A strategy for dynamic programs: start over and muddle through
• A strategy for dynamic programs: start over and muddle through
• Principles of staged static+dynamic partial analysis
• A dynamic logic for QASM programs

This page was built for publication: Static analysis for logic-based dynamic programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5351965)