Referencia para los idiomas Dyck siendo

12

Los idiomas Dyck se definen mediante la siguiente gramática $\mathsf{Dyck}(k)$ sobre el conjunto de símbolos . Intuitivamente, los idiomas Dyck son los idiomas de paréntesis equilibrados de tipos diferentes. Por ejemplo,

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$

está en

pero

([]) ()

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

D y c k (2)

$\mathsf{Dyck}(2)$

no lo es.

([)]

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

En el papel

Algoritmos dinámicos para las lenguas Dyck por Frandsen, Husfeldt, Miltersen, Rauhe y Skyum, 1995,

Se afirma que el siguiente resultado es el folklore:

es -completo bajo lasreducciones de . $\mathsf{Dyck}(k)$ $\mathsf{TC}_0$ $\mathsf{AC}_0$

¿Hay alguna referencia conocida para el reclamo anterior? En particular, estoy buscando resultados que muestren al menos uno de los siguientes:

está en para arbitrario. $\mathsf{Dyck}(k)$ $\mathsf{TC}_0$ $k$
es -duro para arbitrario. $\mathsf{Dyck}(k)$ $\mathsf{TC}_0$ $k$

El papel más cercano que puedo encontrar es

Bi-Lipschitz Bijection entre el Boolean Cube y el Hamming Ball , por Benjamini, Cohen y Shinkar, 2013

lo que me redirige al documento Reconocimiento del espacio de registro y traducción de los idiomas entre paréntesis por Lynch, quien demostró que (es decir, paréntesis equilibrados normales) está en . $\mathsf{Dyck}(1)$ $\mathsf{TC_0}$

Todos los documentos relacionados son bienvenidos también. ¡Gracias!

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

5

$\mathsf{NC}^1$

SamiD
fuente

6

$AC_0$ $\rm Majority$ $Dyck(1)$ $\rm Majority$ $AC_0$ $Dyck(k)$ $k \geq 1$ $AND$ $OR$ $NOT$ $Dyck(1)$

$x \in \{0,1\}^n$ $\rm Majority$
$y \in \{0,1\}^{2n}$ $0$ $(($ $1$ $()$
$i = 1,\dots, n/2$ $z_i$ $y$ $2i$ $z_i = y \circ )^{2i}$
$z_i \in Dyck(1)$ $i = 1,\dots, n/2$

$z_i$ $OR$

$\rm Majority$ $z_i \in Dyck(1)$ ${\rm weight}(x) = n - i$

Igor Shinkar
fuente

Gracias. ¿Conoces algún papel que contenga el resultado anterior? (Está bien si el documento no es el original / más temprano, estoy tratando de rastrear la historia).

Hsien-Chih Chang 張顯之

Hmmm ... por alguna razón supuse que apareció una reducción similar en ese papel de Lynch ... No conozco ninguna otra referencia para esto.

Igor Shinkar

Referencia para los idiomas Dyck siendo

Respuestas: