Communicating finite-state machines and two-variable logic

DOI10.4230/LIPICS.STACS.2018.17MaRDI QIDQ3304111zbMATH OpenOpenAlexFDO

Authors Benedikt Bollig, Marie Fortin, Paul Gastin

Publication date 5 August 2020

Full work available at URL https://arxiv.org/abs/1709.09991

zbMATH Keywords

communicating finite-state machinesmessage sequence chartsMSO logic

Mathematics Subject Classification ID

Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

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.

Recommendations

• Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic
• It is easy to be wise after the event: communicating finite-state machines capture first-order logic with ``happened before
• Developments in Language Theory
• On Communicating Finite-State Machines
• Message-passing automata are expressively equivalent to EMSO logic

Cites work

• A Kleene theorem and model checking algorithms for existentially bounded communicating automata
• A theory of regular MSC languages
• Adding nesting structure to words
• Asynchronous distributed automata: a characterization of the modal \(\mu\)-fragment
• Computer Science Logic
• Decision Problems of Finite Automata Design and Related Arithmetics
• Distributed graph automata
• Finite automata and the logic of one-place predicates
• Generalized finite automata theory with an application to a decision problem of second-order logic
• scientific article; zbMATH DE number 1670860 (Why is no real title available?)
• scientific article; zbMATH DE number 3266604 (Why is no real title available?)
• Logic and Branching Automata
• Message-passing automata are expressively equivalent to EMSO logic
• Modal logic and distributed message passing automata
• Notes on finite asynchronous automata
• On communicating automata with bounded channels
• On Communicating Finite-State Machines
• On logics with two variables
• On notions of regularity for data languages
• Propositional dynamic logic for message-passing systems
• Propositional dynamic logic of regular programs
• Regular sets of infinite message sequence charts
• Two-variable logic on data words
• Weak models of distributed computing, with connections to modal logic

Cited in

(3)

• Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic
• It is easy to be wise after the event: communicating finite-state machines capture first-order logic with ``happened before
• Developments in Language Theory

This page was built for publication: Communicating finite-state machines and two-variable logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3304111)