License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2011.443
URN: urn:nbn:de:0030-drops-32480
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3248/
Go to the corresponding LIPIcs Volume Portal

Miner More, Sara ; Naumov, Pavel ; Sapp, Benjamin

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

pdf-format:
35.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{minermore_et_al:LIPIcs:2011:3248,
  author =	{Sara Miner More and Pavel Naumov and Benjamin Sapp},
  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 =	{Marc Bezem},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3248},
  URN =		{urn:nbn:de:0030-drops-32480},
  doi =		{10.4230/LIPIcs.CSL.2011.443},
  annote =	{Keywords: independence, concurrency, information flow, axiomatization}
}

Keywords: independence, concurrency, information flow, axiomatization
Collection: Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL
Issue Date: 2011
Date of publication: 31.08.2011

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