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 @math -recency-bounded run, only the most recent @math 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.
Both in @cite_11 and @cite_0 , decidability is obtained by constructing a faithful, finite-state abstraction that preserves the properties to be verified. This shows that state-bounded dynamic systems are an interesting class of @cite_12 . On the other hand, state-boundedness is a too restrictive requirement when dealing with systems such as that of Example . In fact, allowing for unboundedly many tuples to be stored in the database is required to deal with , whose behavior is influenced by the presence of certain patterns in the (unbounded) history of the system (cf. the definition of in Example ). It is also essential to capture , where the currently executed task may be interrupted by a task with a higher-priority, and so on, resuming the execution of the original task only when the (unbounded) chain of higher-priority tasks is completed. See, e.g., the pre-emptive offer handling adopted in Example . Notably, as argued in Example , such classes of unbounded systems can all be subject to model checking, by choosing a sufficiently large bound for recency.
@cite_0 @cite_12 @cite_11
2050591418 2204935731
In this paper, we give a step by step introduction to the theory of well quasi-ordered transition systems. The framework combines two concepts, namely (i) transition systems which are monotonic wrt ... We explore the paradigm of artifact-centric systems from a knowledge-based perspective. We provide a semantics based on interpreted-systems to interpret a first-order temporal-epistemic language with identity in a multi-agent setting. We consider the model checking problem for this language and provide abstraction results. We isolate a natural subclass of artifact-systems for which the model checking problem is decidable. We give an upper bound on the complexity of the model checking problem.