ω-автомат

В теории автоматов , разделе теоретической информатики , ω -автомат (или потоковый автомат ) — это вариация конечного автомата, которая работает на бесконечных, а не конечных строках в качестве входных данных. Поскольку ω-автоматы не останавливаются, у них есть множество условий принятия, а не просто набор состояний принятия.

ω-автоматы полезны для определения поведения систем, которые не должны завершаться, таких как аппаратное обеспечение, операционные системы и системы управления . Для таких систем может потребоваться указать свойство, например, «за каждым запросом в конечном итоге следует подтверждение», или его отрицание «существует запрос, за которым не следует подтверждение». Первое является свойством бесконечных слов: нельзя сказать о конечной последовательности, что она удовлетворяет этому свойству.

Классы ω-автоматов включают автоматы Бюхи , автоматы Рабина, автоматы Стритта, автоматы четности и автоматы Мюллера , каждый из которых является детерминированным или недетерминированным. Эти классы ω-автоматов отличаются только условиями принятия. Все они распознают в точности регулярные ω-языки, за исключением детерминированного автомата Бюхи, который строго слабее всех остальных. Хотя все эти типы автоматов распознают один и тот же набор ω-языков , они, тем не менее, различаются по краткости представления для данного ω-языка.

Формально детерминированный ω-автомат — это кортеж A  = ( Q ,Σ,δ, Q ₀ , Acc ), состоящий из следующих компонентов:

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

Вход для A — это бесконечная строка в алфавите Σ, т.е. это бесконечная последовательность α = ( a 1 , a 2 , a 3 ,...). Прогон A на _таком входе — _это бесконечная последовательность _ρ = ( r 0 , r ₁ , r ₂ , ... ₎ состояний, определяемая следующим образом:

• р ₀ = q ₀ .
• r1 ₌ δ ( r0 _, a1 ₎ .
• r2 ₌ δ ₍ r1 , a2 ₎ .

...

• то есть для каждого i : r _i = δ( r _{i -1} , a _i ).

Основная цель ω-автомата — определить подмножество множества всех входов: множество принятых входов. В то время как в случае обычного конечного автомата каждый запуск заканчивается состоянием r _n , и вход принимается тогда и только тогда, когда r _n является принимающим состоянием, определение множества принятых входов для ω-автоматов более сложно. Здесь мы должны рассмотреть весь запуск ρ. Ввод принимается, если соответствующий запуск находится в Acc . Множество принятых входных ω-слов называется распознаваемым ω-языком автомата, который обозначается как L(A).

Определение Acc как подмножества Q ^ω является чисто формальным и не подходит для практики, поскольку обычно такие множества бесконечны. Разница между различными типами ω-автоматов (Бюхи, Рабин и т. д.) состоит в том, как они кодируют некоторые подмножества Acc из Q ^ω как конечные множества, и, следовательно, в каких таких подмножествах они могут кодироваться.

Формально недетерминированный ω-автомат — это кортеж A  = ( Q , Σ, Δ, Q ₀ , Acc ), состоящий из следующих компонентов:

• Q — конечное множество . Элементы Q называются состояниями A.
• Σ — конечное множество, называемое алфавитом A.
• Δ является подмножеством Q  × Σ ×  Q и называется отношением перехода A.
• Q ₀ — это подмножество Q , называемое начальным набором состояний.
• Acc — это условие принятия , подмножество Q ^ω .

В отличие от детерминированного ω-автомата, имеющего функцию перехода δ, недетерминированная версия имеет отношение перехода Δ. Обратите внимание, что Δ можно рассматривать как функцию:  Q  × Σ →  P ( Q ) из Q  × Σ в множество степеней P ( Q ). Таким образом, если задано состояние q _n и символ a _n , следующее состояние q _{n +1} не обязательно определяется однозначно, скорее существует набор возможных следующих состояний.

Последовательность A на входе α = ( a 1 _, a 2 _, a 3 _{, ...)} — это любая бесконечная последовательность ρ = ( r ₀ , r ₁ , r ₂ ,...) состояний, которая удовлетворяет следующим условиям:

• r ₀ является элементом Q ₀ .
• r ₁ является элементом Δ( r ₀ , a ₁ ).
• r ₂ является элементом Δ( r ₁ , a ₂ ).

...

• то есть, для каждого i : r _i является элементом Δ( r _{i -1} , a _i ).

Недетерминированный ω-автомат может допускать много различных запусков на любом заданном входе или не допускать ни одного. Вход принимается, если хотя бы один из возможных запусков является приемным. Является ли запуск приемным, зависит только от Acc , как для детерминированных ω-автоматов. Каждый детерминированный ω-автомат можно рассматривать как недетерминированный ω-автомат, принимая Δ за график δ. Определения запусков и приемки для детерминированных ω-автоматов являются тогда частными случаями недетерминированных случаев.

Условиями принятия могут быть бесконечные наборы ω-слов. Однако люди в основном изучают условия принятия, которые конечно представимы. Ниже перечислены различные популярные условия принятия.

Прежде чем обсуждать список, сделаем следующее наблюдение. В случае бесконечно работающих систем часто интересно, повторяется ли определенное поведение бесконечно часто. Например, если сетевая карта получает бесконечно много запросов ping, то она может не ответить на некоторые из запросов, но должна ответить на бесконечное подмножество полученных запросов ping. Это мотивирует следующее определение: для любого запуска ρ пусть Inf(ρ) будет набором состояний, которые встречаются бесконечно часто в ρ. Это понятие определенных состояний, посещаемых бесконечно часто, будет полезно при определении следующих условий приемки.

• Автомат Бюхи — это ω-автомат A , который использует следующее условие принятия для некоторого подмножества F из Q :

состояние Бюхи

A принимает ровно те запуски ρ, для которых Inf(ρ) ∩  F не пусто, т.е. существует принимающее состояние, которое встречается бесконечно часто в ρ.

• ААвтомат Рабина — это ω-автоматA, который использует следующее условие принятия для некоторого множества Ω пар (B _i ,G _i ) множеств состояний:

состояние Рабина

A принимает ровно те запуски ρ, для которых существует пара (B _i ,G _i ) в Ω такая, что B _i  ∩ Inf(ρ) пусто, а G _i  ∩ Inf(ρ) не пусто.

• Автомат Стритта — это ω-автомат A , который использует следующее условие принятия для некоторого множества Ω пар (B _i ,G _i ) множеств состояний:

Состояние улицы

A принимает ровно те запуски ρ, что для всех пар (B _i ,G _i ) в Ω, B _i  ∩ Inf(ρ) пусто или G _i  ∩ Inf(ρ) не пусто.

• Автомат четности — это автомат A , множество состояний которого равно Q  = {0,1,2,..., k } для некоторого натурального числа  k , и который имеет следующее условие приемки:

Условие четности

A принимает ρ тогда и только тогда, когда наименьшее число в Inf(ρ) четное.

• Автомат Мюллера — это ω-автомат A , который использует следующее условие принятия для подмножества F из P ( Q ) ( множество мощности Q ):

состояние Мюллера

A принимает ровно те серии ρ , для которых Inf(ρ) является элементом  F.

Каждый автомат Бюхи можно рассматривать как автомат Мюллера. Достаточно заменить F на F ', состоящий из всех подмножеств Q , которые содержат хотя бы один элемент  F . Аналогично каждый автомат Рабина, Стритта или четности можно рассматривать как автомат Мюллера.

Следующий ω-язык L над алфавитом Σ = {0,1}, который может быть распознан недетерминированным автоматом Бюхи: L состоит из всех ω-слов в Σ ^ω, в которых 1 встречается только конечное число раз. Недетерминированному автомату Бюхи, распознающему L, нужны только два состояния q ₀ (начальное состояние) и q ₁ . Δ состоит из троек ( q ₀ ,0, q ₀ ), ( q ₀ ,1, q ₀ ), ( q ₀ ,0, q ₁ ) и ( q ₁ ,0, q ₁ ). F  = { q ₁ }. Для любого входа α, в котором 1 встречается только конечное число раз, существует запуск, который остается в состоянии q ₀ до тех пор, пока есть единицы для чтения, и переходит в состояние q ₁ после этого. Этот запуск успешен. Если существует бесконечно много единиц, то существует только один возможный запуск: тот, который всегда остается в состоянии q ₀ . (Как только машина покинула q ₀ и достигла q ₁ , она не может вернуться. Если считывается еще одна единица, последующего состояния не существует.)

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

ω-язык над конечным алфавитом Σ — это множество ω-слов над Σ, т. е. это подмножество Σ ^ω . Говорят, что ω-язык над Σ распознаётся ω-автоматом A (с тем же алфавитом), если он является множеством всех ω-слов, принимаемых A . Выразительная сила класса ω-автоматов измеряется классом всех ω-языков, которые могут быть распознаны некоторым автоматом в этом классе.

Недетерминированные автоматы Бюхи, четности, Рабина, Стритта и Мюллера, соответственно, распознают один и тот же класс ω-языков. ^[1] Они известны как ω-Клиновское замыкание регулярных языков или как регулярные ω-языки . Используя различные доказательства, можно также показать, что детерминированные автоматы четности, Рабина, Стритта и Мюллера распознают регулярные ω-языки. Из этого следует, что класс регулярных ω-языков замкнут относительно дополнения. Однако приведенный выше пример показывает, что класс детерминированных автоматов Бюхи строго слабее.

Поскольку недетерминированные автоматы Мюллера, Рабина, Стритта, четности и Бюхи одинаково выразительны, их можно перевести друг в друга. Давайте использовать следующую аббревиатуру : например, NB обозначает недетерминированный ω-автомат Бюхи, а DP обозначает детерминированный ω-автомат четности. Тогда выполняется следующее.${\displaystyle \{Н,Д\}\times \{М,Р,С,П,Б\}}$

• Очевидно, что любой детерминированный автомат можно рассматривать как недетерминированный.
• ${\displaystyle NB\rightarrow NR/NS/NP}$без взрыва в пространстве состояний.
• ${\displaystyle NR\rightarrow NB}$с полиномиальным разрушением в пространстве состояний, т.е. число состояний в результирующем NB равно , где — число состояний в NB , а — число пар приемов Рабина (см., например, ^[2] ).${\displaystyle 2нм+1}$${\displaystyle n}$${\displaystyle м}$
• ${\displaystyle NS/NM/NP\rightarrow NB}$с экспоненциальным ростом в пространстве состояний.
• ${\displaystyle NB\rightarrow DR/DP}$с экспоненциальным раздутием в пространстве состояний. Этот результат детерминизации использует конструкцию Сафры.

Подробный обзор переводов можно найти в указанном веб-источнике. ^[3]

ω-автоматы могут быть использованы для доказательства разрешимости S1S, монадической теории второго порядка (MSO) натуральных чисел при наличии преемника. Автоматы с бесконечным деревом расширяют ω-автоматы до бесконечных деревьев и могут быть использованы для доказательства разрешимости S2S , теории MSO с двумя преемниками, и это может быть расширено до теории MSO графов с ограниченной (при фиксированной границе) древовидной шириной .

• Фарвер, Берндт (2002), «ω-автоматы», в Гределе, Эрих; Томас, Вольфганг; Уилк, Томас (ред.), Автоматы, логика и бесконечные игры , Конспекты лекций по информатике , Springer, стр. 3–21, ISBN 978-3-540-00388-5.
• Перрен, Доминик; Пин, Жан-Эрик (2004), Бесконечные слова: автоматы, полугруппы, логика и игры , Elsevier , ISBN 978-0-12-532111-2
• Томас, Вольфганг (1990), «Автоматы на бесконечных объектах», в ван Леувен, Ян (ред.), Справочник по теоретической информатике, т. B , MIT Press , стр. 133–191, ISBN 978-0-262-22039-2
• Бахадыр Хуссаинов; Анил Нерод (6 декабря 2012 г.). Теория автоматов и ее применение. Springer Science & Business Media. ISBN 978-1-4612-0171-7.