Определение пустоты пересечения регулярных языков в субквадратичном времени

23

Пусть L1,L2 будут двумя обычными языками, заданными NFA M1,M2 качестве входных данных.

Предположим, мы хотели бы проверить, является ли L1L2 . Это можно сделать с помощью квадратичного алгоритма, который вычисляет автомат произведений M1,M2 , но мне было интересно, известно ли что-нибудь более эффективное.

Существует ли алгоритм o(n2) для определения того, является ли L1L2 ? Какой самый быстрый известный алгоритм?

RB
источник
5
Если у кого-то есть хорошие идеи, пожалуйста, дайте мне знать, но в настоящее время это открытая проблема. Если бы вы могли решить эту проблему, скажем, за линейное время, то в принципе любая проблема, решаемая недетерминированной машиной, использующей только n бит памяти, могла бы быть решена детерминистически за раза. 2n2
Майкл Вехар
6
Я думаю, что это все еще открыто для любого субквадратичного. Немного больше информации: rjlipton.wordpress.com/2009/08/17/…
Майкл Вехар
4
Так, например (основываясь на комментарии Майкла), гипотеза сильного экспоненциального времени подразумевает, что показатель степени должен быть равен 2. Я думаю, что это также может оказаться следствием гипотезы экспоненциального времени ...
Райан Уильямс
4
RB: Предположим, что вы можете проверить на пустоту два DFA размера за время n 1 + ε с ε < 1 . Теперь, если у вас есть k DFA размера n , вы можете создать произведение первых k / 2 DFA и оставшихся k / 2 DFA. Затем проверьте пустоту во времени ( n k / 2 ) 1 + ε = n 1nn1+εε<1knk/2k/2что лучше, чемnk. vzn: Эта отмеченная наградами статья была написана @MichaelWehar, который прокомментировал эту ветку. Майкл, возможно, ты мог бы представить ответ, если у тебя есть время! (nk/2)1+ε=n12k+ε2knk
Михаил Блондин
4
@RyanWilliams Привет, Райан, что заставляет вас думать, что более слабая экспоненциальная гипотеза времени подразумевает, что мы не можем решить не пустоту пересечения для двух DFA быстрее? Кто-то еще предложил мне это тоже. :)
Майкл Вехар

Ответы:

22

Простой ответ : если существует более эффективный алгоритм, который выполняется за время для некоторого δ < 2 , то гипотеза о сильном экспоненциальном времени будет опровергнута.O(nδ)δ<2


Мы докажем более сильную теорему, и тогда последует простой ответ.

Теорема : если мы сможем решить проблему непустоты пересечения для двух DFA за времени, то любая проблема, которая недетерминированно разрешима с использованием только n битов памяти, детерминированно разрешима в p o l y ( n ) 2 ( δ н / 2 ) раз.O(nδ)poly(n)2(δn/2)

Обоснование : Предположим, что мы можем решить не пустоту пересечения для двух DFA за времени. Пусть дана недетерминированная машина Тьюринга M с входной лентой только для чтения и двоичной рабочей лентой для чтения / записи. Пусть задана входная строка x длины n. Предположим, что M не имеет доступа к более чем n битам памяти на двоичной рабочей ленте.O(nδ)

Вычисление M на входе x может быть представлено конечным списком конфигураций. Каждая конфигурация состоит из состояния, позиции на входной ленте, позиции на рабочей ленте и до n бит памяти, которые представляют рабочую ленту.

Теперь учтите, что рабочая лента была разделена пополам. Другими словами, у нас есть левая часть ячейки и правая частьпn2 кл. Каждая конфигурация может быть разбита на левую часть и правую часть. Левая часть состоит из состояния, положения на входной ленте, положения на рабочей ленте иnn2 бита из левого раздела. Правая часть состоит из состояния, положения на входной ленте, положения на рабочей ленте иn.n2 бита из правого раздела.n2

Теперь мы создаем DFA чьи состояния - это левые части, и DFA D 2, чьи состояния - это правильные части. Буквенные символы - это инструкции, в которых указано, в какое состояние переходить, как должны двигаться головки ленты и как следует манипулировать активной ячейкой рабочей ленты.D1D2

Идея состоит в том, что и D 2 читают в списке инструкций, соответствующих вычислению M на входе x, и вместе проверяют, что он действителен и принимает. И D 1, и D 2 всегда будут согласовывать расположение головок магнитных лент, поскольку эта информация включена в их символы ввода. Следовательно, мы можем сделать так, чтобы D 1 проверял, что инструкция подходит, когда положение рабочей ленты находится в левой части, а D 2 проверяет, когда в правой части.D1D2D1D2D1D2

poly(n)2n/2poly(n)

poly(n)2(δn/2)

Вы можете найти это полезным: https://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/


k+O(log(n))O(nδ)poly(n)2(δk/2)

Комментарии, исправления, предложения и вопросы приветствуются. :)

Майкл Вехар
источник
1
Ω(n2)
1
kk
1
(2k2)k
1
NSpace(2log(n))DTime(n)NSpace(2log(n))2log(n)пространство для недетерминированных машин Тьюринга с двусторонней ленточной записью только для чтения и двусторонней ленточной записью для чтения / записи.
Майкл Вехар