Communicating Finite-State Machines and Two-Variable Logic

09/28/2017

∙

by   Benedikt Bollig, et al.

∙

0

∙

share

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 are expressively equivalent to existential MSO logic with two first-order variables and the order relation.