Paper published in a book (Scientific congresses, symposiums and conference proceedings)
A Graphical Proof Theory of Logical Time
Acclavio, Matteo; Horne, Ross James; Mauw, Sjouke et al.
2022In Felty, Amy P. (Ed.) Proc. 7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022)
Peer reviewed
 

Files


Full Text
LIPIcs-FSCD-2022-22.pdf
Publisher postprint (1.09 MB)
Download

All documents in ORBilu are protected by a user license.

Send to



Details



Abstract :
[en] 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.
Disciplines :
Computer science
Author, co-author :
Acclavio, Matteo ;  University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
Horne, Ross James ;  University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
Mauw, Sjouke ;  University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
Straßburger, Lutz;  Inria-Saclay, Palaiseau, France
External co-authors :
yes
Language :
English
Title :
A Graphical Proof Theory of Logical Time
Publication date :
2022
Event name :
7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022)
Event place :
Haifa, Israel
Event date :
August 2-5, 2022
Audience :
International
Main work title :
Proc. 7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022)
Editor :
Felty, Amy P.
Publisher :
Schloss Dagstuhl -- Leibniz-Zentrum fur Informatik, Germany
ISBN/EAN :
978-3-95977-233-4
Collection name :
Leibniz International Proceedings in Informatics
Pages :
22:1-22:25
Peer reviewed :
Peer reviewed
Focus Area :
Security, Reliability and Trust
Available on ORBilu :
since 19 January 2023

Statistics


Number of views
38 (0 by Unilu)
Number of downloads
3 (0 by Unilu)

Scopus citations®
 
3
Scopus citations®
without self-citations
1

Bibliography


Similar publications



Contact ORBilu