1 Search Results for "Mauw, Sjouke"

Document
DOI: 10.4230/LIPIcs.FSCD.2022.22
A Graphical Proof Theory of Logical Time

Authors: Matteo Acclavio, Ross Horne, Sjouke Mauw, and Lutz Straßburger

Published in: LIPIcs, Volume 228, 7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022)

Abstract
Logical time is a partial order over events in distributed systems, constraining which events precede others. Special interest has been given to series-parallel orders since they correspond to formulas constructed via the two operations for "series" and "parallel" composition. For this reason, series-parallel orders have received attention from proof theory, leading to pomset logic, the logic BV, and their extensions. However, logical time does not always form a series-parallel order; indeed, ubiquitous structures in distributed systems are beyond current proof theoretic methods. In this paper, we explore how this restriction can be lifted. We design new logics that work directly on graphs instead of formulas, we develop their proof theory, and we show that our logics are conservative extensions of the logic BV.
Cite as

Matteo Acclavio, Ross Horne, Sjouke Mauw, and Lutz Straßburger. A Graphical Proof Theory of Logical Time. In 7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 228, pp. 22:1-22:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{acclavio_et_al:LIPIcs.FSCD.2022.22,
  author =	{Acclavio, Matteo and Horne, Ross and Mauw, Sjouke and Stra{\ss}burger, Lutz},
  title =	{{A Graphical Proof Theory of Logical Time}},
  booktitle =	{7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022)},
  pages =	{22:1--22:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-233-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{228},
  editor =	{Felty, Amy P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2022.22},
  URN =		{urn:nbn:de:0030-drops-163037},
  doi =		{10.4230/LIPIcs.FSCD.2022.22},
  annote =	{Keywords: proof theory, causality, deep inference}
}
  • Refine by Author
  • 1 Acclavio, Matteo
  • 1 Horne, Ross
  • 1 Mauw, Sjouke
  • 1 Straßburger, Lutz

  • Refine by Classification
  • 1 Theory of computation → Linear logic
  • 1 Theory of computation → Process calculi
  • 1 Theory of computation → Proof theory

  • Refine by Keyword
  • 1 causality
  • 1 deep inference
  • 1 proof theory

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact