Regelmäßige Sprachen und ständige Kommunikationskomplexität

Let eine Sprache sein, und definiert von genau dann , wenn . Ich suche eine Referenz für: $L \subseteq A^*$ $f_L\colon A^* \times A^* \to \{0, 1\}$ $f_L(x, y) = 1$ $x\cdot y \in L$

Vorschlag. ist regelmäßig, wenn die deterministische Kommunikationskomplexität von konstant ist. $L$ $f_L$

Mit anderen Worten, ist regulär, wenn es ein Zwei-Spieler-Protokoll für so dass die Funktion wird durch eine Konstante begrenzt, wobei die Anzahl der von Alice und Bob ausgetauschten Bits ist, wenn Alice und Bob gemäß dem Protokoll empfängt $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$ .

Der einzige Ort, den ich finden konnte, ist in George Hausers Doktorarbeit von 1989, die hier verfügbar ist , wo er dies auch auf andere Verteilungen der Eingabe unter Alice und Bob verallgemeinert , so dass die Anzahl der "Schnitte" konstant ist. $x\cdot y$

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

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

@IgorShinkar: Ich bin nicht sicher, ob ich genau das bekomme, was Sie dort geschrieben haben, aber Sie scheinen auf den klassischen Beweis hinzuweisen, dass jede Sprache mit einem einzelnen Wort pro Länge in eine Sprache mit konstanter Kommunikationskomplexität umgewandelt werden kann. Dies setzt jedoch voraus, dass Alice und Bob genau die Hälfte des getesteten Wortes erhalten. hier gibt es keine solche Annahme und, im Wege eines so, sollten sie das Problem gegeben lösen jede Spaltung des Eingangs. Beantwortet das deine Frage?

Michaël Cadilhac

L

$L$

Antworten:

$\Rightarrow$

$\Leftarrow$

$\Rightarrow$ $L$ $\Leftarrow$ $L$ $w^{-1}L = \{u : wu \in L\}$

holf
quelle

Vielen Dank für Ihre Eingabe. Ich stimme zu, dass es ein einfaches und ein natürliches Ergebnis ist und wahrscheinlich als Folklore betrachtet werden sollte. Ich kenne die beiden Referenzen, die Sie geben, tatsächlich recht gut und konnte, genau wie Sie, das Protokoll, das ich oben in Betracht ziehe, darin nicht finden. Da es sich bei dieser Frage um eine "Referenzanfrage" handelt, kann ich Ihre Antwort an dieser Stelle leider nicht akzeptieren.

Michaël Cadilhac

Ich weiß, aber es war zu lang für einen Kommentar und ich denke, es war immer noch erwähnenswert, dass mindestens ein Weg in der Literatur explizit bewiesen ist. Ich lasse Sie wissen, wenn ich über den Beweis stolpere!

Holf

Sehr geschätzt! :-)

Michaël Cadilhac