Автомат Ко-Бючи - Co-Büchi automaton

Эта статья не цитировать любой источники. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удаленный. Найдите источники: «Автомат Ко-Бючи»  – Новости  · газеты  · книги  · ученый  · JSTOR (Июль 2011 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

(Детерминированные) автоматы Ко-Бюхи строго слабее (недетерминированных) автоматов Бюхи.

Формальное определение

Формально детерминированный автомат Ко-Бюхи кортеж ${ Displaystyle { mathcal {A}} = (Q, Sigma, delta, q_ {0}, F)}$ который состоит из следующих компонентов:

• ${ displaystyle Q}$ это конечный набор. Элементы ${ displaystyle Q}$ называются состояния из ${ displaystyle { mathcal {A}}}$.
• ${ displaystyle Sigma}$ конечное множество, называемое алфавит из ${ displaystyle { mathcal {A}}}$.
• ${ displaystyle delta: Q times Sigma rightarrow Q}$ это функция перехода из ${ displaystyle { mathcal {A}}}$.
• ${ displaystyle q_ {0}}$ является элементом ${ displaystyle Q}$, называемое начальным состоянием.
• ${ Displaystyle F substeq Q}$ это набор окончательного состояния. ${ displaystyle { mathcal {A}}}$ принимает именно эти слова ${ displaystyle w}$ с бегом ${ Displaystyle rho (ш)}$, в котором все бесконечно часто встречающиеся состояния в ${ Displaystyle rho (ш)}$ находятся в ${ displaystyle F}$.

В недетерминированный ко-автомат Бюхи, функция перехода ${ displaystyle delta}$ заменяется соотношением перехода ${ displaystyle Delta}$. Исходное состояние ${ displaystyle q_ {0}}$ заменяется набором начального состояния ${ displaystyle Q_ {0}}$. Как правило, термин ко-автомат Бюхи относится к недетерминированному ко-автомату Бюхи.

Для более полного формализма см. Также ω-автомат.

Условия приема

Условие приемки ко-автомата Бюхи формально

${ Displaystyle существует я forall j: ; j geq i quad rho (w_ {j}) in F.}$

Условие приемки Büchi является дополнением условия приемки co-Büchi:

${ Displaystyle forall я существует j: ; j geq i quad rho (w_ {j}) in F.}$

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

Автоматы Ко-Бюхи замкнуты относительно объединения, пересечения, проекции и детерминизации.