DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2011.443

Concurrency Semantics for the Geiger-Paz-Pearl Axioms of Independence

Authors: Sara Miner More, Pavel Naumov, and Benjamin Sapp

Published in: LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011)

Abstract

Independence between two sets of random variables is a well-known relation in probability theory. Its origins trace back to Abraham de Moivre's work in the 18th century. The propositional theory of this relation was axiomatized by Geiger, Paz, and Pearl. Sutherland introduced a relation in information flow theory that later became known as "nondeducibility." Subsequently, the first two authors generalized this relation from a relation between two arguments to a relation between two sets of arguments and proved that it is completely described by essentially the same axioms as independence in probability theory. This paper considers a non-interference relation between two groups of concurrent processes sharing common resources. Two such groups are called non-interfering if, when executed concurrently, the only way for them to reach deadlock is for one of the groups to deadlock internally. The paper shows that a complete axiomatization of this relation is given by the same Geiger-Paz-Pearl axioms.

Cite as

Sara Miner More, Pavel Naumov, and Benjamin Sapp. Concurrency Semantics for the Geiger-Paz-Pearl Axioms of Independence. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 443-457, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{minermore_et_al:LIPIcs.CSL.2011.443,
  author =	{Miner More, Sara and Naumov, Pavel and Sapp, Benjamin},
  title =	{{Concurrency Semantics for the Geiger-Paz-Pearl Axioms of Independence}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{443--457},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Bezem, Marc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.443},
  URN =		{urn:nbn:de:0030-drops-32480},
  doi =		{10.4230/LIPIcs.CSL.2011.443},
  annote =	{Keywords: independence, concurrency, information flow, axiomatization}
}

Search Results

Documents authored by Sapp, Benjamin

Concurrency Semantics for the Geiger-Paz-Pearl Axioms of Independence

Abstract

Cite as

Thanks for your feedback!

Could not send message