Есть ли какие-либо открытые проблемы с DFA?

59

После изучения детерминированных конечных автоматов (DFA) в старшекурснике, я почувствовал, что они очень хорошо поняты. Мой вопрос: есть ли что-то, чего мы до сих пор не понимаем в них. Я имею в виду не обобщения ДФА, а исходные немодифицированные ДФА, которые мы изучаем в старшекурсниках.

Это неопределенный вопрос, но я надеюсь, что вы поняли идею. Я хочу понять, справедливо ли сказать, что мы полностью понимаем DFA. Таким образом, я действительно имею в виду вопросы, которые по своей сути связаны с DFA, а не проблемы, искусственно созданные для того, чтобы выглядеть как проблема с DFA. Позвольте мне привести пример такой проблемы. Пусть L будет пустым языком, если P = NP, и некоторым фиксированным нерегулярным языком, если P не является NP. Может ли L быть принята DFA? Этот вопрос о ДФА, но не о них по духу. Я надеюсь, что моя точка зрения ясна, и я не получаю педантичные ответы от людей.

Короче говоря честно ли

По сути, мы полностью понимаем DFA.

Мне жаль, если выясняется, что это огромная область исследований, о которой я не знал, и я только что оскорбил целое сообщество людей.

Канадский гусь
источник
16
Первая открытая проблема пришла мне в голову, является ли гипотеза Черны верной. en.wikipedia.org/wiki/Synchronizing_word and liafa.jussieu.fr/~jep/Problemes/Cerny.html Следующее сообщение в блоге может быть также интересным для вас: rjlipton.wordpress.com/2009/08/17/…
Абузер Якарылмаз
1
Учитываются ли открытые проблемы с NFA и регулярными выражениями?
Сянь-Чи Чанг 張顯 之
1
@ Сянь-Чи: давайте будем максимально ограничены в толковании вопроса. Я предполагал, что открытых проблем не осталось, но ответы показывают, что это не так.
канадский гусь
1
DFA и регулярные выражения эквивалентны. NFA и DFA эквивалентны по выразительной силе, хотя NFA может иметь гораздо меньше состояний, чем его соответствующий DFA.
chepner
6
@chepner Хотя DFA, NFA и regexen эквивалентны в выразительной силе, это никоим образом не означает, что знание всего об одном подразумевает знание всего о другом. Например, знание того, как свести к минимуму DFA, напрямую не скажет вам, как минимизировать NFA - что на самом деле является довольно сложной проблемой !
Даниэль Вагнер

Ответы:

56

Вот одна проблема, описанная в книге «Второй курс по формальным языкам и теории автоматов» Шаллита.

Пусть и два разных слова с . Каков размер самого маленького DFA, который принимает но отклоняет , или наоборот?v | ты | = | V | = n u vuv|u|=|v|=nuv

Робсон в своей работе « Разделение струн маленькими автоматами » в 1989 году доказал верхнюю оценку . Самая известная нижняя граница в .Ω ( лог - п )O(n2/5(logn)3/5)Ω(logn)

Для просмотра смотрите это .

Сянь-Чжи Чан 張顯 之
источник
12
В своем недавнем выступлении на BCTCS 2014 в Университете Лафборо я предлагаю 100 фунтов стерлингов за любой нетривиальный прогресс в решении этой проблемы. Ох, и есть и другие открытые проблемы, перечисленные там тоже! См. Cs.uwaterloo.ca/~shallit/Talks/bc4.pdf .
Джеффри Шаллит
1
Я приму это, так как это было первым, но все они - отличные ответы. Спасибо всем и продолжайте!
канадский гусь
Сейчас в Википедии как en.wikipedia.org/wiki/Separating_words_problem
Дэвид Эппштейн
41

Вот очень простое решение проблемы с DFA. Учитывая DFA M, принимает ли M представление base-2 хотя бы одного простого числа?

В настоящее время мы даже не знаем, рекурсивно ли разрешима эта проблема.

Если он рекурсивно разрешим, и у нас был алгоритм для него, мы могли бы решить давнюю открытую проблему о том, существуют ли какие-либо простые числа Ферма (простые числа в форме ) больше, чем наибольшее известное, 65537. (Поскольку любое простое число с представлением base-2 в форме должно быть простым числом Ферма.)1 0 + 122n+110+1

Джеффри Шаллит
источник
В теории чисел существуют и другие гипотезы, относящиеся к периодам, например, проблема несоответствия Эрдоса и включение некоторых в формулировки DFA представляется возможным и в других случаях, возможной исследовательской программе для кого-то ...
vzn
Правильно ли я понимаю, что если бы у нас был алгоритм для этой задачи, это также решило бы проблему Серпинского и проблему Ризеля? ( en.wikipedia.org/wiki/Sierpinski_number , en.wikipedia.org/wiki/Riesel_number )
sdcvvc
Да, sdcvvc, это так.
Джеффри Шаллит
39

Гипотеза Черны все еще открыта и важна. Речь идет о DFA, которые имеют синхронизирующее слово (слово со свойством, что две копии автомата, запущенные в разных состояниях, всегда оказываются в одном и том же состоянии друг с другом после обработки слова), и спрашивает, есть ли (для состояния) автоматы) длина самого короткого такого слова всегда не более . Наилучшие доказанные оценки имеют вид .( n - 1 ) 2 O ( n 3 )n(n1)2O(n3)

Дэвид Эппштейн
источник
Извините, Abuzer Yakaryilmaz, не заметил ваш комментарий, прежде чем опубликовать это как ответ. Но я верю, что это заслуживает того, чтобы быть ответом, а не просто комментарием ...
Дэвид Эппштейн
2
Нет проблем :) Я думаю, что вторая открытая проблема, которую я связал, также выглядит довольно интересной.
Абузер Якарылмаз
7
Я знаю, что это известный вопрос, но есть ли быстрое объяснение, почему это важный вопрос? Что бы мы узнали, если бы граница действительно была а не ? н 3 / 6(n1)2n3/6
Сашо Николов
@SashoNikolov Практический интерес может иметь возможность переустановить систему в известное состояние, не наблюдая ее (например, спутник), используя наименьшее количество действий.
Денис
Да, я впервые узнал об этой проблеме благодаря работе Натараджана по проектированию компонентов сборочных линий, которые механически заставляют детали на них находиться в определенных геометрических ориентациях. Более короткие последовательности сброса (в автомате, представляющем потенциальные шаги переориентации) = более короткие сборочные линии.
Дэвид Эппштейн
20

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

Хорошо известно, что любой NFA в n-состоянии может быть преобразован в эквивалентный DFA, имеющий не более состояний. Это наилучшим образом возможно в худшем случае, в том смысле, что существуют обычные языки с недетерминированным состоянием состояний n (т. Е. Числом состояний в минимальном NFA), но с детерминированным состоянием состояний . Есть также примеры языковых семейств, где недетерминизм может спасти квадратичный фактор, и случаи, когда недетерминизм вообще не помогает спасти какие-либо состояния. Таким образом, естественный вопрос заключается в следующем:2 н2n2n

Проблема магического числа

Существует ли для каждого между и регулярный язык такой, что разрыв между сложностью недетерминированного состояния и сложностью детерминированного состояния составляет точно ?n 2 n L n ααn2nLnα

Если мы полностью поймем конструкцию powerset и отношение Myhill-Nerode с математической точки зрения, то я ожидаю, что можно создавать такие языки для каждого или альтернативно указывать значения для которых это невозможно (если такие значения существуют, они называются «магическими числами»).ααα

Известно, что существуют магические числа для входного алфавита размера , а с 2009 года не существует магических чисел, если размер алфавита составляет не менее . Но если я не ошибаюсь, дело о бинарных алфавитах все еще остается открытым.313

Галина Йираскова. Магические числа и троичный алфавит. В кн .: 13-я Международная конференция «Развитие теории языка» (DLT 2009), том 5583 «Конспекты лекций в области компьютерных наук», страницы 300–311.

Герман Грубер
источник
7
Это большая проблема! Но тот, кто придумал термин «магическое число», должен быть застрелен.
Джеффри Шаллит
20

Название: Пересечение не пустоты для двух ДФА

Описание: Учитывая два ДКА и , существует ли строка такая , что и оба принимают ?Д 2 х Д 1 Д 2 хD1D2xD1D2x

Открытая проблема: Можем ли мы решить непустоту пересечения для двух DFA за времени?o(n2)

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

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

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

Хорошего дня! :)

Майкл Вехар
источник
привет MW рад, что вы заметили этот вопрос. недавно привел Вас на этот другой вопрос повторного разделения P / L . как вы недавно доказали, вышеупомянутый вопрос (верхние границы сложности решения непустоты пересечения нескольких DFA) тесно связан с (основной открытой проблемой) разделения P / NL.
vzn
Большое спасибо! Кто ты, взн? Я пошел в твой блог и осмотрелся, но не мог понять это.
Майкл Вехар
1
D1D2Ω(n2)
12

Вот открытая проблема, связанная с DFA и теорией машинного обучения: являются ли равномерно случайные (случайные переходы и поведение принятия / отклонения) DFA обучаемыми в модели PAC?

Примечание: мы думаем, что произвольный DFA не может быть изучен на основе результатов криптографической твердости . Для случайного DFA у нас есть только нижние оценки SQ , которые не так сильны.

Лев Рейзин
источник
6

n

Мне кажется, что формула замкнутой формы должна существовать, но ни одна не известна. Известны некоторые асимптотические оценки:

n

mikero
источник
Это действительно круто. Я случайно подумал об этом на днях, и я не знал, что другие работали над этим. Спасибо, что поделился. :)
Майкл Вехар
4
Почему вы считаете, что существует закрытая формула? Я думаю, что это очень маловероятно.
domotorp
См. Также этот вопрос, чтобы узнать, что известно об этой проблеме: каково количество языков, принятых DFA размера n
Герман Грубер,
2

Вот вопрос, связанный с DFA, который я задавал здесь раньше, и, насколько я знаю, он все еще открыт:

nΣ={0,1}DFA(n)| D F A ( n ) | = n 2 n 2 nn|DFA(n)|=n2n2n

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

Вопрос: в чем сложность вычисления ? В частности, можно ли вычислить за время ?K n ( x , y ) p o l y ( n , | x | , | y | )Kn(x,y)Kn(x,y)poly(n,|x|,|y|)

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

Арье
источник
Каково текущее состояние сложности проблемы?
Райан
1
Иеремия Блок имел некоторые частичные результаты; Насколько я знаю, это состояние знаний: cs.cmu.edu/~jblocki/Slides/ComputationalComplexityofKn.pdf
Арье
-3

(«мыслить нестандартно» ...) это несколько надуманная проблема, связанная с DFA (не рассматривали ее в других местах), но в TCS проявляется тема, что даже многие явно «простые» вычислительные объекты (такие как DFA) могут иметь сложные свойства также аспект / тема, воплощенная в теореме Райса. (в некоторых отношениях конечная «сложность» - это «неразрешимость», то есть полнота Тьюринга.)

nxnxn

DFAnDFADFAnDFAnDFAтакже является RL (и DFA).

Σ

nDFAnΣ

Σn

Теперь, чтобы связать это больше с вопросом, хотя это широко не отмечено (некоторые считают его тривиальным), многие открытые проблемы в TCS / математике тесно связаны с неразрешимостью в том, что, учитывая оракула для проблемы остановки, они могут быть " решено».

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

[1] Проблемы со словом, требующие экспоненциального времени / Stockmeyer & Meyer

[2] Мейер, AR и Л. Стокмейер. Задача эквивалентности для регулярных выражений с возведением в квадрат требует экспоненциального пространства. 13-й симпозиум IEEE по теории коммутации и автоматов, октябрь 1972 г., с. 125–129.

[3] Введение в языки, автоматы и вычисления / Хопкрофт / Ульман.

ВЗН
источник
2
Я думаю, что вы путаете понятия «неразрешимый» и «открытый».
Лев Рейзин
по общему признанию, это необычный и / или нетрадиционный взгляд, если не сказать больше, но я не единственный, кто поддержал его. см., например, эту цитату Мишеля в этой статье. Проблемы теории чисел из соревнования занятых бобров . также схожие настроения выражали известные гипотезы теории открытых чисел по простой проблеме, неразрешимость которой неизвестна . см. также автоматическую теорему, доказывающую неразрешимость
vzn
DFAnΣn{1nDFAnΣ}
DFA