Автомат с переменным временем - Alternating timed automaton - Wikipedia

В теория автоматов, автомат с переменным временем (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 c(a,\ell ,\nu )}$ быть единственным часовым ограничением ${\displaystyle {\mathcal {B}}_{a,\ell }}$ которым удовлетворяется ${\displaystyle \nu }$.

Чередующийся синхронизированный автомат содержит функцию перехода, которая ассоциируется с 3-кортежем ${\displaystyle (\ell ,a,c)}$, с ${\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}\subseteq L}$ - это набор начальных местоположений.
• ${\displaystyle F\subseteq L}$ - это набор принимающих местоположений.
• ${\displaystyle E\subseteq 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 E(a_{i+1},\ell ,c(a,\ell ,\nu ))}$ в дизъюнктивная нормальная форма, т.е. имеет вид ${\displaystyle \bigvee _{i=1}^{n}\bigwedge _{j=1}^{m_{i}}(\ell _{i,j},r_{i,j})}$. Тогда узел ${\displaystyle n}$ имеет ${\displaystyle m_{i}}$ дети, для некоторых ${\displaystyle 1\leq i\leq n}$. В ${\displaystyle j}$-й ребенок помечен ${\displaystyle (\ell _{i,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 ,i,b)}$ означает, что пробег прочитал ${\displaystyle i}$ буквы, находится в месте ${\displaystyle \ell }$, с часовым значением ${\displaystyle \nu }$, и что переход будет описан ${\displaystyle b}$. Прогон определяется следующим образом:

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

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

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

Подкласс ATA

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

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

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

Например, язык над алфавитом ${\displaystyle \{a\}}$ такой, что никогда не бывает ровно одной единицы времени между двумя буквами, не может быть распознан автоматом по времени. Однако изображенный рядом 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 E(\ell ,a,c))}$ где дизъюнкция и конъюнкция меняются местами и ${\displaystyle E'(q_{0},a,c)}$ имитирует бег из каждого места ${\displaystyle L_{0}}$ одновременно.

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

Сложность

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

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

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

1. Ласота, Славомир; Валукевич, Игорь (2008). «Чередующиеся временные автоматы». Транзакции ACM по вычислительной логике. 9 (2): 1–26. arXiv:1208.5909. Дои:10.1145/1342991.1342994.