Büchi автомат

Автомат Бюхи с двумя состояниями и , первое из которых является начальным состоянием, а второе — принимающим. Его входы — бесконечные слова над символами . Например, он принимает бесконечное слово , где обозначает бесконечное повторение строки. Он отклоняет бесконечное слово . ${\displaystyle q_{0}}$ ${\displaystyle q_{1}}$ ${\displaystyle \{a,b\}}$ ${\displaystyle (ab)^{\omega }}$ ${\displaystyle x^{\omega }}$ ${\displaystyle aaab^{\omega }}$

В информатике и теории автоматов детерминированный автомат Бюхи — это теоретическая машина, которая либо принимает, либо отвергает бесконечные входные данные. Такая машина имеет набор состояний и функцию перехода, которая определяет, в какое состояние машина должна перейти из текущего состояния при считывании следующего входного символа. Некоторые состояния являются принимающими состояниями, а одно состояние является начальным. Машина принимает входные данные тогда и только тогда, когда она будет проходить через принимающее состояние бесконечное количество раз при считывании входных данных.

Недетерминированный автомат Бюхи , позже называемый просто автоматом Бюхи , имеет функцию перехода, которая может иметь несколько выходов, что приводит ко многим возможным путям для одного и того же входа; он принимает бесконечный вход тогда и только тогда, когда некоторый возможный путь принимает. Детерминированные и недетерминированные автоматы Бюхи обобщают детерминированные конечные автоматы и недетерминированные конечные автоматы на бесконечные входы. Каждый из них является типом ω-автоматов . Автоматы Бюхи распознают ω-регулярные языки , версию регулярных языков с бесконечным количеством слов . Они названы в честь швейцарского математика Юлиуса Рихарда Бюхи , который изобрел их в 1962 году. ^[1]

Автоматы Бюхи часто используются при проверке моделей как теоретико-автоматная версия формулы линейной временной логики .

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

Формально детерминированный автомат Бюхи представляет собой кортеж A  = ( Q ,Σ,δ, q ₀ , F ), состоящий из следующих компонентов:

• Q — конечное множество . Элементы Q называются состояниями A.
• Σ — конечное множество, называемое алфавитом A.
• δ:  Q ×  Σ →  Q — функция, называемая функцией перехода A.
• q ₀ — элемент Q , называемый начальным состоянием A.
• F ⊆ Q — условие принятия . A принимает ровно те прогоны , в которых хотя бы одно из бесконечно часто встречающихся состояний находится в  F.

В ( недетерминированном ) автомате Бюхи функция перехода δ заменяется отношением перехода Δ, которое возвращает набор состояний, а единственное начальное состояние q ₀ заменяется набором I начальных состояний. Обычно термин автомат Бюхи без квалификатора относится к недетерминированным автоматам Бюхи.

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

Свойства закрытия

Множество автоматов Бюхи замыкается относительно следующих операций.

Пусть и будут автоматами Бюхи, а будет конечным автоматом . ${\displaystyle \scriptstyle A=(Q_{A},\Sigma ,\Delta _{A},I_{A},{F}_{A})}$ ${\displaystyle \scriptstyle B=(Q_{B},\Sigma ,\Delta _{B},I_{B},{F}_{B})}$ ${\displaystyle \scriptstyle C=(Q_{C},\Sigma ,\Delta _{C},I_{C},{F}_{C})}$

• Союз : существует автомат Бюхи, который распознает язык ${\displaystyle \scriptstyle L(A)\cup L(B).}$

Доказательство: Если предположить, что wlog пуст, то распознается автоматом Бюхи ${\displaystyle \scriptstyle Q_{A}\cap Q_{B}}$ ${\displaystyle \scriptstyle L(A)\cup L(B)}$ ${\displaystyle \scriptstyle (Q_{A}\cup Q_{B},\Sigma ,\Delta _{A}\cup \Delta _{B},I_{A}\cup I_{B},{F}_{A}\cup {F}_{B}).}$

• Пересечение : существует автомат Бюхи, который распознает язык ${\displaystyle \scriptstyle L(A)\cap L(B).}$

Доказательство: Автомат Бюхи распознает , где ${\displaystyle \scriptstyle A'=(Q',\Sigma ,\Delta ',I',F')}$ ${\displaystyle \scriptstyle L(A)\cap L(B),}$

• ${\displaystyle \scriptstyle Q'=Q_{A}\times Q_{B}\times \{1,2\}}$
• ${\displaystyle \scriptstyle \Delta '=\Delta _{1}\cup \Delta _{2}}$
  • ${\displaystyle \scriptstyle \Delta _{1}=\{((q_{A},q_{B},1),a,(q'_{A},q'_{B},i))|(q_{A},a,q'_{A})\in \Delta _{A}{\text{ and }}(q_{B},a,q'_{B})\in \Delta _{B}{\text{ and if }}q_{A}\in F_{A}{\text{ then }}i=2{\text{ else }}i=1\}}$
  • ${\displaystyle \scriptstyle \Delta _{2}=\{((q_{A},q_{B},2),a,(q'_{A},q'_{B},i))|(q_{A},a,q'_{A})\in \Delta _{A}{\text{ and }}(q_{B},a,q'_{B})\in \Delta _{B}{\text{ and if }}q_{B}\in F_{B}{\text{ then }}i=1{\text{ else }}i=2\}}$
• ${\displaystyle \scriptstyle I'=I_{A}\times I_{B}\times \{1\}}$
• ${\displaystyle \scriptstyle F'=\{(q_{A},q_{B},2)|q_{B}\in F_{B}\}}$

По построению, является запуском автомата A' на входном слове w , если является запуском A на w и является запуском B на w . является принимающим и является принимающим, если r' является конкатенацией бесконечной серии конечных сегментов 1-состояний (состояний с третьим компонентом 1) и 2-состояний (состояний с третьим компонентом 2) поочередно. Существует такая серия сегментов r', если r' принимается A'. ${\displaystyle \scriptstyle r'=(q_{A}^{0},q_{B}^{0},i^{0}),(q_{A}^{1},q_{B}^{1},i^{1}),\dots }$ ${\displaystyle \scriptstyle r_{A}=q_{A}^{0},q_{A}^{1},\dots }$ ${\displaystyle \scriptstyle r_{B}=q_{B}^{0},q_{B}^{1},\dots }$ ${\displaystyle \scriptstyle r_{A}}$ ${\displaystyle \scriptstyle r_{B}}$

• Конкатенация : существует автомат Бюхи, который распознает язык ${\displaystyle \scriptstyle L(C)\cdot L(A).}$

Доказательство: Если предположить, что wlog пуст , то автомат Бюхи распознает , где ${\displaystyle \scriptstyle Q_{C}\cap Q_{A}}$ ${\displaystyle \scriptstyle A'=(Q_{C}\cup Q_{A},\Sigma ,\Delta ',I',F_{A})}$ ${\displaystyle \scriptstyle L(C)\cdot L(A)}$

• ${\displaystyle \scriptstyle \Delta '=\Delta _{A}\cup \Delta _{C}\cup \{(q,a,q')|q'\in I_{A}{\text{ and }}\exists f\in F_{C}.(q,a,f)\in \Delta _{C}\}}$
• ${\displaystyle \scriptstyle {\text{ if }}I_{C}\cap F_{C}{\text{ is empty then }}I'=I_{C}{\text{ otherwise }}I'=I_{C}\cup I_{A}}$

• ω-замыкание : если не содержит пустого слова, то существует автомат Бюхи, распознающий язык ${\displaystyle \scriptstyle L(C)}$ ${\displaystyle \scriptstyle L(C)^{\omega }.}$

Доказательство: Автомат Бюхи, который распознает, строится в два этапа. Во-первых, мы строим конечный автомат A' такой, что A' также распознает, но нет входящих переходов в начальные состояния A'. Итак, где Обратите внимание, что поскольку не содержит пустую строку. Во-вторых, мы построим автомат Бюхи A", который распознает , добавляя цикл обратно в начальное состояние A'. Итак, , где ${\displaystyle \scriptstyle L(C)^{\omega }}$ ${\displaystyle \scriptstyle L(C)}$ ${\displaystyle \scriptstyle A'=(Q_{C}\cup \{q_{\text{new}}\},\Sigma ,\Delta ',\{q_{\text{new}}\},F_{C}),}$ ${\displaystyle \scriptstyle \Delta '=\Delta _{C}\cup \{(q_{\text{new}},a,q')|\exists q\in I_{C}.(q,a,q')\in \Delta _{C}\}.}$ ${\displaystyle \scriptstyle L(C)=L(A')}$ ${\displaystyle \scriptstyle L(C)}$ ${\displaystyle \scriptstyle L(C)^{\omega }}$ ${\displaystyle \scriptstyle A''=(Q_{C}\cup \{q_{\text{new}}\},\Sigma ,\Delta '',\{q_{\text{new}}\},\{q_{\text{new}}\})}$ ${\displaystyle \scriptstyle \Delta ''=\Delta '\cup \{(q,a,q_{\text{new}})|\exists q'\in F_{C}.(q,a,q')\in \Delta '\}.}$

• Дополнение : существует автомат Бюхи, который распознает язык. ${\displaystyle \scriptstyle \Sigma ^{\omega }/L(A).}$

Доказательство: Доказательство представлено здесь .

Распознаваемые языки

Автоматы Бюхи распознают ω-регулярные языки . Используя определение ω-регулярного языка и приведенные выше свойства замыкания автоматов Бюхи, можно легко показать, что автомат Бюхи может быть построен таким образом, что он распознает любой заданный ω-регулярный язык. Для обратного см. построение ω-регулярного языка для автомата Бюхи.

Детерминированные и недетерминированные автоматы Бюхи

Недетерминированный автомат Бюхи, распознающий ⁠ ⁠ ${\displaystyle (0\cup 1)^{*}0^{\omega }}$

Класс детерминированных автоматов Бюхи недостаточен для охвата всех омега-регулярных языков. В частности, не существует детерминированного автомата Бюхи, распознающего язык ⁠ ⁠ ${\displaystyle (0\cup 1)^{*}0^{\omega }}$ , который содержит ровно слова, в которых 1 встречается только конечное число раз. Мы можем показать от противного, что такого детерминированного автомата Бюхи не существует. Предположим, что A — детерминированный автомат Бюхи, распознающий ⁠ ⁠ ${\displaystyle (0\cup 1)^{*}0^{\omega }}$ с конечным множеством состояний F . A принимает ⁠ ⁠ ${\displaystyle 0^{\omega }}$ . Таким образом, A посетит некоторое состояние в F после прочтения некоторого конечного префикса ⁠ ⁠ ${\displaystyle 0^{\omega }}$ , скажем, после ⁠ ⁠ ${\displaystyle i_{0}}$ -й буквы. A также принимает ω-слово Поэтому для некоторого ⁠ ⁠ после префикса автомат посетит некоторое состояние в F . Продолжая эту конструкцию , генерируется ω-слово , которое заставляет A посещать некоторое состояние в F бесконечно часто, и слово не находится в ⁠ ⁠ Противоречии. ${\displaystyle 0^{i_{0}}10^{\omega }.}$ ${\displaystyle i_{1}}$ ${\displaystyle 0^{i_{0}}10^{i_{1}}}$ ${\displaystyle 0^{i_{0}}10^{i_{1}}10^{i_{2}}\dots }$ ${\displaystyle (0\cup 1)^{*}0^{\omega }.}$

Класс языков, распознаваемых детерминированными автоматами Бюхи, характеризуется следующей леммой.

Лемма: ω-язык распознаётся детерминированным автоматом Бюхи, если он является предельным языком некоторого регулярного языка .

Доказательство: Любой детерминированный автомат Бюхи A можно рассматривать как детерминированный конечный автомат A' и наоборот, поскольку оба типа автомата определяются как 5-кортеж одних и тех же компонентов, различается только интерпретация условия принятия. Мы покажем, что ⁠ ⁠ ${\displaystyle L(A)}$ является предельным языком ⁠ ⁠ ${\displaystyle L(A')}$ . ω-слово принимается A , если оно заставит A посещать конечные состояния бесконечно часто. Таким образом, бесконечно много конечных префиксов этого ω-слова будут приняты A' . Следовательно, ⁠ ⁠ ${\displaystyle L(A)}$ является предельным языком ⁠ ⁠ ${\displaystyle L(A')}$ .

Алгоритмы

Проверка моделей систем с конечным числом состояний часто может быть переведена в различные операции над автоматами Бюхи. В дополнение к операциям замыкания, представленным выше, ниже приведены некоторые полезные операции для приложений автоматов Бюхи.

Детерминизация

Поскольку детерминированные автоматы Бюхи строго менее выразительны, чем недетерминированные автоматы, не может быть алгоритма для детерминизации автоматов Бюхи. Однако теорема Макнотона и конструкция Сафры предоставляют алгоритмы, которые могут перевести автомат Бюхи в детерминированный автомат Мюллера или детерминированный автомат Рабина . ^[2]

Проверка пустоты

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

Эффективный алгоритм, позволяющий проверить пустоту автомата Бюхи:

1. Рассмотрим автомат как ориентированный граф и разложим его на сильно связанные компоненты (ССК).
2. Запустите поиск (например, поиск в глубину ), чтобы определить, какие SCC достижимы из начального состояния.
3. Проверьте, существует ли нетривиальный SCC, который достижим и содержит конечное состояние.

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

Минимизация

Минимизация детерминированных автоматов Бюхи (т. е. при наличии детерминированного автомата Бюхи нахождение детерминированного автомата Бюхи, распознающего тот же язык с минимальным числом состояний) является NP-полной задачей. ^[3] Это контрастирует с минимизацией DFA , которая может быть выполнена за полиномиальное время.

Варианты

• Автомат Co-Büchi
• Слабый автомат Бюхи
• Полудетерминированный автомат Бюхи
• Обобщенный автомат Бюхи

Переход от других моделей описания к недетерминированным автоматам Бюхи

Отобобщенные автоматы Бюхи(GBA)

Несколько наборов состояний в состоянии принятия могут быть переведены в один набор состояний с помощью конструкции автомата, которая известна как «конструкция подсчета». Допустим, A  = (Q,Σ,∆,q ₀ ,{F ₁ ,...,F _n }) — это GBA, где F ₁ ,...,F _n — это наборы состояний принятия, тогда эквивалентный автомат Бюхи — это A'  = (Q', Σ, ∆',q' ₀ ,F'), где

• Q' = Q × {1,...,n}
• q' ₀ = ( q ₀ ,1 )
• ∆' = { ( (q,i), a, (q',j) ) | (q,a,q') ∈ ∆ и если q ∈ F _{i ,} то j=((i+1) mod n) иначе j=i }
• Ф'=Ф ₁ × {1}

ОтЛинейная временная логикаформула

Перевод из линейной временной логической формулы в обобщенный автомат Бюхи приведен здесь . А перевод из обобщенного автомата Бюхи в автомат Бюхи представлен выше.

Отавтоматы Мюллера

Данный автомат Мюллера может быть преобразован в эквивалентный автомат Бюхи с помощью следующей конструкции автомата. Предположим, что A  = (Q,Σ,∆,Q ₀ ,{F ₀ ,...,F _n }) — автомат Мюллера, где F ₀ ,...,F _n — множества допускающих состояний. Эквивалентный автомат Бюхи — это A'  = (Q', Σ, ∆',Q ₀ ,F'), где

• Q' = Q ∪  ∪ ⁿ _i=0 {i} × F _i  × 2 ^{F _i}
• ∆'= ∆ ∪ ∆ ₁  ∪ ∆ ₂ , где
  • ∆ ₁  ={ ( q, a, (i,q',∅) ) | (q, a, q') ∈ ∆ и q' ∈ F _i }
  • ∆ ₂ ={ ( (i,q,R), a, (i,q',R') ) | (q,a,q')∈∆ и q,q' ∈ F _i и если R=F _i то R'= ∅ в противном случае R'=R∪{q} }
• F'= ∪ ⁿ _i=0 {i} × F _i  × { _Fi }

A' сохраняет исходный набор состояний из A и добавляет к ним дополнительные состояния. Автомат Бюхи A' моделирует автомат Мюллера A следующим образом: в начале входного слова выполнение A' следует за выполнением A , поскольку начальные состояния одинаковы и ∆' содержит ∆. В некоторой недетерминированно выбранной позиции во входном слове A' решает перейти в новые добавленные состояния с помощью перехода в ∆ ₁ . Затем переходы в ∆ ₂ пытаются посетить все состояния F _i и продолжают расти R . Как только R становится равным F _i , он сбрасывается в пустой набор, и ∆ ₂ пытается посетить все состояния состояний F _i снова и снова. Таким образом, если состояния R = F _i посещаются бесконечно часто, то A' принимает соответствующий ввод, и A тоже . Эта конструкция точно следует первой части доказательства теоремы Макнотона .

Из структур Крипке

Пусть заданная структура Крипке определяется как M = ⟨ Q , I , R , L , AP ⟩, где Q — множество состояний, I — множество начальных состояний, R — отношение между двумя состояниями, также интерпретируемое как ребро, L — метка для состояния, а AP — множество атомарных предложений, которые образуют  L .

Автомат Бюхи будет иметь следующие характеристики:

${\displaystyle Q_{\text{final}}=Q\cup \{{\text{init}}\}}$

${\displaystyle \Sigma =2^{AP}}$

${\displaystyle I=\{{\text{init}}\}}$

${\displaystyle F=Q\cup \{{\text{init}}\}}$

${\displaystyle \delta =q{\overrightarrow {a}}p}$если ( q , p ) принадлежит R и L ( p ) = a

и init q, если q принадлежит I и L ( q ) = a . ${\displaystyle {\overrightarrow {a}}}$

Однако следует отметить, что существует разница в интерпретации между структурами Крипке и автоматами Бюхи. В то время как первая явно называет полярность каждой переменной состояния для каждого состояния, последняя просто объявляет текущий набор переменных, содержащих или не содержащих истину. Она абсолютно ничего не говорит о других переменных, которые могут присутствовать в модели.

Дополнение

В теории автоматов дополнение автомата Бюхи — это задача дополнения автомата Бюхи, т. е. построения другого автомата, распознающего дополнение ω-регулярного языка, распознаваемого данным автоматом Бюхи. Существование алгоритмов для такого построения доказывает, что множество ω-регулярных языков замкнуто относительно дополнения.

Эта конструкция особенно сложна по сравнению с конструкциями для других свойств замыкания автоматов Бюхи. Первая конструкция была представлена ​​Бюхи в 1962 году. ^[4] Позднее были разработаны другие конструкции, которые позволили эффективное и оптимальное дополнение. ^{[5] [6] [7] [8] [9]}

Конструкция Бюхи

Бюхи представил ^[4] конструкцию двойного экспоненциального дополнения в логической форме. Здесь мы имеем его конструкцию в современных обозначениях, используемых в теории автоматов. Пусть A  = ( Q ,Σ,Δ, Q ₀ , F ) — автомат Бюхи. Пусть ~ _A — отношение эквивалентности над элементами Σ ⁺ такое, что для каждого v,w ∈ Σ ⁺ , v  ~ _A  w тогда и только тогда, когда для всех p,q ∈ Q , A имеет пробег от p до q над v тогда и только тогда, когда это возможно над w и, кроме того, A имеет пробег через F от p до q над v тогда и только тогда, когда это возможно над w . Каждый класс ~ _A определяет отображение f : Q → 2 ^Q × 2 ^Q следующим образом: для каждого состояния p ∈ Q имеем ( Q ₁ , Q ₂ )= f ( p ), где Q ₁ = { q ∈ Q | w может переместить автомат A из p в q } и Q ₂ = { q ∈ Q | w может переместить автомат A из p в q через состояние в F }. Обратите внимание, что Q ₂ ⊆ Q ₁ . Если f — отображение, определяемое таким образом, мы обозначаем (уникальный) класс, определяющий f , через L _f .

Следующие три теоремы дают построение дополнения к A с использованием классов эквивалентности ~ _A.

Теорема 1: ~ _A имеет конечное число эквивалентных классов, и каждый класс является регулярным языком .
Доказательство: Поскольку существует конечное число f : Q → 2 ^Q × 2 ^Q , отношение ~ _A имеет конечное число классов эквивалентности. Теперь покажем, что L _f является регулярным языком. Для p , q ∈ Q и i ∈ {0,1} пусть A _{i , p , q} = ( {0,1}× Q , Σ, Δ ₁ ∪Δ ₂ , {(0, p )}, {( i , q )} ) — недетерминированный конечный автомат , где Δ ₁ = { ((0, q ₁ ),(0, q ₂ )) | ( q ₁ , q ₂ ) ∈ Δ} ∪ { ((1, q ₁ ),(1, q ₂ )) | ( q ₁ , q ₂ ) ∈ Δ}, и Δ ₂ = { ((0, q ₁ ),(1, q ₂ )) | q ₁ ∈ F ∧ ( q ₁ , q ₂ ) ∈ Δ }. Пусть Q' ⊆ Q . Пусть α _{p ,Q'} = ∩{ L ( A _{1, p , q} ) | q ∈ Q'}, что является множеством слов, которые могут переместить A из p во все состояния в Q' через некоторое состояние в F . Пусть β _{p ,Q'} = ∩{ L ( A _{0, p , q} )- L ( A _{1, p , q} )-{ε} | q ∈ Q'}, что является множеством непустых слов, которые могут переместить A из p во все состояния в Q' и не имеют пробега, который проходит через какое-либо состояние в F . Пусть γ _{p ,Q'} = ∩{ Σ ⁺ - L ( A _{0, p , q} ) | q ∈ Q'}, что является множеством непустых слов, которые не могут переместить Aиз p в любое из состояний в Q'. Поскольку регулярные языки замкнуты относительно конечных пересечений и относительных дополнений, каждое α _{p ,Q'} , β _{p ,Q'} и γ _{p ,Q'} является регулярным. По определениям, L _f = ∩{ α _{p , Q 2} ∩ β _{p , Q 1 - Q 2} ∩ γ _{p , Q - Q 1} | ( Q ₁ , Q ₂ )= f ( p ) ∧ p ∈ Q }.

Теорема 2: Для каждого w ∈ Σ ^ω существуют ~ _A классов L _f и L _g такие, что w ∈ L _f ( L _g ) ^ω .
Доказательство: Мы будем использовать бесконечную теорему Рамсея для доказательства этой теоремы. Пусть w = a ₀ a ₁ ... и w ( i , j ) = a _i ... a _{j -1} . Рассмотрим множество натуральных чисел N . Пусть классы эквивалентности ~ _A будут цветами подмножеств N размера 2. Мы назначаем цвета следующим образом. Для каждого i < j пусть цвет { i , j } будет классом эквивалентности, в котором встречается w ( i , j ). По бесконечной теореме Рамсея мы можем найти бесконечное множество X ⊆ N такое, что каждое подмножество X размера 2 имеет один и тот же цвет. Пусть 0 < i ₀ < i ₁ < i ₂ .... ∈ X . Пусть f — определяющее отображение класса эквивалентности, такое что w (0, i ₀ ) ∈ L _f . Пусть g — определяющее отображение класса эквивалентности, такое что для каждого j >0, w ( i _{j -1} , i _j ) ∈ L _g . Тогда w ∈ L _f ( L _g ) ^ω .

Теорема 3: Пусть L _f и L _g — классы эквивалентности ~ _A . Тогда L _f ( L _g ) ^ω либо является подмножеством L ( A ), либо не пересекается с L ( A ).
Доказательство: Предположим, что существует слово w ∈ L ( A ) ∩ L _f ( L _g ) ^ω , в противном случае теорема выполняется тривиально. Пусть r — допускающий запуск A по входу w . Нам нужно показать, что каждое слово w' ∈ L _f ( L _g ) ^ω также принадлежит L ( A ), т. е. существует запуск r' A по входу w' такой, что состояние из F встречается в r' бесконечно часто. Поскольку w ∈ L _f ( L _g ) ^ω , пусть w ₀ w ₁ w ₂ ... = w такой, что w ₀ ∈ L _f и для каждого i > 0, w _i ∈ L _g . Пусть s _i будет состоянием в r после потребления w ₀ ... w _i . Пусть I будет набором индексов, таким что i ∈ I тогда и только тогда, когда сегмент пробега в r от s _i до s _{i +1} содержит состояние из F . I должно быть бесконечным набором. Аналогично, мы можем разбить слово w'. Пусть w' ₀ w' ₁ w' ₂ ... = w', таким образом, что w' ₀ ∈ L _f и для каждого i > 0, w' _i ∈ L _g . Мы строим r' индуктивно следующим образом. Пусть первое состояние r' будет таким же, как r . По определению L _f , мы можем выбрать сегмент пробега на слове w' ₀ для достижения s ₀. По предположению индукции, у нас есть запуск на w' ₀ ...w' _i , который достигает s _i . По определению L _g , мы можем расширить запуск вдоль сегмента слова w' _{i +1} таким образом, что расширение достигнет s _i+1 и посетит состояние в F , если i ∈ I . Полученный в результате этого процесса r' будет иметь бесконечно много сегментов запуска, содержащих состояния из F , поскольку I бесконечно. Следовательно, r' является принимающим запуском и w' ∈ L ( A ).

Согласно приведенным выше теоремам, мы можем представить Σ ^ω - L ( A ) как конечное объединение ω-регулярных языков вида L _f ( L _g ) ^ω , где L _f и L _g — классы эквивалентности ~ _A . Следовательно, Σ ^ω - L ( A ) — ω-регулярный язык. Мы можем перевести язык в автомат Бюхи. Эта конструкция дважды экспоненциальна по размеру A .

Ссылки

1. Бюхи, Дж. Р. (1962). «О методе принятия решений в ограниченной арифметике второго порядка». Собрание сочинений Дж. Ричарда Бюхи . Стэнфорд: Stanford University Press. стр. 425–435. doi :10.1007/978-1-4613-8928-6_23. ISBN 978-1-4613-8930-9. {{cite book}}: |journal=проигнорировано ( помощь )
2. Сафра, С. (1988), «О сложности ω-автоматов», Труды 29-го ежегодного симпозиума по основам компьютерной науки (FOCS '88) , Вашингтон, округ Колумбия, США: IEEE Computer Society, стр. 319–327, doi :10.1109/SFCS.1988.21948, ISBN 0-8186-0877-3, S2CID  206559211.
3. Шеве, Свен (2010). «Минимизация детерминированных автоматов четности и Бюхи и относительная минимизация детерминированных конечных автоматов». arXiv : 1007.1333 [cs.FL].
4. Büchi, JR (1962), «О методе принятия решений в ограниченной арифметике второго порядка», Труды Международного конгресса по логике, методу и философии науки, Стэнфорд, 1960 , Стэнфорд: Stanford University Press, стр. 1–12.
5. Макнотон, Р. (1966), «Тестирование и генерация бесконечных последовательностей конечным автоматом», Информация и управление , 9 (5): 521–530, doi : 10.1016/s0019-9958(66)80013-x.
6. Sistla, AP; Vardi, MY ; Wolper, P. (1987), «Проблема дополнения для автоматов Бюхи с приложениями к темпоральной логике», Theoretical Computer Science , 49 (2–3): 217–237, doi : 10.1016/0304-3975(87)90008-9.
7. Сафра, С. (октябрь 1988 г.), «О сложности ω-автоматов», Труды 29-го симпозиума IEEE по основам компьютерной науки , Уайт-Плейнс, Нью-Йорк , стр. 319–327..
8. Купферман, О .; Варди, М.Ю. (июль 2001 г.), «Слабые чередующиеся автоматы не такие уж слабые», ACM Transactions on Computational Logic , 2 (3): 408–429, doi :10.1145/377978.377993.
9. Шеве, Свен (2009). Büchi Complementation Made Tight. STACS.

• Бахадыр Хуссаинов; Анил Нерод (6 декабря 2012 г.). Теория автоматов и ее применение. Springer Science & Business Media. ISBN 978-1-4612-0171-7.
• Томас, Вольфганг (1990). «Автоматы на бесконечных объектах». В Van Leeuwen (ред.). Справочник по теоретической информатике . Elsevier. С. 133–164.

Внешние ссылки

• «Конечные автоматы на бесконечных входах» (PDF) .
• Варди, Моше Й. «Автоматно-теоретический подход к линейной темпоральной логике». CiteSeerX  10.1.1.125.8126 .