Автомат с переменным таймером

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

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

Определение

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

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

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

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

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

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

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

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

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

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

Бегать

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

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

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

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

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

Беги как игра

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

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

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

Набор последовательных состояний, начинающихся в состоянии вида $(\ell ,\nu ,i)$ и заканчивающийся перед следующим таким состоянием, называется фазой .

Определение приемочного прогона такое же, как и для автоматов с таймером .

Подкласс АТА

Автомат с переменным таймером и одним тактом

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

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

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

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

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

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

Закрытие

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

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

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

Сложность

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

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

Ссылки

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

[Alternating_timed_automata-1] Ласота, Савомир; Валукевич, Игорь (2008). «Попеременные временные автоматы». Транзакции ACM в вычислительной логике . 9 (2): 1–26. arXiv : 1208.5909 . дои : 10.1145/1342991.1342994 . S2CID 12319 .

[1]