State-Boundedness in Data-Aware Dynamic Systems

Proc. of the 14th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR 2014). 2014.

Verification of dynamic systems that manipulate data, stored in a database or ontology, has lately received increasing attention. A plethora of recent works has shown that verification of systems working over unboundedly many data is decidable even for very rich temporal properties, provided that the system is state-bounded. This condition requires the existence of an overall bound on the amount of data stored in each single state along the system evolution. In general, checking state-boundedness is undecidable. An open question is whether it is possible to isolate significant classes of dynamic systems for which state-boundedness is decidable. In this paper we provide a strong negative answer, by resorting to a novel connection with variants of Petri nets. In particular, we show undecidability for systems whose data component contains unary relations only, and whose action component queries and updates such relations in a very limited way. To contrast this result, we propose interesting relaxations of the sufficient conditions proposed in the concrete setting of Data-Centric Dynamic Systems, building on recent results on chase termination for tuple-generating dependencies.

@inproceedings{KR-2014-state-boundedness,
   title = "State-Boundedness in Data-Aware Dynamic Systems",
   year = "2014",
   author = "Bagheri Hariri, Babak and Diego Calvanese and Marco Montali
and Alin Deutsch",
   booktitle = "Proc. of the 14th Int. Conf. on Principles of Knowledge
Representation and Reasoning (KR 2014)",
   pages = "458--467",
   publisher = "AAAI Press",
}