Problemas com o LogDCFL

LogCFL é o conjunto de todos os idiomas com espaço de log redutível para um idioma sem contexto. Da mesma forma, LogDCFL é o conjunto de todos os idiomas com espaço de log redutível para um idioma sem contexto determinístico. Consulte este artigo da Wikipedia para alguns problemas naturais completos do LogCFL. Existem vários outros problemas interessantes completos do LogCFL. Não foi possível encontrar nenhum problema natural com o LogDCFL. Nomeie qualquer problema completo com LogDCFL natural.

cc.complexity-theory complexity-classes Shiva Kintali
fonte

Por curiosidade, posso perguntar por que você está interessado no LogDCFL?

Michaël Cadilhac

Estou interessado em computação limitada por espaço em geral e tentando entender o LogDCFL.

Shiva Kintali

Respostas:

O idioma a seguir é um pequeno ajuste do normal do LogCFL completo, para que ele seja completo do LogDCFL. A prova pode ser encontrada na complexidade da fita de línguas determinísticas, livre de contexto, de Sudborough.

Seja e . O seguinte linguagem sobre é LogDCFL-completo. consiste em palavras $\Sigma = \{(_1,(_2,)_1, )_2\}$ $T = \{[,],|\}$ $\Sigma \cup T$ $L$ , onde tal que existe com ou para todos ose está entre parênteses.

W_{0 0} [(_{1 1} {eu}_{1 1} | (_{2} r_{1 1}] ... [(_{1 1} {eu}_{n} | (_{2} r_{n}]

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

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
fonte