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].
Origine : Fichiers produits par l'(les) auteur(s)
Loading...