LogDCFL-vollständige Probleme

LogCFL ist die Menge aller Sprachen, deren Logspace auf eine kontextfreie Sprache reduziert werden kann. Ebenso ist LogDCFL die Menge aller Sprachen, deren Logspace auf eine deterministische kontextfreie Sprache reduziert werden kann. In diesem Wikipedia-Artikel finden Sie einige natürliche LogCFL-vollständige Probleme. Es gibt einige andere interessante LogCFL-vollständige Probleme. Ich konnte keine natürlichen LogDCFL-vollständigen Probleme finden. Nennen Sie ein beliebiges natürliches LogDCFL-vollständiges Problem.

cc.complexity-theory complexity-classes Shiva Kintali
quelle

Darf ich aus Neugier fragen, warum Sie sich für LogDCFL interessieren?

Michaël Cadilhac

Ich interessiere mich allgemein für raumgebundene Berechnungen und versuche LogDCFL zu verstehen.

Shiva Kintali

Antworten:

Bei der folgenden Sprache handelt es sich um eine geringfügige Änderung der üblichen vollständigen LogCFL-Sprache, sodass es sich um eine vollständige LogDCFL-Sprache handelt. Der Beweis findet sich in Sudboroughs On the Tape Complexity of Deterministic Context-Free Languages.

Sei und . Die folgende Sprache über ist LogDCFL-vollständig. besteht aus den Wörtern $\Sigma = \{(_1,(_2,)_1, )_2\}$ $T = \{[,],|\}$ $\Sigma \cup T$ $L$ , wo sodass es existiert mit oder für alleund ist in Klammern richtig.

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
quelle