2020/12/08 by Laure Petrucci, Petrucci, Laure, Michał Knapik +1
Computer Science · #FOS: Computer and information sciences #Formal Methods in Verification #Logic in Computer Science (cs.LO) #Model-Driven Software Engineering Techniques #cs.LO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2012.04739
arxiv created 2020/12/08 · openalex publication_date 2020/12/08 · arxiv updated 2020/12/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We investigate networks of automata that synchronise over common action labels. A graph synchronisation topology between the automata is defined in such a way that two automata are connected iff they can synchronise over an action. We show a very effective reduction of networks of automata with tree-like synchronisation topologies. The reduction preserves a certain form of reachability, but not safety. The procedure is implemented in an open-source tool.