Communicating Finite-State Machines and Two-Variable Logic

Benedikt Bollig, Marie Fortin, Paul Gastin

Communicating finite-state machines are a fundamental, well-studied model of finite-state processes that communicate via unbounded first-in first-out channels. We show that they ar…