Linguagens regulares e complexidade constante de comunicação

Vamos $L \subseteq A^*$ seja um idioma, e definir $f_L\colon A^* \times A^* \to \{0, 1\}$ por $f_L(x, y) = 1$ sse $x\cdot y \in L$ . Estou procurando uma referência para:

Proposição. $L$ é regular se a complexidade determinística da comunicação de $f_L$ é constante.

$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$

O único lugar que pude encontrar é na tese de doutorado de George Hauser, 1989, disponível aqui , onde ele também generaliza isso para outras distribuições da entrada entre Alice e Bob, de modo que o número de "cortes" seja constante. $x\cdot y$

reference-request communication-complexity regular-language Michaël Cadilhac
fonte

Pegue um idioma que não seja regular e defina . Então tem complexidade de comunicação , mas certamente não é regular. o que estou perdendo?

C

$C$

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

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

L

$L$

O (1)

$O(1)$

Igor Shinkar

@IgorShinkar: Não sei se entendi exatamente o que você escreveu lá, mas você parece estar sugerindo a prova clássica de que todo idioma com uma única palavra por comprimento pode ser transformado em um idioma com constante complexidade de comunicação. No entanto, isso pressupõe que Alice e Bob recebem exatamente metade da palavra sendo testada; aqui, não existe tal suposição e, de maneira contraditória, eles devem resolver o problema, dada qualquer divisão da entrada. Isso responde à sua pergunta?

Michaël Cadilhac

Ah eu vejo. Portanto, para qualquer divisão, o CC é constante, então é regular.

L

$L$

Igor Shinkar

Respostas:

Para , você tem "Complexidade da comunicação", Eyal Kushilevitz em Avanços em computadores, volume 44, 1997 ( http://www.sciencedirect.com/science/article/pii/S0065245808603423 ). $\Rightarrow$

Você também pode encontrar a seção "Complexidade da comunicação e hierarquia de Chomsky" no livro "Complexidade da comunicação e computação paralela", de Juraj Hromkovič, onde é comprovada. Pode ser que também esteja comprovado em algum lugar do livro, mas não consigo encontrá-lo aqui. O mais próximo que parece haver é o Exercício 5.2.5.2, mas é apenas um exercício (veja também o Capítulo 5 inteiro, que estuda extensivamente o autômato finito, mas não acho que ele responda explicitamente à sua pergunta). $\Leftarrow$

Pelo que vale a pena, a prova de ambas as direções parece fácil, então acho que, se você precisar dela em um artigo, pode esboçá-la rapidamente: para , pegue um autômato finito para e observe que Alice é suficiente para se comunicar o estado que ela alcança após ter lido sua parte da entrada. Então Bob termina a simulação nos autômatos. Para , se você possui um protocolo limitado por uma constante, possui um número finito de quociente que é uma caracterização bem conhecida de linguagens regulares . $\Rightarrow$ $L$ $\Leftarrow$ $L$ $w^{-1}L = \{u : wu \in L\}$

holf
fonte

Muito obrigado pela sua contribuição. Concordo que é um resultado fácil e natural, e provavelmente deveria ser considerado folclore. Conheço as duas referências que você fornece muito bem e, como você fez, não consegui encontrar o protocolo que estou considerando acima. Como esta pergunta é uma "solicitação de referência", receio que não possa aceitar sua resposta neste momento.

Michaël Cadilhac

Eu sei, mas foi muito longo para um comentário e acho que ainda vale a pena mencionar que pelo menos uma maneira é provada explicitamente na literatura. Eu deixo você saber se eu tropeçar na prova!

Holf

Muito apreciado! :-)

Michaël Cadilhac