DFA пересечение в субквадратичном пространстве?

25

Пересечение двух (минимальных) DFA с n состояниями может быть вычислено с использованием O (n ² ) времени и пространства. В общем, это оптимально, поскольку результирующий (минимальный) DFA может иметь n ² состояний. Однако, если результирующий минимальный DFA имеет z состояний, где z = O (n), можно ли его вычислить в пространстве n ^2-eps для некоторой константы eps> 0? Я был бы заинтересован в таком результате даже для особого случая, когда входные DFA являются ациклическими.

automata-theory dfa Расмус Паг
источник

3

Гм ... если два DFA с n-состояниями являются ациклическими, то каждое из них просто принимает конечный набор слов длиной не более n, и в этом случае их пересечение является просто пересечением двух помеченных графов переходов, которые будут иметь n состояний и может быть вычислено в линейном времени и пространстве. Или я что-то упустил?

Джошуа Грохов

4

Да, ациклические DFA принимают только конечный набор слов. Но есть примеры ациклических DFA, чье пересечение имеет размер n ^ 2. Например, подумайте об одном DFA, который принимает строки в форме AABC (где ABC - строки длины k), и о том, который принимает строки в форме ABCC.

Расмус Паг

1

retagging: cs.cc является обозначением arxiv, поэтому указанным тегам не нужен префикс cs.cc.

Суреш Венкат

15

Ответ - да, без каких-либо требований к размеру автомата. Его можно вычислить в пространстве $O(\log^2 n)$ даже для DFA, где - это константа. $k$ $k$

Пусть ( будет DFA. Мы показываем, что с учетом вычисление минимального распознавания DFA может быть выполнено в пробел. Сначала докажем некоторые технические результаты. $A_i = (Q_i, \Sigma_i, \delta_i, z_i, F_i)$ $i \in [k])$ $k$ $\langle A_1, \ldots, A_k \rangle$ $\text{L}(A_1) \cap \cdots \cap\text{L}(A_k)$ $O(\log^2 n)$

Определение 1 : Пусть два состояния, тогда если , $q, r$ $q \equiv r$ $\forall w \in \Sigma^*$ $q . w \in F \Leftrightarrow r . w \in F$

Теперь рассмотрим автомат заданный классической декартовой конструкцией произведений. Пусть и быть состояния . $A$ $q = (q_1, \ldots, q_k)$ $r = (r_1, \ldots, r_k)$ $A$

Лемма 1 : Решаем, находится ли в NL. $q \equiv r$

Доказательство (набросок): мы показываем, что проверка неэквивалентности находится в NL, и используем NL = coNL. Угадай слово (одна буква за раз), такое что является конечным состоянием и не Это может быть достигнуто путем вычисления в лог-пространстве для и использования того факта, что является конечным, если . Можно показать, что влечет существование поли-размера. $w \in \Sigma^*$ $q . w$ $r . w$ $q_i . w, r_i . w$ $i \in [k]$ $q$ $q_i \in F_i \, \forall i \in [k]$ $q \not\equiv r$ $w$

Лемма 2 : Решение о том, является ли доступным, находится в NL. $q$

Доказательство (эскиз): угадать (полиразмер) пути от до ( ). $z_i$ $q_i$ $i \in [k]$

Определение 2 : Рассмотрим состояния в лексикографическом порядке. Определите как первое доступное состояние и первое доступное состояние после которое не эквивалентно никакому предыдущему состоянию. Определим как уникальное такое, что . $A$ $s(1)$ $s(i)$ $s(i-1)$ $c(q)$ $i$ $q \equiv s(i)$

Лемма 3 : может быть вычислена в пространстве . $s(i)$ $O(\log^2 n)$

Доказательство (набросок): определение 2 дает алгоритм. Мы используем счетчиков для перебора состояний. Пусть и текущее состояние. В каждом состоянии мы используем лемму 2, чтобы проверить , доступна ли . Если это так, мы зацикливаемся на всех предыдущих состояниях и проверяем, эквивалентно ли какое-либо из них . Если их нет, мы увеличиваем и выводим если . В противном случае мы сохраняем как и продолжаем. Поскольку мы храним только постоянное количество счетчиков, наши тесты можно выполнить в $k$ $j \leftarrow 0$ $q$ $q$ $q$ $j$ $q$ $j = i$ $q$ $s(j)$ $\text{NL} \subseteq \text{DSPACE}(\log^2 n)$ , это завершает доказательство.

Следствие 1 : может быть вычислено в пространстве . $c(q)$ $O(\log^2 n)$

Теорема : минимизировать можно в пространстве . $A$ $O(\log^2 n)$

Доказательство (эскиз): Пустьбыть наибольшим таким, что определено (т. е. количество классов ). Мы даем алгоритм, выводящий автомат где $1 \leq m \leq |Q_0| \cdots |Q_1|$ $i$ $s(i)$ $\equiv$ $A' = (Q', \Sigma, \delta', z', F')$

$Q' = \lbrace s(i) : i \in [m] \rbrace$ ;
$F' = \lbrace q \in Q' : q_i \in F_i \, \forall i \in [k] \rbrace$ ;
$z' = s(c(q))$ где . $q = (z_0, \ldots, z_k)$

Теперь мы покажем, как вычислить . Для каждого , вычислите и выведите переход . По лемме 3 и следствию 1 этот алгоритм работает в пространстве . Можно проверить, что минимально и . $\delta'$ $i \in [m], a \in \Sigma$ $q \leftarrow s(i) . a$ $\left(s(i), a, s(c(q))\right)$ $O(\log^2 n)$ $A'$ $\text{L}(A') = \text{L}(A)$

Майкл Блондин
источник

3

Хороший алгоритм! Вот немного другой способ взглянуть на этот алгоритм. Суть его состоит в том, что минимизация состояния любого заданного DFA может быть выполнена за полиномиальное время и пространство . После этого легко построить некоторый DFA, представляющий пересечение в логарифмическом пространстве (следовательно, в полиномиальном времени и пространстве ), и мы можем составить две функции, вычислимые в полиномиальном времени и пространство (аналогично составлению двух сокращений в логарифмическом пространстве), получая весь алгоритм за полиномиальное время и пространство .

O (\log^{2} n)

$O(\log^2 n)$

O (\log^{2} n)

$O(\log^2 n)$

O (\log^{2} n)

$O(\log^2 n)$

O (\log^{2} n)

$O(\log^2 n)$

Цуёси Ито

2

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

O (\log^{2} n)

$O(\log^2 n)$

N L \subseteq P \cap D S P A C E [\log^{2} n]

$NL \subseteq P \cap DSPACE[\log^2 n]$

N L \subseteq T I S P [n^{O (1)}, \log^{2} n]

$NL \subseteq TISP[n^{O(1)}, \log^2 n]$

O (\log^{2} n)

$O(\log^2 n)$

N L

$NL$

O (\log^{2} n)

$O(\log^2 n)$

Райан Уильямс

Вы правы, я тоже не знаю как. Я опубликовал это очень давно, поэтому я не уверен, почему я написал это так, но, возможно, я имел в виду «полиномиальное время или O (log² n)». Я отредактирую это, потому что это вводит в заблуждение. Спасибо!

Михаил Блондин

14

Дик Липтон и его коллеги недавно работали над этой проблемой, и Липтон писал об этом здесь:

http://rjlipton.wordpress.com/2009/08/17/on-the-intersection-of-finite-automata/

Кажется, что работа лучше, чем O (n ^ 2) открыта даже для очень особого случая определения, определяет ли пересечение DFA пустой язык.
В статье приводятся последствия сложности, которые могут возникнуть в результате значительно улучшенного алгоритма обработки не только двух DFA на перекрестке, но и больших чисел.

Энди Друкер
источник

1

а как насчет нижних границ?

Маркос Вильягра

1

Просто чтобы прояснить вопросы: я счастлив потратить O (n ^ 2) время (или, может быть, даже n ^ O (1) время), чтобы улучшить ограничение пространства.

Расмус Паг

13

Если вам дано k DFA (k является частью входных данных) и вы хотите знать, пусто ли их пересечение, эта проблема в целом завершена PSPACE:

Декстер Козен: нижние оценки для систем естественного доказательства FOCS 1977: 254-266

Возможно, если вы внимательно изучите это доказательство (и подобные конструкции Липтона и его соавторов), вы можете найти некоторую нижнюю границу пространства даже для фиксированного k.

Райан Уильямс
источник

Спасибо за этот указатель. Я предполагаю, что это может привести к нижней границе пространства n ^ Omega (1) на необходимом дополнительном пространстве, помимо входных данных. Но может ли это привести к нижней границе суперлинейного пространства?

Расмус Паг

1

@ user124864 Учитывая

DFA с

состояниями каждый, автомат продукта будет иметь

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

k

$k$

n

$n$

n^{k}

$n^k$

Майкл Вехар

1

@ user124864 Даже сложно определить, распознает ли продукт DFA непустой язык, сложно. Это проблема непустоты пересечения. Под жестким я подразумеваю, что это

завершено в сильном смысле.

X N L

$XNL$

Майкл Вехар

1

@ user124864 Если вы сможете решить ее менее чем за

раз, то мы получим более быстрые алгоритмы для решения задач PSPACE. Он не разрешим в недетерминированном двоичном пространстве

. Неизвестно, сможем ли мы решить ее менее чем за

детерминированного двоичного пространства. Неизвестно, сможем ли мы решить ее за одновременное детерминированное полиномиальное время и бинарное пространство

для любой функции

n^{k}

$n^k$

o (1) \cdot k \cdot \log (n)

$o(1) \cdot k \cdot \log(n)$

k^{2} \log^{2} (n)

$k^2 \log^2(n)$

f (k) \cdot \log^{2} (n)

$f(k) \cdot \log^2(n)$

(это улучшило бы теорему Савича).

f

$f$

Майкл Вехар

1

@ user124864 Примечание: у нас есть оба из следующих. (1) победа

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

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

n^{k}

$n^k$

n^{k}

$n^k$

Майкл Вехар

7

Для двух автоматов , принимающих конечные языки (ациклические автоматы), сложность состояний лежит в (1) . Этот результат также справедлив для унарных DFA (не обязательно ациклических) (2) . Тем не менее, вы, похоже, говорите о пространстве, необходимом для вычисления пересечения двух автоматов. Я не вижу, как классическая конструкция, использующая декартово произведение, использует $A$ $B$ $L(A) \cap L(B)$ $\Theta(|A| \cdot |B|)$ $O(n^2)$ Космос. Все, что вам нужно, это постоянное количество счетчиков логарифмического размера. Когда вы вычисляете функцию перехода для нового состояния вам нужно только сканировать входные данные, не просматривая ранее сгенерированные данные. $(q,r)$

Возможно, вы хотите вывести минимальный автомат? Если это так, то я понятия не имею, можно ли этого достичь. Сложность состояния пересечения для конечных языков не выглядит обнадеживающей. Однако унарные DFA имеют одинаковую сложность состояния, и я думаю, что этого можно достичь с помощью таких автоматов. Используя результаты из (2) , вы можете получить точный размер автомата, распознающего пересечение. Этот размер описывается длиной хвоста и цикла, поэтому переходная функция может быть легко вычислена с очень небольшим пространством, так как структура полностью описывается этими двумя размерами. Затем все, что вам нужно сделать, это сгенерировать набор конечных состояний. Пусть будет числом состояний в результирующем автомате, тогда для всех $n$ , состояние это конечное состояние тогдатолько тогда принимаюсь как и . Этот тест может быть проведен с небольшим количеством места. $1 \leq i \leq n$ $i$ $a^i$ $A$ $B$

Майкл Блондин
источник

1

Да, меня интересует минимальный автомат или хотя бы автомат такого же размера. Спасибо за указатели на одинарные DFA. Тем не менее, это не очень помогает для общего случая.

Расмус Паг

DFA пересечение в субквадратичном пространстве?

Ответы: