A structural linearization principle for processes

In [11], an induction principle for processes was given which allows one to apply model-checking techniques to parameterized families of processes. A limitation of the induction principle is that it does not apply to the case in which one process depends directly upon a parameterized number of processes, which grows without bound. This would seem to preclude its application to families ofN processes interconnected in a star topology. Nonetheless, we show that if the dependency can be computed incrementally, then the direct dependency upon the parameterized number of processes may be re-expressed recursively in terms of a linear cascade of processes, yielding in effect a linearization of the inter-process dependencies and allowing the induction principle to apply.A previous version of this paper appears in the Proceedings of CAV 1993 (LNCS 697).