Communication complexity tools on recognizable picture languages - GREYC amacc Access content directly
Journal Articles Theoretical Computer Science Year : 2019

Communication complexity tools on recognizable picture languages

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].
Fichier principal
Vignette du fichier
comComUREC.pdf (308.13 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook X LinkedIn More