LogDCFL-complete problemas

LogCFL es el conjunto de todos los idiomas que son logspace reductibles a un lenguaje sin contexto. Del mismo modo, LogDCFL es el conjunto de todos los lenguajes que son espacio de registro reducible a un lenguaje determinista sin contexto. Vea este artículo de Wikipedia para algunos problemas naturales completos de LogCFL. Hay varios otros problemas interesantes de LogCFL-complete. No pude encontrar ningún problema natural de LogDCFL-complete. Nombre cualquier problema natural de LogDCFL-complete.

cc.complexity-theory complexity-classes Shiva Kintali
fuente

Por curiosidad, ¿puedo preguntar por qué está interesado en LogDCFL?

Michaël Cadilhac

Estoy interesado en la computación limitada en el espacio en general e intento entender LogDCFL.

Shiva Kintali

Respuestas:

El siguiente lenguaje es un pequeño retoque del habitual LogCFL complete para que sea LogDCFL complete. La prueba se puede encontrar en la Complejidad On the Tape de Sudborough de lenguajes deterministas sin contexto.

Deje y . El siguiente lenguaje sobre es LogDCFL-complete. consta de palabras $\Sigma = \{(_1,(_2,)_1, )_2\}$ $T = \{[,],|\}$ $\Sigma \cup T$ $L$ donde

w_{0 0} [(_{1} l_{1} El | (_{2} r_{1}] ... [(_{1} l_{norte} El | (_{2} r_{norte}]

$w_0\left[(_1l_1|(_2r_1\right]\ldots\left[(_1l_n|(_2r_n\right]$

tal que exista

con

para todo

es paréntesis correcto.

w_{0}, l_{i}, r_{i} \in Σ^{*}

$w_0, l_i, r_i \in \Sigma^*$

w_{1}, \dots, w_{n}

$w_1, \ldots, w_n$

w_{i} = (_{1} l_{i}

$w_i = (_1l_i$

w_{i} = (_{2} r_{i}

$w_i = (_2r_i$

i \geq 1

$i \geq 1$

w_{0} w_{1} \dots w_{n}

$w_0w_1\ldots w_n$

Michaël Cadilhac
fuente