ω-автомат - ω-automaton

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

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

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

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

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

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

Вход для A представляет собой бесконечную строку в алфавите Е, т.е. представляет собой бесконечную последовательность α = ( 1 , 2 , 3 , ...). Запуска из А на такой вход бесконечная последовательность ρ = ( г 0 , г 1 , г 2 , ...) состояний, определяется следующим образом :

  • г 0 знак равно q 0 .
  • r 1 = δ ( r 0 , a 1 ).
  • r 2 = δ ( r 1 , a 2 ).
...
  • r n = δ ( r n -1 , a n ).

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

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

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

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

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

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

Запуск из А на входных a = ( 1 , 2 , 3 , ...) любая бесконечная последовательность ρ = ( г 0 , г 1 , г 2 , ...) состояний , которая удовлетворяет следующие условия :

  • r 0 является элементом Q 0 .
  • r 1 является элементом ∆ ( r 0 , a 1 ).
  • r 2 является элементом Δ ( r 1 , a 2 ).
...
  • r n является элементом Δ ( r n -1 , a n ).

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

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

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

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

  • Бюх автомат является ω-автомат , который использует следующее условие приема, для некоторого подмножества F из Q :
Состояние Бюхи
A принимает в точности те серии ρ, для которых Inf (ρ) ∩  F не пусто, т. Е. Существует принимающее состояние, которое бесконечно часто встречается в ρ.
  • А Автомат Рабина - это ω-автоматA,который использует следующее условие приемлемости для некоторого множества Ω пар (B i , G i ) множеств состояний:
Условие Рабина
A принимает в точности те серии ρ, для которых существует пара (B i , G i ) в Ω такая, что B i  ∩ Inf (ρ) пусто и G i  ∩ Inf (ρ) не пусто.
  • Streett автомат является ω-автомат , который использует следующее условие приема, для некоторого множества Q , пар (B я , G я ) множеств состояний:
Состояние улицы
A принимает ровно те пробеги ρ такие, что для всех пар (B i , G i ) в Ω, B i  ∩ Inf (ρ) пусто или G i  ∩ Inf (ρ) не пусто.
  • Автомат четности является автоматом которого множество состояний Q  = {0,1,2, ..., к } для некоторого натурального числа  к , и имеет следующее условие приема:
Условие четности
A принимает ρ тогда и только тогда, когда наименьшее число в Inf (ρ) четно.
Состояние Мюллера
Принимает именно те пробеги р , для которых Inf (ρ) является элементом  F .

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

Пример

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

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

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

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

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

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

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

Поскольку недетерминированные автоматы Мюллера, Рабина, Стритта, четности и Бюхи одинаково выразительны, они могут быть преобразованы друг в друга. Используем следующую аббревиатуру : например, NB обозначает недетерминированный ω-автомат Бюхи, а DP обозначает ω-автомат детерминированной четности. Тогда имеет место следующее.

  • Ясно, что любой детерминированный автомат можно рассматривать как недетерминированный.
  • без взрыва в пространстве состояний.
  • с полиномиальным раздутием в пространстве состояний, т. е. количество состояний в результирующем NB равно , где - количество состояний в NB, а - количество принимающих пар Рабина (см., например,).
  • с экспоненциальным раздутием в пространстве состояний.
  • с экспоненциальным раздутием в пространстве состояний. Этот результат детерминизации использует конструкцию Сафры .

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

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

  • Фарвер, Берндт (2002), «ω-Автоматы», в Grädel, Erich; Томас, Вольфганг; Уилке, Томас (ред.), Автоматы, логика и бесконечные игры , Конспект лекций по информатике , 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.


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