<div class="csl-bib-body">
<div class="csl-entry">van Ditmarsch, H., Kuznets, R., & Randrianomentsoa, R. (2023). On Two- and Three-valued Semantics for Impure Simplicial Complexes. In A. Achilleos & D. Della Monica (Eds.), <i>Proceedings of the Fourteenth International Symposium on Games, Automata, Logics, and Formal Verification</i> (pp. 50–66). Open Publishing Association. https://doi.org/10.4204/EPTCS.390.4</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/191632
-
dc.description.abstract
Simplicial complexes are a convenient semantic primitive to reason about processes (agents) communicating with each other in synchronous and asynchronous computation. Impure simplicial complexes distinguish active processes from crashed ones, in other words, agents that are alive from agents that are dead. In order to rule out that dead agents reason about themselves and about other agents, three-valued epistemic semantics have been proposed where, in addition to the usual values true and false, the third value stands for undefined: the knowledge of dead agents is undefined and so are the propositional variables describing their local state. Other semantics for impure complexes are two-valued where a dead agent knows everything. Different choices in designing a semantics produce different three-valued semantics, and also different two-valued semantics. In this work, we categorize the available choices by discounting the bad ones, identifying the equivalent ones, and connecting the non-equivalent ones via a translation. The main result of the paper is identifying the main relevant distinction to be the number of truth values and bridging this difference by means of a novel embedding from three- into two-valued semantics. This translation also enables us to highlight quite fundamental modeling differences underpinning various two- and three-valued approaches in this area of combinatorial topology. In particular, pure complexes can be defined as those invariant under the translation.
en
dc.description.sponsorship
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
simplicial complex
en
dc.subject
epistemic logic
en
dc.subject
distributed computing
en
dc.title
On Two- and Three-valued Semantics for Impure Simplicial Complexes
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.rights.license
Urheberrechtsschutz
de
dc.rights.license
In Copyright
en
dc.contributor.affiliation
Université de Toulouse, France
-
dc.relation.doi
10.4204/EPTCS.390
-
dc.description.startpage
50
-
dc.description.endpage
66
-
dc.relation.grantno
P 33600-N
-
dc.type.category
Full-Paper Contribution
-
dc.relation.eissn
2075-2180
-
tuw.booktitle
Proceedings of the Fourteenth International Symposium on Games, Automata, Logics, and Formal Verification
-
tuw.container.volume
390
-
tuw.book.ispartofseries
Electronic Proceedings in Theoretical Computer Science
-
tuw.relation.publisher
Open Publishing Association
-
tuw.project.title
Reasoning about Knowledge in Byzantine Distributed Systems
-
tuw.researchTopic.id
I2
-
tuw.researchTopic.name
Computer Engineering and Software-Intensive Systems
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E191-02 - Forschungsbereich Embedded Computing Systems
-
tuw.publisher.doi
10.4204/EPTCS.390.4
-
dc.identifier.libraryid
AC17203774
-
dc.description.numberOfPages
17
-
tuw.author.orcid
0000-0001-5894-8724
-
tuw.author.orcid
0000-0002-4553-5450
-
dc.rights.identifier
Urheberrechtsschutz
de
dc.rights.identifier
In Copyright
en
tuw.editor.orcid
0000-0002-1314-333X
-
tuw.editor.orcid
0000-0001-9743-665X
-
tuw.event.name
GandALF 2023: Fourteenth International Symposium on Games, Automata, Logics, and Formal Verification
en
tuw.event.startdate
18-09-2023
-
tuw.event.enddate
20-09-2023
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Udine
-
tuw.event.country
IT
-
tuw.event.institution
University of Udine
-
tuw.event.presenter
Randrianomentsoa, Rojo
-
tuw.event.track
Single Track
-
wb.sciencebranch
Informatik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.value
100
-
item.grantfulltext
open
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.openaccessfulltext
Open Access
-
item.openairetype
conference paper
-
item.cerifentitytype
Publications
-
item.fulltext
with Fulltext
-
item.mimetype
application/pdf
-
item.languageiso639-1
en
-
crisitem.author.dept
E191-02 - Forschungsbereich Embedded Computing Systems
-
crisitem.author.dept
E191-02 - Forschungsbereich Embedded Computing Systems
-
crisitem.author.dept
E191-02 - Forschungsbereich Embedded Computing Systems