Zwykłe języki i stała złożoność komunikacji

Pozwolić $L \subseteq A^*$ być językiem i zdefiniować $f_L\colon A^* \times A^* \to \{0, 1\}$ przez $f_L(x, y) = 1$ iff $x\cdot y \in L$ . Szukam referencji dla:

Propozycja. $L$ jest regularna w deterministycznej złożoności komunikacji $f_L$ jest stały.

Innymi słowy, $L$ jest normalny iff istnieje protokół dla dwóch graczy $P$ dla $f_L$ takie, że funkcja

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

$n \mapsto \max\{\text{comm}(P, x, y) : |x\cdot y| = n\}$ ograniczona jest przez stały, w którym to liczba bitów wymieniane przez Alicja i Bob gdy Alicja otrzymuje i Bob , postępując zgodnie z procedurą .

comm (P, x, y)

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

x

$x$

y

$y$

P

$P$

Jedyne miejsce, jakie udało mi się znaleźć, to praca doktorska George'a Hausera z 1989 roku, dostępna tutaj , gdzie uogólnia on również na inne rozkłady pomiędzy Alice i Bobem, tak że liczba „cięć” jest stała. $x\cdot y$

reference-request communication-complexity regular-language Michaël Cadilhac
źródło

Weź język który nie jest regularny, i zdefiniuj . Wtedy ma złożoność komunikacyjną , ale z pewnością nie jest regularna. czego mi brakuje?

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: Nie jestem pewien, czy dostaję dokładnie to, co tam napisałeś, ale wydaje ci się, że sugerujesz klasyczny dowód, że każdy język z jednym słowem na długość można przekształcić w język o stałej złożoności komunikacyjnej. Zakłada się jednak, że Alice i Bob otrzymują dokładnie połowę testowanego słowa; tutaj nie ma takiego założenia i, w sposób kontradyktoryjny, powinni rozwiązać problem, biorąc pod uwagę jakikolwiek podział danych wejściowych. Czy to jest odpowiedź na Twoje pytanie?

Michaël Cadilhac,

Rozumiem. Więc jeśli dla dowolnego podziału CC jest stały, to jest regularny.

L

$L$

Igor Shinkar,

Odpowiedzi:

W przypadku masz „złożoność komunikacji”, Eyal Kushilevitz in Advances in Computers, tom 44, 1997 ( http://www.sciencedirect.com/science/article/pii/S0065245808603423 ). $\Rightarrow$

Sekcję „Złożoność komunikacji i hierarchia Chomsky'ego” można także znaleźć w książce „Złożoność komunikacji i obliczenia równoległe” Juraja Hromkoviča, w której jest to udowodnione. Być może jest również udowodniony gdzieś w książce, ale nie mogę go tutaj znaleźć. Wydaje się, że najbliższą rzeczą jest Ćwiczenie 5.2.5.2, ale jest to tylko ćwiczenie (patrz także cały Rozdział 5, który dogłębnie studiuje automat skończony, ale nie sądzę, aby wyraźnie odpowiadał na twoje pytanie). $\Leftarrow$

Jeśli chodzi o to, co jest warte, dowód obu kierunków wydaje się łatwy, więc myślę, że jeśli potrzebujesz go w papierze, możesz go szybko naszkicować: w przypadku , weź skończony automat do i zauważ, że wystarczy Alice stan, który osiąga po przeczytaniu swojej części danych wejściowych. Następnie Bob kończy symulację w automatach. Dla , jeśli masz protokół ograniczony stałą, to ma skończoną liczbę ilorazów co jest dobrze znaną charakterystyką zwykłych języków . $\Rightarrow$ $L$ $\Leftarrow$ $L$ $w^{-1}L = \{u : wu \in L\}$

holf
źródło

Dziękuję bardzo za Twój wkład. Zgadzam się, że jest to wynik łatwy i naturalny, i prawdopodobnie należy go uważać za folklor. Znam dwa odniesienia, które podajesz całkiem dobrze, i tak jak ty, nie mogłem znaleźć w nim protokołu, który rozważam powyżej. Ponieważ to pytanie jest „prośbą o referencje”, obawiam się, że nie mogę w tej chwili zaakceptować Twojej odpowiedzi.

Michaël Cadilhac

Wiem, ale było za długo na komentarz i myślę, że nadal warto wspomnieć, że przynajmniej jeden sposób został wyraźnie potwierdzony w literaturze. Daję ci znać, jeśli natknę się na dowód!

holf

Bardzo doceniony! :-)

Michaël Cadilhac