A spectral property for concurrent systems and some probabilistic applications

Abstract

We aim at constructing a probabilistic framework on the executions of concurrent systems for the purpose of random generation. In our setting, the abstract concurrent systems are considered as monoid actions on a finite set of states, which encompass 1-bounded Petri nets. We introduce a notion of irreducible concurrent system and we prove the equivalence between irreducibility and a “spectral property”. This proof relies on the techniques of analytic combinatorics and resolves the difficulty that the Perron-Frobenius theorem is not directly applicable for concurrent systems. Finally, we apply the spectral property to the probabilistic theory of concurrent systems. The uniform measure of executions can be realized as a Markov chain of states-and-cliques on a state space. With the aid of spectral property, we are able to distinguish the main components which determine the characteristic root of the system.

線上視訊請點選連結

 

附件下載