Langages réguliers et complexité de communication constante

Soit une langue, et définissons par ssi . Je recherche une référence pour: $L \subseteq A^*$ $f_L\colon A^* \times A^* \to \{0, 1\}$ $f_L(x, y) = 1$ $x\cdot y \in L$

Proposition. est régulier si la complexité de communication déterministe de est constante. $L$ $f_L$

Autrement dit, est régulier ssi il existe un protocole à deux joueurs pour tel que la fonction est bornée par une constante, où est le nombre de bits échangés par Alice et Bob lorsque Alice reçoit et Bob , en suivant le protocole . $L$ $P$ $f_L$

n \mapsto max {comm (P, X, y) : | X \cdot y | = n}

$n \mapsto \max\{\text{comm}(P, x, y) : |x\cdot y| = n\}$

comm (P, x, y)

$\text{comm}(P, x, y)$

x

$x$

y

$y$

P

$P$

Le seul endroit que j'ai pu trouver est dans la thèse de George Hauser, 1989, disponible ici , où il généralise également cela à d'autres distributions de l'entrée entre Alice et Bob, de sorte que le nombre de "coupes" est constant. $x\cdot y$

reference-request communication-complexity regular-language Michaël Cadilhac
la source

Prenez un langage

C

$C$ qui n'est pas régulier, et définissez

L = {c \circ r : c \in C, r \in {0, 1}^{| c |}}

$L = \{c \circ r : c \in C, r \in \{0,1\}^{|c|} \}$ . Alors

L

$L$ a la complexité de communication

O (1)

$O(1)$ , mais ce n'est certainement pas régulier. Qu'est-ce que je rate?

Igor Shinkar

@IgorShinkar: Je ne suis pas sûr d'obtenir précisément ce que vous y avez écrit, mais vous semblez faire allusion à la preuve classique que chaque langue avec un seul mot par longueur peut être transformée en une langue avec une complexité de communication constante. Cependant, cela suppose qu'Alice et Bob reçoivent exactement la moitié du mot testé; ici, il n'y a pas une telle hypothèse et, de manière contradictoire, ils devraient résoudre le problème compte tenu de la répartition des intrants. Est-ce que ça répond à votre question?

Michaël Cadilhac

Oh je vois. Donc, si pour toute division, le CC est constant, alors est régulier.

L

$L$

Igor Shinkar

Réponses:

Pour , vous avez "Communication Complexity", Eyal Kushilevitz dans Advances in Computers, Volume 44, 1997 ( http://www.sciencedirect.com/science/article/pii/S0065245808603423 ). $\Rightarrow$

Vous pouvez également trouver une section "Communication Complexity and Chomsky Hierarchy" dans le livre "Communication Complexity and Parallel Computing" de Juraj Hromkovič où cela est prouvé. Il se peut que soit également prouvé quelque part dans le livre, mais je ne le trouve pas ici. La chose la plus proche semble être l'Exercice 5.2.5.2 mais, ce n'est qu'un exercice (voir aussi le Chapitre 5 entier, qui étudie en détail l'automate fini mais je ne pense pas qu'il réponde explicitement à votre question). $\Leftarrow$

Pour ce que ça vaut, la preuve des deux directions semble facile donc je pense que si vous en avez besoin dans un papier vous pouvez le dessiner rapidement: pour , prenez un automate fini pour et observez qu'il suffit à Alice de communiquer l'état qu'elle atteint après avoir lu sa partie de l'entrée. Ensuite, Bob termine la simulation dans les automates. Pour , si vous avez un protocole limité par une constante, alors a un nombre fini de quotient qui est une caractérisation bien connue des langages réguliers . $\Rightarrow$ $L$ $\Leftarrow$ $L$ $w^{-1}L = \{u : wu \in L\}$

loup
la source

Merci beaucoup pour votre contribution. Je suis d'accord que c'est un résultat facile, et naturel à cela, et qui devrait probablement être considéré comme du folklore. En fait, je connais très bien les deux références que vous donnez et, tout comme vous, je n'y ai pas trouvé le protocole que j'examine ci-dessus. Cette question étant une "demande de référence", je crains de ne pas pouvoir accepter votre réponse à ce stade.

Michaël Cadilhac

Je sais, mais c'était trop long pour un commentaire et je pense qu'il valait quand même la peine de mentionner qu'au moins une façon est prouvée explicitement dans la littérature. Je vous préviens si je tombe sur la preuve!

holf

Très apprécié! :-)

Michaël Cadilhac