Coalgebraic tools for randomness-conserving protocols

被引：0

作者：

Kozen, Dexter ^{[1
]}

Soloviev, Matvey ^{[1
]}

机构：

[1] Cornell Univ, Ithaca, NY 14853 USA

来源：

JOURNAL OF LOGICAL AND ALGEBRAIC METHODS IN PROGRAMMING | 2022年 / 125卷

关键词：

Randomness; Entropy; Protocol; Reduction; Transducer; Coalgebra;

D O I：

10.1016/j.jlamp.2021.100734

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. (C) 2021 Published by Elsevier Inc.

引用

页数：23

共 30 条

[1]

Adamek J., 1991, FDN CODING

[2]

[Anonymous], 1951, National Bureau of Standards Applied Mathematics Series

[3]

[Anonymous], 1974, A Course in Probability Theory

[4] INDEPENDENT UNBIASED COIN FLIPS FROM A CORRELATED BIASED SOURCE - A FINITE STATE MARKOV-CHAIN [J].

BLUM, M .

COMBINATORICA, 1986, 6 (02) :97-108

[5]

Böcherer G, 2014, IEEE INT SYMP INFO, P176, DOI 10.1109/ISIT.2014.6874818

[6]

Cassels J., 1965, Cambridge Tracts in Math., V45

[7]

Cover Thomas M, 1999, Elements of Information Theory

[8]

Doberkat E.E., 2007, STOCHASTIC RELATIONS

[9]

Dodis Y, 2004, LECT NOTES COMPUT SC, V3122, P334

[10]

Doob J.L., 1953, Stochastic processes, V2

← 1 2 3 →