Полнота и контекстно-зависимые языки.

Меня интересуют два вопроса относительно контекстно-зависимых языков (CSL) и полноты:

Существует ли понятие полноты для CSL и какие языки являются законченными?
Существуют ли естественные CSL, которые являются NP-полными?

Для 2. я, конечно, могу думать о естественных NP-полных языках, которые являются CSL (так как CSL равен NSPACE [ ], SAT - CSL), но я ищу другой путь, то есть контекст- чувствительная грамматика, описывающая NP-полный язык. $n$

np-hardness fl.formal-languages space-bounded Михаэль Кадилхак
источник

Давайте посмотрим, правильно ли я понимаю (2): будет ли достаточно написать контекстно-зависимую грамматику, которая генерирует все допустимые экземпляры 3SAT по фиксированному алфавиту связующих и переменных SAT?

Евгений Торстенсен

Ну, я бы не добавил переменные SAT как часть алфавита (двоичное кодирование их индексов достаточно хорошее), но это, безусловно, ответило бы на мой второй вопрос!

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

Кстати, ты попробовал?

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

(1) Как вы упомянули, можно записать CSG для 3SAT, но это похоже на запись полного описания машины Тьюринга для задачи максимального потока (или любого конкретного языка в P); Я не ожидал бы, что это даст какое-либо понимание теории сложности. (Но, эй, если получится иначе, я буду рад это услышать.) (2) Как правило, понятие контекстно-зависимой грамматики и понятие NP-полноты не сочетаются друг с другом, потому что набор контекстно-зависимых языки не закрыты при сокращении за полиномиальное время.

Цуёси Ито

Спасибо за этот комментарий Tsuyoshi. Действительно, грамматика для 3SAT, вероятно, не то, что я ищу, но я пошел с той же реакцией, что и ваша: если это будет несколько легко / естественно, мне было бы интересно. Для вашего (2), одна из моих целей заключается в следующем: скажем, у меня есть класс языков CS, закрытый сокращением пространства журналов, и я хочу показать, что мой класс не содержит (или вряд ли) содержит проблемы, полные NP, Мне бы только нужно было показать, что конкретный язык CS, полный NP, отсутствует в моем классе, что может быть проще, если язык, естественно, CS.

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

Ответы:

Чтобы ответить на ваш первый вопрос, сводимость, отвечающая вашим потребностям, - это log-lin-reducibility, то есть сводимость logspace с дополнительным ограничением, заключающимся в том, что размер выходной строки сокращения не более линейен по размеру входных данных. Если я правильно помню, проблема членства для контекстно-зависимых грамматик (или, если хотите, линейно ограниченных автоматов) - это каноническая CSL-полная проблема относительно лог-линейной сводимости.

С прикладной стороны, проблема универсальности (обычных) регулярных выражений над двоичным алфавитом является CSL-полной относительно log-lin-приводимости. Понятие и результат полноты найдены также у Альберта Р. Мейера и Ларри Дж. Стокмейера (SWAT 1972): Stockmeyer (кандидатская диссертация, MIT 1974). Дополнительную информацию и аналогичные результаты в этой области см. Также в недавнем опросе Хольцера и Кутриба (DLT 2010).

РЕДАКТИРОВАТЬ (2017/03/06): Что касается вашего второго вопроса, в качестве принятого ответа на приведенный ниже вопрос цитируется статья Раунда (1973 г.), в которой создается односторонний автомат с вложенными стеками, распознающий SAT. Хотя SAT не будет квалифицироваться как «естественный» CSL, возможно, стоит поискать в литературе другие примеры автоматов с односторонним вложенным стеком или индексированных грамматик.

Контекстно-зависимая грамматика для SAT?

Герман Грубер
источник

Большое спасибо, это действительно то, что я искал!

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

Для редактирования: Фантастика! Спасибо, что вернулись и ответили на этот вопрос, это отличный дух!

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