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 of N 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.