Mutual exclusion problems for discrete event systems with shared events

摘要

The authors consider coordination problems for partially synchronized processes. They prove that the decidability of the mutual exclusion problem with shared events is not solvable in polynomial time. However, they also show that there is an interesting subclass of discrete event processes with shared events for which the mutual exclusion problem remains computationally feasible.