Чередующийся автомат с синхронизацией по времени - Википедия - Alternating timed automaton

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

ATA более выразительны, чем таймер. автомат с чередованием часов (OCATA) это ограничение ATA, позволяющее использовать одни часы. OCATA позволяют выражать синхронизированные языки что не может быть выражено с помощью временного автомата.^[1]

Определение

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

Отличие от таймерного автомата

Учитывая набор ${ displaystyle X}$, позволять ${ Displaystyle { mathcal {B}} ^ {+} (X)}$ множество положительных булевых комбинаций элементов ${ displaystyle X}$. Т.е. набор, содержащий элементы ${ displaystyle X}$, и содержащий ${ displaystyle phi land psi}$ и ${ displaystyle phi lor psi}$, за ${ displaystyle phi, psi in { mathcal {B}} ^ {+} (X)}$.

За каждую букву ${ displaystyle a}$ и расположение ${ displaystyle ell}$, позволять ${ displaystyle { mathcal {B}} _ {a, ell}}$ набор ограничений часов, так что их зоны раздел ${ Displaystyle mathbb {R} _ { geq 0} ^ {| X |}}$, с ${ displaystyle | X |}$ количество часов. Учитывая оценку часов ${ displaystyle nu}$, позволять ${ Displaystyle с (а, ell, nu)}$ быть единственным часовым ограничением ${ displaystyle { mathcal {B}} _ {a, ell}}$ которым удовлетворяется ${ displaystyle nu}$.

Чередующийся синхронизированный автомат содержит функцию перехода, которая ассоциируется с 3-кортежем ${ Displaystyle ( ell, а, с)}$, с ${ displaystyle c in { mathcal {B}} _ {a, ell}}$, к элементу ${ Displaystyle { mathcal {B}} ^ {+} (L times { mathcal {P}} (C))}$.

Например, ${ displaystyle ( ell _ {1}, emptyset) lor (( ell _ {2}, {x }) land ( ell _ {2}, {y }))}$ является элементом ${ Displaystyle { mathcal {B}} ^ {+} (L times { mathcal {P}} (C))}$. Интуитивно это означает, что бег можно продолжить, переместившись в нужное место. ${ displaystyle ell _ {1}}$и не сбрасывать часы. Или переместившись на место ${ displaystyle ell _ {2}}$ и должен быть успешным, когда либо ${ displaystyle x}$ или же ${ displaystyle y}$ сброшен.

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

Формально автомат с переменным временем кортеж ${ displaystyle { mathcal {A}} = langle Sigma, L, L_ {0}, C, F, E rangle}$ который состоит из следующих компонентов:

• Σ - конечное множество, называемое алфавит или же действия из ${ displaystyle { mathcal {A}}}$.
• ${ displaystyle L}$ это конечный набор. Элементы ${ displaystyle L}$ называются локации или же штатов ${ displaystyle { mathcal {A}}}$.
• ${ displaystyle C}$ конечное множество, называемое часы из ${ displaystyle { mathcal {A}}}$.
• ${ Displaystyle L_ {0} substeq L}$ - это набор начальных местоположений.
• ${ Displaystyle F substeq L}$ - это набор принимающих местоположений.
• ${ displaystyle E substeq L times Sigma times { mathcal {B}} (C) to { mathcal {B}} ^ {+} (L times { mathcal {P}} (C) )}$ это функция переходов из ${ displaystyle { mathcal {A}}}$. Это частичная функция, определенная, как описано в предыдущем разделе.

Любое логическое выражение можно переписать в эквивалентное выражение в дизъюнктивная нормальная форма. В представлении ATA каждая дизъюнкция представлена ​​отдельной стрелкой. Каждая конъюнкция дизъюнкции представлена ​​набором стрелок с одинаковым хвостом и несколькими головками. Хвост помечен буквой, а каждая голова помечена набором часов, который он сбрасывает.

Пробег

Теперь мы определим запуск чередующегося синхронизированного автомата над синхронизированным словом ${ displaystyle w = ( sigma _ {1}, t_ {1}), ( sigma _ {2}, t_ {2}), dots,}$. Есть два эквивалентных способа определить серию: либо как дерево, либо как игра.

Беги как дерево

В этом определении пробега пробег - это больше не список пар, а укоренившееся дерево. Узлы дерева перемещения помечены парами с указанием местоположения и оценки часов. Дерево определяется следующим образом:

• корень дерева имеет форму ${ displaystyle ( ell _ {0}, nu _ {0})}$ с ${ displaystyle ell _ {0} in L_ {0}}$,
• Рассмотрим узел ${ displaystyle n}$ дерева на глубине ${ displaystyle i}$, с этикеткой ${ Displaystyle ( ell, nu)}$. Без ограничения общности предположим, что ${ Displaystyle Е (а_ {я + 1}, ell, с (а, ell, nu))}$ в дизъюнктивная нормальная форма, т.е. имеет вид ${ Displaystyle bigvee _ {я = 1} ^ {n} bigwedge _ {j = 1} ^ {m_ {i}} ( ell _ {i, j}, r_ {i, j})}$. Тогда узел ${ displaystyle n}$ имеет ${ displaystyle m_ {i}}$ дети, для некоторых ${ Displaystyle 1 Leq я Leq п}$. В ${ displaystyle j}$-й ребенок помечен ${ displaystyle ( ell _ {я, j}, ( nu + t_ {i + 1} -t_ {i}) [r_ {i, j} to 0]}$.

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

Беги как игра

Забег также можно определить как игру для двух игроков. ${ displaystyle G_ {A, w}}$. Назовем двух игроков «игроком» и «противником». Цель игрока состоит в том, чтобы создать приемный прогон, а цель противника - создать отклоняющий (не принимающий) прогон.

Каждое состояние игры представляет собой кортеж, состоящий из местоположения, оценки часов, позиции в слове и, возможно, элемента ${ Displaystyle { mathcal {B}} ^ {+} (L times { mathcal {P}} (C))}$. Интуитивно понятно, что кортеж ${ Displaystyle ( ell, nu, я, b)}$ означает, что пробег прочитал ${ displaystyle i}$ буквы, находится в месте ${ displaystyle ell}$, с часовым значением ${ displaystyle nu}$, и что переход будет описан ${ displaystyle b}$. Прогон определяется следующим образом:

• Начальное состояние имеет вид ${ displaystyle ( ell _ {0}, nu _ {0}, 0)}$, для некоторых ${ displaystyle ell _ {0} in L_ {0}}$.
• учитывая состояние ${ Displaystyle ( ell, nu, я)}$, если длина слова ${ displaystyle i}$, пробег заканчивается. В противном случае его преемником будет ${ displaystyle ( ell, nu, i, c (a_ {i + 1}, ell, nu))}$.
• Преемник государства ${ Displaystyle ( ell, nu, я, ( ell ', г))}$ это состояние ${ displaystyle ( ell ', nu + t_ {i} -t_ {i-1} [r to 0], i + 1)}$,
• Преемник государства ${ Displaystyle ( ell, nu, я, phi lor psi)}$ выбирается игроком, либо ${ Displaystyle ( элл, ню, я, фи)}$ или же ${ displaystyle ( ell, nu, i, psi)}$,
• Преемник государства ${ displaystyle ( ell, nu, i, phi land psi)}$ выбирается оппонентом, либо ${ Displaystyle ( элл, ню, я, фи)}$ или же ${ displaystyle ( ell, nu, i, psi)}$.

Множество последовательных состояний, начинающихся в состоянии вида ${ Displaystyle ( ell, nu, я)}$ и завершение до следующего такого состояния называется фаза.

Определение принимающего прогона то же, что и для синхронизированные автоматы.

Подкласс ATA

Один автомат с чередованием часов

А автомат с чередованием часов (OCATA) - это автомат с чередованием времени, использующий одни часы.

Выразительность OCATA и таймерного автомата несравнима.

Например, язык над алфавитом ${ Displaystyle {а }}$ такой, что никогда не бывает ровно одной единицы времени между двумя буквами, не может быть распознан автоматом по времени. Однако изображенный рядом OCATA

OCATA принимает язык, на котором не встречаются две буквы за 1 единицу времени.

принимает это

OCATA принимает язык, на котором не встречаются две буквы за 1 единицу времени.

. В этом автомате с чередованием по времени запускаются две ветви. Ветка перезагружает часы ${ displaystyle x}$, и гарантирует, что каждый раз в будущем, когда будет отправлено письмо, часы ${ displaystyle x}$ отличается от 1. Это гарантирует, что время между этой буквой и следующими не равно единице. Вторая ветвь только ожидает отправки других писем и выполняет ту же проверку.

Чисто универсальный и чисто экзистенциальный ATA

Говорят, что ATA чисто универсальный (соответственно, чисто экзизенциальный), если его функция перехода не использует дизъюнкцию (соответственно конъюнкцию).

Чисто-экзистенциальные ATA столь же выразительны, как и недетерминированные временные автоматы.

Закрытие

Класс языка, принятый ATA и OCATA, закрыт для дополнения. Конструкция поясняется для случая, когда есть единственное исходное местоположение.

Учитывая ATA ${ Displaystyle { mathcal {A}} = langle Sigma, L, {q_ {0} }, C, F, E rangle}$ принятие синхронизированного языка ${ displaystyle L}$, его дополнительный язык ${ displaystyle L ^ {c}}$ принимается автоматом ${ displaystyle A ^ {c}}$ что по сути ${ displaystyle langle Sigma, L, {q_ {0} }, C, L setminus F, E ' rangle}$, куда ${ displaystyle E '( ell, a, c)}$ определяется как ${ Displaystyle Е ( ell, а, с))}$ где дизъюнкция и конъюнкция меняются местами и ${ displaystyle E '(q_ {0}, a, c)}$ имитирует бег из каждого места ${ displaystyle L_ {0}}$ одновременно.

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

Сложность

Проблема пустоты, проблема универсальности и проблема локализации для OCATA: разрешимый но это неэлементарная проблема.

Эти три проблемы неразрешимый через ATA.

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