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

28

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

Теперь рассмотрим две строки и определим как количество элементов которые принимают как и .x,yΣK(x,y)DFA(n) xy

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

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

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

Арье
источник
2
Если вы исправляете DFA без фиксации конечных состояний, то либо он отображает x и y в одно и то же состояние, в этом случае единственным ограничением является то, что состояние должно быть конечным, либо он отображает их в два разных состояния, и в этом случае единственное ограничение заключается в том, что они оба должны быть окончательными. Таким образом, я бы перефразировал вашу проблему как «сколько DFA отображает x и y в разные состояния?».
a3nm
3
Арье, ты можешь объяснить количество ? Я не могу получить 2 n фактор. Добавлено: К сожалению, я забыл указать конечные состояния. Во всяком случае, ради других, вот как идет счет. Для каждого состояния укажите куда идти на входах 0 и 1 ; что составляет п 2 н . Укажите набор конечных состояний; это 2 н . n2n2n2n01n2n2n
Шриватсан Нараянан
2
Действительно, мне все равно, что происходит со строками, отличными от и y . Я полагаю, нужно определенное количество очков, чтобы начать щедрость? xy
Арье
4
Самый маленький автомат, который принимает и y, имеет одно состояние, поэтому я не думаю, что это ужасно информативно ...xy
Aryeh
3
Вот идея: нам нужно знать только число -state ДКА , которые в конечном итоге в том же состоянии , по х и у . Пусть это число будет m, а M - общее количество DFA, то есть M = n 2 n 2 n . Тогда ответ 1nxymMM=n2n2n, это дает оценки. Для вычисленияmдругая идея состоит в том, что мы можем забыть об общем начальном сегментеxиy,а также предположить, что wlogx=0aиb=1b. Мы только посчитаем количество двоичных DAG сlсостояниями и высотой не болееmax{a,b},которые0aи1bоказываются в одном и том же месте, и из этого легко вычислитьm.12m+14(Mm)mxyx=0ab=1blmax{a,b}0a1bm
Каве

Ответы:

1

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

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

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

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

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

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

domotorp
источник
Я прояснил проблему - желателен алгоритм (или сокращение от некоторой известной сложной проблемы). Приближение выборки используется в статье, где вводится это ядро: portal.acm.org/citation.cfm?id=1577108poly(n,|x|,|y|)
Aryeh
2
Что касается унарной версии: унарных автоматов с состояниями много полиномиально, так что я бы поспорил, что для этого случая есть многовариантный алгоритм для вычисления K n ( x , y ) . nKn(x,y)
Арье
Действительно, вы абсолютно правы в том, что унарная версия вычислима. Мне все еще интересно, насколько проста формула для данных x и y.
Домоторп
Используемое вами сокращение является ошибочным: x и y могут приниматься одним и тем же автоматом и заканчиваться в совершенно разных состояниях, фактически они могут разделять только начальное состояние на своих путях, что верно для всех строк.
amnn
@amnn: Прошло три года с тех пор, как я написал это, но разве третий абзац моего ответа не объясняет, почему я имею дело только с окончанием в том же состоянии?
domotorp
0

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

На входе , y, где x , y Σ xyx,yΣ

  1. хранить и уxy
  2. Инициализировать счетчик до 0c0
  3. для каждого из ваших DFAn2n2n
  4. а. смоделируйте это на обоих словах (этот шаг )O(|xy|)

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

  5. выход c

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

Кай
источник
3
Ясно, что все машины будут работать. Арье хочет знать, возможно, есть алгоритм полиномиального времени или какой-то другой результат сложности.
Лев Рейзин
Строго говоря, это полиномиальное время на входе, если n не является частью ввода, это то, что говорил Кай. Но вопрос явно другой.
domotorp
4
А ну понятно. Я не думаю, что это то, что он имеет в виду под «исправить ». Я думаю, что естественная интерпретация проблемы - та, которая не упрощает ее. n
Лев Рейзин
1
Хорошо, спасибо, что указал на лазейку, Кай. Это было исправлено :)
Aryeh