Problèmes liés à LogDCFL

LogCFL est l'ensemble de toutes les langues qui sont réductibles en espace de journalisation en une langue sans contexte. De même, LogDCFL est l'ensemble de toutes les langues qui sont un espace de journalisation réductible à une langue déterministe sans contexte. Consultez cet article de wikipedia pour certains problèmes naturels liés à LogCFL. Il existe plusieurs autres problèmes intéressants liés à LogCFL. Je n'ai pas pu trouver de problèmes naturels complets avec LogDCFL. Nommez tout problème naturel lié à LogDCFL.

cc.complexity-theory complexity-classes Shiva Kintali
la source

Par curiosité, puis-je vous demander pourquoi vous êtes intéressé par LogDCFL?

Michaël Cadilhac

Je m'intéresse au calcul borné à l'espace en général et j'essaie de comprendre LogDCFL.

Shiva Kintali

Réponses:

Le langage suivant est un léger ajustement de l'habituel LogCFL complet pour qu'il soit LogDCFL complet. La preuve peut être trouvée dans la complexité de la bande de Sudborough des langues déterministes sans contexte.

Soit et . La langue suivante sur est complète avec LogDCFL. compose des mots $\Sigma = \{(_1,(_2,)_1, )_2\}$ $T = \{[,],|\}$ $\Sigma \cup T$ $L$ où tel qu'il existe avec ou pour toutet est entre parenthèses correct.

w_{0} [(_{1} l_{1} | (_{2} r_{1}] \dots [(_{1} l_{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
la source