A Kantorovich-monadic powerdomain for information hiding, with probability and nondeterminism

Annabelle McIver*, Larissa Meinicke, Carroll Morgan

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

18 Citations (Scopus)

Abstract

We propose a novel domain-theoretic model for nondeterminism, probability and hidden state, with relations on it that compare information flow. One relation is Smyth-like, based on a structural, refinement-like order between semantic elements; the other is a testing order that generalises several extant entropy-based techniques. Our principal theorem is that the two orders are equivalent. The model is based on the Giry/Kantorovich monads, and it abstracts Partially Observable Markov Decision Processes by discarding observables' actual values but retaining the effect they had on an observer's knowledge. We illustrate the model, and its orders, on some small examples, where we find that our formalism provides the apparatus for comparing systems in terms of the information they leak.

Original languageEnglish
Title of host publicationProceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2012
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages461-470
Number of pages10
ISBN (Print)9780769547695
DOIs
Publication statusPublished - 2012
Event2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2012 - Dubrovnik, Croatia
Duration: 25 Jun 201228 Jun 2012

Other

Other2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2012
Country/TerritoryCroatia
CityDubrovnik
Period25/06/1228/06/12

Fingerprint

Dive into the research topics of 'A Kantorovich-monadic powerdomain for information hiding, with probability and nondeterminism'. Together they form a unique fingerprint.

Cite this