Infinite Communication Complexity

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.
Type de document :
Pré-publication, Document de travail
First Version. Written from the Computer Science POV. 2014
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01108690
Contributeur : Emmanuel Jeandel <>
Soumis le : vendredi 23 janvier 2015 - 11:58:32
Dernière modification le : jeudi 22 septembre 2016 - 14:31:42
Document(s) archivé(s) le : vendredi 24 avril 2015 - 10:22:14

Fichiers

comm.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01108690, version 1

Citation

Pierre Guillon, Emmanuel Jeandel. Infinite Communication Complexity. First Version. Written from the Computer Science POV. 2014. 〈hal-01108690〉

Partager

Métriques

Consultations de
la notice

327

Téléchargements du document

85