Rewriting systems with data a framework for reasoning about systems with unbounded structures over infinite data domains
Ahmed Bouajjani, Peter Habermehl, Yan Jurski, Mihaela Sighireanu · 2007
Abstract. We introduce a uniform framework for reasoning about infinitestate systems with unbounded control structures and unbounded data domains. Our framework is based on constrained rewriting systems on words over an infinite alphabet. We consider several rewriting semantics: factor, prefix, and multiset rewriting. Constraints are expressed in a logic on such words which is parametrized by a first-order theory on the considered data domain. We show that our framework is suitable for reasoning about various classes of systems such as recursive sequential programs, multithreaded programs, parametrized and dynamic networks of processes, etc. Then, we provide generic results (1) for the decidability of the satisfiability problem of the fragment ∃ ∗ ∀ ∗ of this logic provided that the underlying logic on data is decidable, and (2) for proving inductive invariance and for carrying out Hoare style reasoning within this fragment. We also show that the reachability problem if decidable for a class of prefix rewriting systems with integer data. 1