Referenz für Dyck-Sprachen ist

12

Dyck-Sprachen durch die folgende Grammatik $\mathsf{Dyck}(k)$ über der Menge der Symbole . Intuitiv sind Dyck-Sprachen die Sprachen der ausgeglichenen Klammern von

S \to S S | (_{1} S)_{1} | \dots | (_{k} S)_{k} | ϵ

$S \rightarrow SS \,|\, (_1 S )_1 \,|\, \ldots \,|\, (_k S )_k \,|\, \epsilon$

{(_{1}, \dots, (_{k},)_{1}, \dots,)_{k}}

$\{(_1,\ldots,(_k,)_1,\ldots,)_k\}$

k

$k$ anderer Art. Zum Beispiel

ist in

aber

([]) ()

$(\,[\,]\,)\,(\,)$

D y c k (2)

$\mathsf{Dyck}(2)$

([)]

$(\,[\,)\,]$ ist nicht.

In der Zeitung

Dynamische Algorithmen für die Dyck-Sprachen von Frandsen, Husfeldt, Miltersen, Rauhe und Skyum, 1995,

Es wird behauptet, dass das folgende Ergebnis Folklore ist:

ist -komplett unter -Reduktionen. $\mathsf{Dyck}(k)$ $\mathsf{TC}_0$ $\mathsf{AC}_0$

Gibt es eine bekannte Referenz für den obigen Anspruch? Insbesondere suche ich nach Ergebnissen, die mindestens eine der folgenden Eigenschaften aufweisen:

ist in für beliebiges . $\mathsf{Dyck}(k)$ $\mathsf{TC}_0$ $k$
ist -hart für beliebiges . $\mathsf{Dyck}(k)$ $\mathsf{TC}_0$ $k$

Das nächste Papier, das ich finden kann, ist

Bi-Lipschitz-Bijektion zwischen dem Booleschen Würfel und dem Hamming Ball , von Benjamini, Cohen und Shinkar, 2013

Das leitet mich zu dem Artikel Log Space Recognition and Translation of parenthesis languages von Lynch weiter, der bewies, dass (dh normal ausgeglichene Klammern) in . $\mathsf{Dyck}(1)$ $\mathsf{TC_0}$

Alle verwandten Artikel sind ebenfalls willkommen. Vielen Dank!

reference-request fl.formal-languages circuit-complexity ho.history-overview context-free Hsien-Chih Chang 張顯張顯
quelle

5

Siehe „Auf der relative Komplexität einiger Sprachen in von Barrington, Corbett $\mathsf{NC}^1$

SamiD
quelle

6

Hier ist eine -Reduktion von zu . (Das bedeutet , dass ist reduzierbar für alle ). Um dies zu tun, konstruieren wir eine poly-Größe konstante Tiefe Schaltung , deren Gates $AC_0$ $\rm Majority$ $Dyck(1)$ $\rm Majority$ $AC_0$ $Dyck(k)$ $k \geq 1$ $AND$ , , und $OR$ $NOT$ . $Dyck(1)$

Gegeben sei eine Instanz von $x \in \{0,1\}^n$ $\rm Majority$ do ist
Berechnen Sie indem Sie jede durch und jede durch ersetzen. $y \in \{0,1\}^{2n}$ $0$ $(($ $1$ $()$ .
Nun für jedes Es sei werden der String durch Verketten erhaltenen mit -many Schließ Klammern, also . $i = 1,\dots, n/2$ $z_i$ $y$ $2i$ $z_i = y \circ )^{2i}$
Wenn für einige dann AKZEPTIEREN. Ansonsten ABLEHNEN. $z_i \in Dyck(1)$ $i = 1,\dots, n/2$

Dies kann eindeutig mit einer Schaltung mit konstanter Tiefe erfolgen. (Rechnen $z_i$ 1 in der Tiefe durchgeführt werden kann, und Berechnen der letzte Schritt wird eine geschieht mit - Gate) . $OR$

Es ist auch leicht zu sehen, dass diese Schaltung tatsächlich berechnet, weil genau dann, wenn . $\rm Majority$ $z_i \in Dyck(1)$ ${\rm weight}(x) = n - i$

Igor Shinkar
quelle

Vielen Dank. Kennen Sie Papier, das das obige Ergebnis enthält? (Es ist in Ordnung, wenn das Papier nicht das Original / früheste ist, ich versuche, die Geschichte zurückzuverfolgen.)

Hsien-Chih Chang 張顯張顯

Hmmm ... aus irgendeinem Grund bin ich davon ausgegangen, dass in diesem Artikel von Lynch eine ähnliche Reduktion aufgetaucht ist ... Ich kenne keine andere Referenz dafür.

Igor Shinkar

Referenz für Dyck-Sprachen ist

Antworten: