Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Bollig, Benedikt; Fortin, Marie; Gastin, Paul http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-95455
URL:

; ;

It Is Easy to Be Wise After the Event: Communicating Finite-State Machines Capture First-Order Logic with "Happened Before"

pdf-format:


Abstract

Message sequence charts (MSCs) naturally arise as executions of communicating finite-state machines (CFMs), in which finite-state processes exchange messages through unbounded FIFO channels. We study the first-order logic of MSCs, featuring Lamport's happened-before relation. We introduce a star-free version of propositional dynamic logic (PDL) with loop and converse. Our main results state that (i) every first-order sentence can be transformed into an equivalent star-free PDL sentence (and conversely), and (ii) every star-free PDL sentence can be translated into an equivalent CFM. This answers an open question and settles the exact relation between CFMs and fragments of monadic second-order logic. As a byproduct, we show that first-order logic over MSCs has the three-variable property.

BibTeX - Entry

@InProceedings{bollig_et_al:LIPIcs:2018:9545,
  author =	{Benedikt Bollig and Marie Fortin and Paul Gastin},
  title =	{{It Is Easy to Be Wise After the Event: Communicating Finite-State Machines Capture First-Order Logic with "Happened Before"}},
  booktitle =	{29th International Conference on Concurrency Theory  (CONCUR 2018)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-087-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{118},
  editor =	{Sven Schewe and Lijun Zhang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9545},
  URN =		{urn:nbn:de:0030-drops-95455},
  doi =		{10.4230/LIPIcs.CONCUR.2018.7},
  annote =	{Keywords: communicating finite-state machines, first-order logic, happened-before relation}
}

Keywords: communicating finite-state machines, first-order logic, happened-before relation
Seminar: 29th International Conference on Concurrency Theory (CONCUR 2018)
Issue date: 2018
Date of publication: 2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI