Дополнение к автомату Бюхи - Complementation of Büchi automaton

В теория автоматов, дополнение к автомату Бюхи является строительство другого Büchi автомат который признает дополнение ω-регулярный язык распознается данным автоматом Бюхи. Наличие алгоритмов для этой конструкции доказывает, что множество ω-регулярных языков и автоматов Бюхи являются закрыт под дополнение.

Эта конструкция особенно сложна по сравнению с конструкциями других закрывающие свойства автоматов Бюхи. Первую конструкцию Büchi представил в 1962 году.[1] Позже были разработаны другие конструкции, которые позволили эффективно и оптимально дополнять друг друга.[2][3][4][5]

Строительство Бючи

Büchi представил[1] конструкция с дважды экспоненциальным дополнением в логической форме. Здесь мы имеем его конструкцию в современных обозначениях, используемых в теории автоматов. А = (Q, Σ, Δ,Q0,F) быть Büchi автомат.Пусть ~А - отношение эквивалентности над элементами Σ+ так что для каждого v, w ∈ Σ+,v ~А ш если и только для всех р, д ∈ Q, А сбежал от п к q над v если это возможно ш и, кроме тогоА имеет пробег через F из п к q над v если это возможно шПо определению каждая карта f:Q → 2Q × 2Qопределяет класс ~АОбозначим класс LжМы интерпретируем f следующим образом.ш ∈ Lж если и только если, для каждого состояния п ∈ Q и (Q1, Q2) = f (p),ш может двигаться автомат А из пкаждому состоянию в Q1 и каждому состоянию в Q2 через государство в FОтметим, что Q2 ⊆ Q1Следующие три теоремы дают конструкцию дополнения к А используя классы эквивалентности ~А.

Теорема 1: ~А имеет конечное число эквивалентных классов, и каждый класс является обычный язык.
Доказательство:Поскольку f конечное число:Q → 2Q × 2Q, ~А имеет конечное число эквивалентных классов. Теперь покажем, что Lж является регулярным языком. Для p, q ∈ Q и i ∈ {0,1}, пусть Aя, р, д = ( {0,1}×Q, Σ, Δ1∪Δ2, {(0, p)}, {(i, q)}) быть недетерминированный конечный автомат, где Δ1 = {((0, q1), (0, q2)) | (q1, q2) ∈ Δ} ∪ {((1, q1), (1, q2)) | (q1, q2) ∈ Δ} и Δ2 = {((0, q1), (1, q2)) | q1 ∈ F ∧ (q1, q2) ∈ Δ}. Пусть Q '⊆ Q.Пусть αр, Q ' = ∩ {L (A1, п, д) | q ∈ Q '} - множество слов, которые могут перемещаться А из p во все состояния в Q 'через некоторое состояние в F.Пусть βр, Q ' = ∩ {L (A0, p, q) -L (А1, п, д) -ε | q ∈ Q '}, который представляет собой набор непустых слов, которые могут перемещаться А от p до всех состояний в Q'и не имеет пробега, проходящего через какое-либо состояние в F.Пусть γр, Q ' = ∩ {Σ+-L (А0, p, q) | q ∈ Q '}, который представляет собой набор непустых слов, которые не могут двигаться А из p в любое из состояний Q '. По определениям Lж = ∩ {αр, Q2∩βр, Q1-Q2∩γр, Q-Q1| (Q1, Q2) = f (p) ∧ p ∈ Q}.

Теорема 2: Для каждого ш ∈ Σω, есть ~А классы Lж и яграмм такой, чтош ∈ Lж(Lграмм)ω.
Доказательство: Мы будем использовать бесконечная теорема Рамсея чтобы доказать эту теорему. ш = а0а1... и ш(i, j) = ая... аj-1.Рассмотрим набор натуральных чисел N.Пусть классы эквивалентности ~А быть цветами подмножеств N размера 2. Мы назначаем цвета следующим образом. Для каждого i ш(i, j). Благодаря бесконечной теореме Рамсея можно найти бесконечное множество X ⊆ Nтакое, что каждое подмножество X размера 2 имеет один и тот же цвет. Пусть 0 0 <я1 <я2 .... ∈ X. Пусть f - определяющее отображение класса эквивалентности такое, что ш(0, я0) ∈ Lж.Пусть g - определяющее отображение класса эквивалентности такое, что для каждого j> 0ш(яj-1,яj) ∈ Lграмм.Следовательно, ш ∈ Lж(Lграмм)ω.

Теорема 3: Пусть Lж и яграмм - классы эквивалентности ~А.Lж(Lграмм)ω является либо подмножеством L(А) или не пересекаются с L(А).
Доказательство: Предположим слово ш ∈ L(А) ∩ Lж(Lграмм)ωВ противном случае теорема выполняется тривиально. Пусть r - принимающий пробег А над вводом ш. Нам нужно показать, что каждое слово w '∈ Lж(Lграмм)ωтакже в L(А), т.е. существует серия r ' А над входом w 'такой, что F встречается в r 'бесконечно часто. ш ∈ Lж(Lграмм)ω, пусть w0ш1ш2... = ш такой, что w0 ∈ Lж и для каждого i> 0 wя ∈ Lграмм.Давайтея быть состоянием в r после потребления w0... wя.Пусть I - такой набор индексов, что i ∈ I тогда и только тогда, когда отрезок пробега в r из sя к sя + 1 содержит состояние из F.I должно быть бесконечным множеством. Точно так же мы можем разбить слово w '. Пусть w'0w '1w '2... = w 'такое, что w'0 ∈ Lж и для каждого i> 0 w 'я ∈ LграммМы построим r 'индуктивно следующим образом: пусть первое состояние r' совпадает с r. По определению Lж, мы можем выбрать отрезок пробега на слове w '0 достичь s0.По предположению индукции мы имеем пробег на w '0... ш 'я что доходит до sя.По определению Lграмм, мы можем продолжить пробег по отрезку слова w 'я + 1 такое, что расширение достигает sя + 1 и посещает штат в F если i ∈ I.У r ', полученное в результате этого процесса, будет бесконечно много сегментов серии, содержащих состояния из F, поскольку I - бесконечное множество, поэтому r '- приемный пробег и w' ∈ L(А).

В силу приведенных выше теорем мы можем представить Σω-L(А) как конечное объединение ω-регулярные языки из Lж(Lграмм)ω, где Lж и яграмм являются классами эквивалентности ~А, Поэтому Σω-L(А) является ω-регулярным языком. перевести язык в автомат Бюхи. Эта конструкция двояко экспоненциальна по размеру А.

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

  1. ^ а б Бючи, Дж. Р. (1962), «О методе решения в ограниченной арифметике второго порядка», Proc. Международный конгресс по логике, методу и философии науки, Стэнфорд, 1960 г., Stanford: Stanford University Press, стр. 1–12..
  2. ^ McNaughton, R. (1966), "Проверка и создание бесконечных последовательностей с помощью конечного автомата", Информация и контроль, 9: 521–530, Дои:10.1016 / с0019-9958 (66) 80013-х.
  3. ^ Sistla, A. P .; Варди, М. Ю.; Вольпер, П. (1987), "Проблема дополнения для автоматов Бюхи с приложениями к темпоральной логике", Теоретическая информатика, 49: 217–237, Дои:10.1016/0304-3975(87)90008-9.
  4. ^ Сафра, С. (Октябрь 1988 г.), «О сложности ω-автоматов», Proc. 29-й IEEE Симпозиум по основам информатики, Уайт-Плейнс, Нью-Йорк, стр. 319–327.
  5. ^ Купферман, О .; Варди, М. Ю. (Июль 2001 г.), «Слабые переменные автоматы не так уж и слабы», Транзакции ACM по вычислительной логике, 2 (2): 408–429.