2016/01/20 by Hugo Gimbert, Gimbert, Hugo
Computer Science · #Distributed systems and fault tolerance #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Petri Nets in System Modeling
paper · doi:10.48550/arxiv.1601.05176
openalex publication_date 2016/01/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The decidability of the distributed version of the Ramadge and Wonham controller synthesis problem,where both the plant and the controllers are modeled as asynchronous automataand the controllers have causal memoryis a challenging open problem.There exist three classes of plants for which the existence of a correct controller with causal memory has been shown decidable: when the dependency graph of actions is series-parallel, when the processes are connectedly communicating and when the dependency graph of processes is a tree. We design a class of plants, called decomposable games, with a decidable controller synthesis problem.This provides a unified proof of the three existing decidability results as well as new examples of decidable plants.