Ω-автомат - Ω-automaton

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

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

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

Детерминированные ω-автоматы

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

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

An Вход за А - бесконечная строка над алфавитом Σ, т.е. бесконечная последовательность α = (а₁,а₂,а₃, ...). пробег из А на таком входе - бесконечная последовательность ρ = (р₀,р₁,р₂, ...) состояний, определяемых следующим образом:

р₀ = q₀.
р₁ = δ (р₀,а₁).
р₂ = δ (р₁,а₂).

...

р_п = δ (р_п-1,а_п).

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

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

Недетерминированные ω-автоматы

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

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

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

А пробег из А на входе α = (а₁,а₂,а₃, ...) - любая бесконечная последовательность ρ = (р₀,р₁,р₂, ...) состояний, удовлетворяющих следующим условиям:

р₀ является элементом Q₀.
р₁ является элементом Δ (р₀,а₁).
р₂ является элементом Δ (р₁,а₂).

...

р_п является элементом Δ (р_п-1,а_п).

Недетерминированный ω-автомат может допускать множество различных запусков на любом заданном входе или вообще не допускать ни одного запуска. Ввод принимается, если принимается хотя бы один из возможных прогонов. Принимается ли пробег, зависит только от Acc, как и для детерминированных ω-автоматов. Любой детерминированный ω-автомат можно рассматривать как недетерминированный ω-автомат, если взять ∆ за график δ. Тогда определения прогонов и приемки для детерминированных ω-автоматов являются частными случаями недетерминированных случаев.

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

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

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

А Büchi автомат является ω-автоматом А который использует следующее условие принятия для некоторого подмножества F из Q:

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

С F конечно, это равносильно тому, что ρ_п принимает бесконечно много натуральных чиселп.

А Автомат Рабина является ω-автоматом А который использует следующее условие приемлемости для некоторого множества Ω пар (B_я,ГРАММ_я) наборов состояний:

Условие Рабина: А принимает именно те прогоны ρ, для которых существует пара (B_я,ГРАММ_я) в Ω такое, что B_я ∩ Inf (ρ) пусто и G_я ∩ Inf (ρ) не пусто.

А Автомат Streett является ω-автоматом А который использует следующее условие приемлемости для некоторого множества Ω пар (B_я,ГРАММ_я) наборов состояний:

Состояние улицы: А принимает в точности такие прогоны ρ, что для всех пар (B_я,ГРАММ_я) в Ω, B_я ∩ Inf (ρ) пусто или G_я ∩ Inf (ρ) не пусто.

Условие Стритта - это отрицание условия Рабина. Поэтому детерминированный автомат Стритта принимает в точности то дополнение к языку, которое принимает детерминированный автомат Рабина, состоящее из тех же данных.

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

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

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

Состояние Мюллера: А принимает в точности те серии ρ, для которых Inf (ρ) является элементомF.

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

Пример

Недетерминированный автомат Бюхи, распознающий (0∪1) * 0^ω

Следующий ω-язык 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₁, он не может вернуться. Если читается еще один 1, состояние преемника отсутствует.)

Обратите внимание, что указанный выше язык не может быть распознан детерминированным Büchi автомат, который строго менее выразительный чем его недетерминированный аналог.

Выразительная сила ω-автоматов

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

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

Преобразование между ω-автоматами

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

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

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

дальнейшее чтение

Фарвер, Берндт (2002), «ω-Автоматы», в Grädel, Erich; Томас, Вольфганг; Вилке, Томас (ред.), Автоматы, логика и бесконечные игры, Конспект лекций по информатике, Springer, стр. 3–21, ISBN 978-3-540-00388-5.
Перрен, Доминик; Пин, Жан-Эрик (2004), Бесконечные слова: автоматы, полугруппы, логика и игры, Эльзевир, 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.