Communicating Finite-State Machines and Two-Variable Logic
classification
💻 cs.LO
cs.FL
keywords
finite-statecommunicatinglogicmachineschannelscommunicateequivalentexistential
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.