Skip to Main content Skip to Navigation
Journal articles

Communication complexity tools on recognizable picture languages

Véronique Terrier 1
1 Equipe AMACC - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
Abstract : The paper deals with the class REC of recognizable picture languages, UREC its unambiguous variant and co-REC the complement class of REC. The aim of this paper is twofold: First, the paper focuses on some necessary conditions for a language to be recognizable. Such conditions have already been identified in several works [13, 1, 5, 2, 3]. Here, we revisit them in the light of communication complexity arguments. Second, we use communication complexity measures in order to construct a language which is a recognizable and co-recognizable language but not an unam-biguous one. This answers a question raised in [14].
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

https://hal-normandie-univ.archives-ouvertes.fr/hal-02151118
Contributor : Véronique Terrier <>
Submitted on : Friday, June 7, 2019 - 4:57:02 PM
Last modification on : Friday, January 8, 2021 - 11:22:06 AM

File

comComUREC.pdf
Files produced by the author(s)

Identifiers

Citation

Véronique Terrier. Communication complexity tools on recognizable picture languages. Theoretical Computer Science, Elsevier, 2019, ⟨10.1016/j.tcs.2019.05.040⟩. ⟨hal-02151118⟩

Share

Metrics

Record views

106

Files downloads

152