Recency-Bounded Verification of Dynamic Database-Driven Systems
MetadataShow full item record
SubjectComputability and decidability; Model checking; Data aware business processes; Relational transition systems; Formal logic
We propose a formalism to model database-driven systems, called database manipulating systems (DMS). The actions of a DMS modify the current instance of a relational database by adding new elements into the database, deleting tuples from the relations and adding tuples to the relations. The elements which are modified by an action are chosen by (full) first-order queries. DMS is a highly expressive model and can be thought of as a succinct representation of an infinite state relational transition system, in line with similar models proposed in the literature. We propose monadic second order logic (MSO-FO) to reason about sequences of database instances appearing along a run. Unsurprisingly, the linear-time model checking problem of DMS against MSO-FO is undecidable. Towards decidability, we propose under-approximate model checking of DMS, where the under-approximation parameter is the "bound on recency". In a k-recency-bounded run, only the most recent k elements in the current active domain may be modified by an action. More runs can be verified by increasing the bound on recency. Our main result shows that recency-bounded model checking of DMS against MSO-FO is decidable, by a reduction to the satisfiability problem of MSO over nested words. © 2016 ACM.
Showing items related by title, author, creator and subject.
Montagesystemplanung für die schlanke Produktion (assembly system planning for lean) production): Eine Methode zur Gestaltung flexibler Montagesysteme im Rahmen ganzheitlicher Produktionssysteme (A method for designing flexible assembly systems as part of integrated production systems) Gschirr, M; Baur, G; Rauch, E (Carl Hanser Verlag, 2009)Under the pressure of an increasing number of variants, smaller lot sizes and shorter product life cycles many companies are constrained to adapt their production con-tinuously at the needs of the environment. More and ...
Matt, DT; Rauch, E (InTech, 2012)The geographically distributed production of fresh food poses unique challenges to the production system design because of their stringent industry and logistics requirements. The purpose of this research is to examine the ...
Collaborative Cloud Manufacturing: Design of Business Model Innovations Enabled by Cyberphysical Systems in Distributed Manufacturing Systems Rauch E; Seidenstricker S; Dallasega P; Hämmerl R (2016)Collaborative cloud manufacturing, as a concept of distributed manufacturing, allows different opportunities for changing the logic of generating and capturing value. Cyberphysical systems and the technologies behind them ...