Communication complexity tools on recognizable picture languages - Normandie Université Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2019

Communication complexity tools on recognizable picture languages

Résumé

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].
Fichier principal
Vignette du fichier
comComUREC.pdf (308.13 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02151118 , version 1 (07-06-2019)

Identifiants

Citer

Véronique Terrier. Communication complexity tools on recognizable picture languages. Theoretical Computer Science, 2019, ⟨10.1016/j.tcs.2019.05.040⟩. ⟨hal-02151118⟩
114 Consultations
178 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More