WikiDer > Слабый автомат Бючи

В Информатика и теория автоматов, а Слабый автомат Бючи это формализм, который представляет собой набор бесконечных слов. Слабый автомат Бюхи является модификацией Büchi автомат такой, что для всех пар состояний ${ displaystyle q}$ и ${ displaystyle q '}$ принадлежащий к тому же компонент сильной связности, ${ displaystyle q}$ принимает тогда и только тогда, когда ${ displaystyle q '}$ принимает.

А Büchi автомат принимает слово ${ displaystyle w}$ если существует запуск, такой, что по крайней мере одно состояние возникает бесконечно часто в наборе конечных состояний ${ displaystyle F}$. Для слабых автоматов Бюхи это условие эквивалентно существованию прогона, который в конечном итоге остается в наборе принимающих состояний.

Слабые автоматы Бючи строго менее выразительны, чем автомат Бюхи, и чем Автомат Ко-Бючи.

Характеристики

Детерминированные слабые автоматы Бюхи можно минимизировать во времени ${ Displaystyle О (п журнал (п))}$.^[1]

Языки, принятые автоматами Слабого Бюхи, замкнуты относительно объединения, пересечения и дополнения.

Недетерминированные автоматы Слабого Бюхи более выразительны, чем Слабые автоматы Бюхи. Например, язык ${ Displaystyle (а + б) ^ {*} б ^ { омега}}$ может быть определен слабым автоматом Бюхи, но никаким детерминированным автоматом Бюхи

Рекомендации

• Бойджело, Бернар (3 июля 2005 г.). «Эффективная процедура принятия решения для линейной арифметики над целыми и действительными числами» (PDF). Транзакции ACM по вычислительной логике. 6 (3): 614–633. Дои:10.1145/1071596.1071601.