LogDCFL-полные проблемы

LogCFL - это набор всех языков, пространство логирования которых сводится к языку без контекста. Аналогично, LogDCFL - это набор всех языков, пространство логирования которых сводится к детерминированному контекстно-свободному языку. Смотрите эту статью в Википедии, чтобы узнать о некоторых естественных проблемах, связанных с LogCFL. Есть несколько других интересных LogCFL-полных проблем. Я не смог найти никаких естественных LogDCFL-полных проблем. Назовите любую естественную LogDCFL-полную проблему.

cc.complexity-theory complexity-classes Шива Кинтали
источник

Из любопытства могу ли я спросить, почему вы заинтересованы в LogDCFL?

Михаэль Кадилхак

Я заинтересован в ограниченных в пространстве вычислениях в целом и пытаюсь понять LogDCFL.

Шива Кинтали

Ответы:

Следующий язык представляет собой небольшую настройку обычного завершенного LogCFL, поэтому он завершает LogDCFL. Доказательство можно найти в книге «Сложность детерминированных контекстно-свободных языков».

Пусть и . Следующий язык над является LogDCFL-полным. состоит из слов $\Sigma = \{(_1,(_2,)_1, )_2\}$ $T = \{[,],|\}$ $\Sigma \cup T$ $L$ где такое, что существует с или для всехи в скобках правильно.

{вес}_{0} [(_{1} L_{1} | (_{2} р_{1}] ... [(_{1} L_{N} | (_{2} р_{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$

Михаэль Кадилхак
источник