The regular viewpoint on PA-processes
PA is the process algebra allowing non-determinism, sequential and parallel compositions, and recursion. We suggest viewing PA-processes as trees, and using tree-automata techniques for verification problems on PA. Our main result is that the set of iterated predecessors of a regular set of PA-processes is a regular tree language, and similarly for iterated successors. Furthermore, the corresponding tree automata can be built effectively in polynomial time. This has many immediate applications to verification problems for PA-processes, among which a simple and general model-checking algorithm. (C) 2002 Elsevier Science B.V. All rights reserved.
process algebra tree automata verification of infinite-state systems