Coalgebraic Tools for Randomness-Conserving Protocols

DOI10.1016/J.JLAMP.2021.100734MaRDI QIDQ6303957arXivFDO

Authors Dexter Kozen, Matvey Soloviev

Publication date 7 July 2018

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.JLAMP.2021.100734

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Measures of information, entropy (94A17)

arXiv classification

cs.FLcs.ITcs.LOmath.ITmath.PR

Abstract: We propose a coalgebraic model for constructing and reasoning about state-based protocols that implement efficient reductions among random processes. We provide basic tools that allow efficient protocols to be constructed in a compositional way and analyzed in terms of the tradeoff between state and loss of entropy. We show how to use these tools to construct various entropy-conserving reductions between processes.

This page was built for publication: Coalgebraic Tools for Randomness-Conserving Protocols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6303957)