Сколько DFA принимают две заданные строки?

Зафиксируйте целое число и алфавит . Определим как совокупность всех конечных автоматов на состояниях с начальным состоянием 1. Мы рассматриваем все DFA (не только связанные, минимальные или невырожденные); таким образом, . $n$ $\Sigma=\{0,1\}$ $DFA(n)$ $n$ $|DFA(n)| = n^{2n}2^n$

Теперь рассмотрим две строки и определим как количество элементов которые принимают как и . $x,y\in\Sigma^*$ $K(x,y)$ $DFA(n)$ $x$ $y$

Вопрос: Какова сложность вычисления ? $K(x,y)$

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

Изменить: Теперь, когда есть щедрость на этот вопрос, я думаю, что немного больше точности в формулировке в порядке. Для , пусть будет набором из автоматов, как определено выше. Для , определите как число автоматов в которые принимают и и . Вопрос: можно ли вычислить за время ? $n\ge1$ $DFA(n)$ $n^{2n}2^n$ $x,y\in\{0,1\}^*$ $K_n(x,y)$ $DFA(n)$ $x$ $y$ $K_n(x,y)$ $poly(n,|x|,|y|)$

cc.complexity-theory fl.formal-languages automata-theory counting-complexity Арье
источник

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

a3nm

Арье, ты можешь объяснить количество

? Я не могу получить

фактор. Добавлено: К сожалению, я забыл указать конечные состояния. Во всяком случае, ради других, вот как идет счет. Для каждого состояния укажите куда идти на входах

; что составляет

. Укажите набор конечных состояний; это

n^{2 n} 2^{n}

$n^{2n} 2^n$

2^{n}

$2^n$

0

$0$

1

$1$

n^{2 n}

$n^{2n}$

2^{n}

$2^n$

Шриватсан Нараянан

Действительно, мне все равно, что происходит со строками, отличными от

. Я полагаю, нужно определенное количество очков, чтобы начать щедрость?

x

$x$

y

$y$

Арье

Самый маленький автомат, который принимает

имеет одно состояние, поэтому я не думаю, что это ужасно информативно ...

x

$x$

y

$y$

Aryeh

Вот идея: нам нужно знать только число

-state ДКА , которые в конечном итоге в том же состоянии , по

. Пусть это число будет

- общее количество DFA, то есть

. Тогда ответ

n

$n$

x

$x$

y

$y$

m

$m$

M

$M$

M = n^{2 n} 2^{n}

$M=n^{2n}2^{n}$

, это дает оценки. Для вычисления

другая идея состоит в том, что мы можем забыть об общем начальном сегменте

а также предположить, что wlog

. Мы только посчитаем количество двоичных DAG с

состояниями и высотой не более

которые

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

\frac{1}{2} m + \frac{1}{4} (M - m)

$\frac{1}{2}m + \frac{1}{4}(M-m)$

m

$m$

x

$x$

y

$y$

x = 0^{a}

$x=0^a$

b = 1^{b}

$b=1^b$

l

$l$

max {a, b}

$\max\{a,b\}$

0^{a}

$0^a$

1^{b}

$1^b$

m

$m$

Каве

Ответы:

Так что вопрос довольно короткий, но очень интересный. Я предполагаю, что входное значение в унарном виде, а и в двоичном (или у нас есть проблемы, как указано в ответе Кая). $n$ $x$ $y$

Прежде всего, если вам интересно знать приблизительно, вы можете просто сгенерировать несколько случайных DFA, и это даст вам (whp) хорошее приближение. (Интересно, есть ли у этого класса сложности имя?) $K(x,y)$

Тогда знание точно кажется сложной задачей. Как отмечено в комментариях a3_nm и Kaveh, вопрос эквивалентен определению количества автоматов, для которых и переходят в одно и то же состояние. Я буду обозначать вероятность того, что они перейдут в одно и то же состояние через . $K(x,y)$ $x$ $y$ $p$

Обновление: некоторые вещи, которые я здесь написал, не соответствуют действительности, теперь я их исправил.

Легко видеть, что . У нас есть равенство, если - все 0, а - все ноль, за исключением последнего бита, который равен 1. Существуют ли другие случаи? Я не знаю. Если, например, - пустая строка и , то $p \ge 1/n$ $x$ $y$ $x$ $y=00$ . $p= \frac{n+1}{(n-1)n}$

Чтобы упростить задачу, я даже начал думать о том, что произойдет, если и одинарны. Если оба не меньше и их разность делится на тогда . Есть ли простая формула для унарной версии? $x$ $y$ $n$ $n!$ $p=1$

domotorp
источник

Я прояснил проблему - желателен алгоритм

(или сокращение от некоторой известной сложной проблемы). Приближение выборки используется в статье, где вводится это ядро: portal.acm.org/citation.cfm?id=1577108

p o l y (n, | x |, | y |)

$poly(n,|x|,|y|)$

Aryeh

Что касается унарной версии: унарных автоматов с

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

n

$n$

K_{n} (x, y)

$K_n(x,y)$

Арье

Действительно, вы абсолютно правы в том, что унарная версия вычислима. Мне все еще интересно, насколько проста формула для данных x и y.

Домоторп

Используемое вами сокращение является ошибочным: x и y могут приниматься одним и тем же автоматом и заканчиваться в совершенно разных состояниях, фактически они могут разделять только начальное состояние на своих путях, что верно для всех строк.

amnn

@amnn: Прошло три года с тех пор, как я написал это, но разве третий абзац моего ответа не объясняет, почему я имею дело только с окончанием в том же состоянии?

domotorp

Я вполне могу упустить момент, но вы заявили, что фиксировано, поэтому все DFA этого размера можно считать предварительно вычисленными и сохраненными в легко симулируемом формате. Вычислите следующим образом: $n$ $K$

На входе , где $x$ $y$ $x,y\in\Sigma^*$

хранить и $x$ $y$
Инициализировать счетчик до $c$ $0$
для каждого из ваших DFA $n^{2n} 2^n$
а. смоделируйте это на обоих словах (этот шаг ) $\mathcal{O}(|xy|)$

б. приращение если оба прогона симуляции принимают $c$
выход $c$

В целом, вычисления имеют линейную сложность. Ответ совсем другой для . $K(n,x,y)$

Кай
источник

Ясно, что все машины будут работать. Арье хочет знать, возможно, есть алгоритм полиномиального времени или какой-то другой результат сложности.

Лев Рейзин

Строго говоря, это полиномиальное время на входе, если n не является частью ввода, это то, что говорил Кай. Но вопрос явно другой.

domotorp

А ну понятно. Я не думаю, что это то, что он имеет в виду под «исправить

». Я думаю, что естественная интерпретация проблемы - та, которая не упрощает ее.

n

$n$

Лев Рейзин

Хорошо, спасибо, что указал на лазейку, Кай. Это было исправлено :)

Aryeh