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 language | English |
---|---|
Title of host publication | Proceedings of the 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2012 |
Place of Publication | Piscataway, NJ |
Publisher | Institute of Electrical and Electronics Engineers (IEEE) |
Pages | 461-470 |
Number of pages | 10 |
ISBN (Print) | 9780769547695 |
DOIs | |
Publication status | Published - 2012 |
Event | 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2012 - Dubrovnik, Croatia Duration: 25 Jun 2012 → 28 Jun 2012 |
Other
Other | 2012 27th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2012 |
---|---|
Country/Territory | Croatia |
City | Dubrovnik |
Period | 25/06/12 → 28/06/12 |