Сложность проверки, если два слова имеют чередование в языке

9

Для фиксированного языка L на каком-то алфавите A, давайте рассмотрим следующую проблему, которую я называю L-Интерлевинг :

  • Вход: два слова u,vA
  • Вывод: существует ли там перемежения изu а также v который в L,

Здесь чередование двух словu а также v это слово w что можно получить интуитивно, взяв буквы u а также vсохраняя их относительный порядок. Формально,w это чередование u а также v если мы можем разделить его на две непересекающиеся подпоследовательности, одна из которых равна u а другой, который равен v, Например, «bheleloll» - это чередование «привет» и «звонок».

Какова сложность L-Взаимодействие проблемы, в зависимости от языка L? В частности:

  • Если Lрегулярный, то мы можем решить задачу с помощью динамического алгоритма на двух строках, который показывает, что он находится в классе NL. Нелегко ли это для некоторых обычных языков? Однако для некоторых обычных языков проблема явно в L (детерминированное пространство журналов). Есть ли какая-то характеристика языков, для которых проблема в L?
  • Если L не регулярно, проблема все еще в NL, когда Lимеет полиномиальную онлайн детерминированную сложность пространства (см. здесь это понятие или мой предыдущий вопрос ). Однако это не распространяется, например, на все контекстно-свободные языки; тем не менее, некоторые другие (например, палиндромы) также могут быть показаны как NL (например, путем выполнения динамического алгоритма одновременно с начала и с конца). Есть ли контекстно-свободный язык, чейL-перемежение проблемы NP-трудно?
a3nm
источник

Ответы:

6

За слово w=w1w и для двух целых i,j с 1ij мы обозначаем через w(i,j) подслово wiwi+1wj из w, Кроме того, мы позволяемw(0,0) обозначить пустое слово.

  • Позволять u=u1um а также v=v1vn быть два слова на рассмотрении.
  • Предположим, что контекстно-свободный язык L задается контекстно-свободной грамматикой в ​​нормальной форме Хомского.

Построить динамическую программу, где государство [i,j,r,s,A] определяется

  • два целых числа i,j с 1ijm или i=j=0
  • два целых числа r,s с 1rsn или r=s=0
  • нетерминальный символ A в контекстно-свободной грамматике

Для каждого состояния определите, существует ли в контекстно-свободной грамматике какой-либо вывод, начинающийся с нетерминала A и это заканчивается некоторым чередованием двух слов u(i,j) а также w(r,s), Это решение может быть легко принято, если состояния обрабатываются в правильном порядке (короткие подслова перед более длинными подсловами).

В общем, это дает алгоритм полиномиального времени для Lпроблема чередования любых контекстно-свободных языков L,

Гамов
источник
Спасибо! Действительно, я не заметил, что этот вариант en.wikipedia.org/wiki/CYK_algorithm будет работать, чтобы показать, что проблема в P для языков без контекста. Тем не менее, мы не видим, как показать, что проблема заключается в NL с использованием этого алгоритма: нам, кажется, нужно сделать логарифмическое число догадок (высоту дерева), причем каждое предположение является логарифмическим (то есть позиции в строка). Есть идеи по этому поводу?
17
2
@ a3nm принадлежит ли пустое слово к КЛЛ, P-hard.
Сильвен
@Sylvain: ОК, это P-hard, но как функция CFL. :) Помните, что в моей задаче язык (или CFL для него) является фиксированным, и входные данные представляют собой только две строки, поэтому я не думаю, что этот аргумент применим.
3
2
@ a3nm извините, я действительно пропустил тот факт, что язык был исправлен. Тогда естественным кандидатом будет LogCFL-твердость.
Сильвен
@Sylvain: Это верно, спасибо! Так что, на самом деле, я предполагаю, что проблема слова сложна в LogCFL даже для фиксированного языка CFL (т. Е. Самого сложного языка Грейбаха), поэтому, в частности, существуют языки CFL, для которых моя проблема сложна в LogCFL (возьмем случаи, когда вторая строка пуста). ). Наоборот, я представляю, что алгоритм Гамова находится в LogCFL (?). Тем не менее, это заставляет меня задуматься о языках, для которых моя проблема будет проще, чем эта граница, и о том, как их можно классифицировать ...
a3nm