Reachability Analysis of Process Rewrite Systems

摘要

Process Rewrite Systems (PRS for short) subsume many common (infinite-state) models such as pushdown systems and Petri nets. They can be adopted as formal models of parallel programs (multithreaded programs) with procedure calls. We develop automata techniques allowing to build finite representations of the forward/backward sets of reachable configurations of PRSs modulo various term structural equivalences (corresponding to properties of the operators of sequential composition and parallel composition). We show that, in several cases, these reachability sets can be represented by polynomial size finite bottom-up tree-automata. When associativity and commutativity of the parallel composition is taken into account, nonregular representations based on (a decidable class of) counter tree automata are sometimes needed.