Problemy z logDCFL-complete

LogCFL to zestaw wszystkich języków, które można sprowadzać do przestrzeni logicznej do języka bezkontekstowego. Podobnie LogDCFL jest zbiorem wszystkich języków, które są przestrzenią logiczną redukowalną do deterministycznego języka bezkontekstowego. Zobacz ten artykuł na Wikipedii, aby zapoznać się z niektórymi naturalnymi problemami związanymi z logCFL. Istnieje kilka innych interesujących problemów z LogCFL. Nie mogłem znaleźć żadnych naturalnych problemów z logDCFL. Nazwij każdy naturalny problem z logDCFL.

cc.complexity-theory complexity-classes Shiva Kintali
źródło

Z ciekawości mogę zapytać, dlaczego jesteś zainteresowany LogDCFL?

Michaël Cadilhac

Interesuję się ogólnie obliczeniami ograniczonymi przestrzenią i próbuję zrozumieć LogDCFL.

Shiva Kintali,

Odpowiedzi:

Poniższy język jest drobną modyfikacją zwykłego kompletnego LogCFL, tak że jest kompletny LogDCFL. Dowód można znaleźć w Sudborough's On the Tape Complexity of Deterministic Context-Lext Languages.

$\Sigma = \{(_1,(_2,)_1, )_2\}$ $T = \{[,],|\}$ $\Sigma \cup T$ $L$

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
źródło