Как быстро мы можем решить, является ли данный DFA минимальным?

11

Минимизация детерминированных конечных автоматов (DFA) является проблемой, которая была тщательно изучена в литературе, и было предложено несколько алгоритмов для решения следующей проблемы: Учитывая DFA , вычислим соответствующий минимальный DFA, принимающий тот же язык, что и . Большинство этих алгоритмов работают за полиномиальное время.AAA

Однако мне интересно, является ли вариант решения этой проблемы - «учитывая DFA , является ли минимальным?» - может быть решена более эффективно, чем вычисление минимального автомата. Очевидно, что это также можно сделать эффективно, запустив, например , алгоритм уточнения разделов Хопкрофта, а затем решив, содержат ли все разделы ровно одно состояние.AAA

Как предлагает Юваль Фильмус в своем ответе , вариант разрешимости может быть решен быстрее, возможно, с использованием стандартных алгоритмов. К сожалению, я не вижу, как (надеюсь, я не упустил очевидный момент здесь).

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

Корнелиус Бранд
источник
Алгоритм Хопкрофта уже работает в квазилинейном времени, поэтому нет особых возможностей для его улучшения.
Юваль Фильмус
Да, я отредактировал свой вопрос так, чтобы он отражал этот факт, @YuvalFilmus
Cornelius Brand
1
Я считаю, что самый быстрый известный алгоритм минимизации DFA - все еще этот . Это быстрее, чем любой алгоритм, опубликованный до 2008 года, выполняемый за время , где - количество переходов. mО(N+мжурналN)м
Юхо
мне кажется маловероятным, что решение проблемы по сложности эквивалентно проблеме минимизации, первое кажется, возможно, сложнее, потому что оно включает тестирование на эквивалентность DFA, которая не является нетривиальной. таким образом, кажется, что сложность решения проблемы является максимумом «минимизации или проверки эквивалентности». и какова сложность проверки эквивалентности?
ВЗН
@vzn Предполагая, что вы имели в виду «[...] что нетривиально»: это необязательно, так как, например, процедура, которую я дал в своем вопросе, избегает проверки на эквивалентность. Однако я также считаю, что проблема не проще, чем сведение к минимуму.
Корнелиус Бренд

Ответы:

5

Возможно, это не совсем тот ответ, который вы ищете, но поскольку вы спрашивали о проблемах с решением, я подумал, что вас может заинтересовать сложность проблемы. Это -полное.NL

Теперь, что это значит для DFA быть минимальным? Есть два свойства:

  1. Каждое состояние достижимо: , что мы можем достичь из начального состояния , следуя ; в символах: . д S ш с ш дQQвесΣ*QsвесsвесQ

  2. Каждая пара состояний различимы: с такое , что и и (только один из представляет собой принимает состояние).q r w Σ q w s r w t | { с ,Q,рQQр весΣ*QвесsрвесT|{s,T}F|знак равно1s,T

Обратите внимание , что может быть вычислена в лог-пространстве (т.е. , просто отслеживать текущее положение , как вы будете следовать одну букву в то время). Кроме того, существует лишь конечное число чередований между и так , как следствие теоремы Иммерман-Szelepcsenyi , мы имеем , что проблема заключается в .L wИксвесYLвесNL

Самый простой способ , чтобы увидеть , что это трудно для является уведомление , что свойство 1 , решает - направленного недостижимости, которая является Прототипом трудной задачей. Но даже если вы рассматриваете только достижимые DFA, проблема остается сложной (то есть свойство 2 является -hard), и вы можете найти относительно прямое доказательство в лемме 2.2 Cho & Huynh (1992) .NLsTNL

Конечно, я использовал недетерминизм, так что это немного кашель, так как он отличается от алгоритма Хопкрофта. Но мы знаем, что , поэтому вы можете использовать эти конструкции, чтобы получить более гибкий алгоритм, чем Хопкрофт (который по своей природе должен отслеживать многих разделов) ). nNLL2N

Артем Казнатчеев
источник
Кажется, это улучшает пространство, но не усложняет время?
ВЗН
Я согласен с взн. Хотя мне нравится этот ответ, я по- прежнему заинтересован в идеях, которые более тесно связаны с первоначальным вопросом.
Корнелиус Марка
NLп