Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

Infinite Communication Complexity

Pierre Guillon 1 Emmanuel Jeandel 2 
2 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : Suppose that Alice and Bob are given each an infinite string, and they want to decide whether their two strings are in a given relation. How much communication do they need? How can communication be even defined and measured for infinite strings? In this article, we propose a formalism for a notion of infinite communication complexity, prove that it satisfies some natural properties and coincides, for relevant applications, with the classical notion of amortized communication complexity. More-over, an application is given for tackling some conjecture about tilings and multidimensional sofic shifts.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Emmanuel Jeandel Connect in order to contact the contributor
Submitted on : Friday, January 23, 2015 - 11:58:32 AM
Last modification on : Thursday, January 20, 2022 - 5:33:01 PM
Long-term archiving on: : Friday, April 24, 2015 - 10:22:14 AM


Files produced by the author(s)


  • HAL Id : hal-01108690, version 1


Pierre Guillon, Emmanuel Jeandel. Infinite Communication Complexity. 2014. ⟨hal-01108690⟩



Record views


Files downloads