Alternating timed automaton

In automata theory, an alternating timed automaton (ATA) is a mix of both timed automaton and alternating finite automaton. That is, it is a sort of automata which can measure time and in which there exists universal and existential transition.

ATAs are more expressive than timed automaton. one clock alternating timed automaton (OCATA) is the restriction of ATA allowing the use of a single clock. OCATAs allow to express timed languages which can not be expressed using timed-automaton. ^[1]

Definition

An alternating timed automaton is defined as a timed automaton, where the transitions are more complex.

Difference from a timed-automaton

Given a set ${\displaystyle X}$, let ${\displaystyle {\mathcal {B}}^{+}(X)}$ the set of positive Boolean combination of elements of ${\displaystyle X}$. I.e. the set containing the elements of ${\displaystyle X}$, and containing ${\displaystyle \phi \land \psi }$ and ${\displaystyle \phi \lor \psi }$, for ${\displaystyle \phi ,\psi \in {\mathcal {B}}^{+}(X)}$.

For each letter ${\displaystyle a}$ and location ${\displaystyle \ell }$, let ${\displaystyle {\mathcal {B}}_{a,\ell }}$ be a set of clock constraints such that their zones partition ${\displaystyle \mathbb {R} _{\geq 0}^{|X|}}$, with ${\displaystyle |X|}$ the number of clocks. Given a clock valuation ${\displaystyle \nu }$, let ${\displaystyle c(a,\ell ,\nu )}$ be the only clock constraint of ${\displaystyle {\mathcal {B}}_{a,\ell }}$ which is satisfied by ${\displaystyle \nu }$.

An alternating timed-automaton contains a transition function, which associates to a 3-tuple ${\displaystyle (\ell ,a,c)}$, with ${\displaystyle c\in {\mathcal {B}}_{a,\ell }}$, to an element of ${\displaystyle {\mathcal {B}}^{+}(L\times {\mathcal {P}}(C))}$.

For example, ${\displaystyle (\ell _{1},\emptyset )\lor ((\ell _{2},\{x\})\land (\ell _{2},\{y\}))}$ is an element of ${\displaystyle {\mathcal {B}}^{+}(L\times {\mathcal {P}}(C))}$. Intuitively, it means that the run may either continue by moving to location ${\displaystyle \ell _{1}}$, and resetting no clock. Or by moving to location ${\displaystyle \ell _{2}}$ and should be successful when either ${\displaystyle x}$ or ${\displaystyle y}$ is reset.

Formal definition

Formally, an alternating timed automaton is a tuple ${\displaystyle {\mathcal {A}}=\langle \Sigma ,L,L_{0},C,F,E\rangle }$ that consists of the following components:

• Σ is a finite set called the alphabet or actions of ${\displaystyle {\mathcal {A}}}$.
• ${\displaystyle L}$ is a finite set. The elements of ${\displaystyle L}$ are called the locations or states of ${\displaystyle {\mathcal {A}}}$.
• ${\displaystyle C}$ is a finite set called the clocks of ${\displaystyle {\mathcal {A}}}$.
• ${\displaystyle L_{0}\subseteq L}$ is the set of start locations.
• ${\displaystyle F\subseteq L}$ is the set of accepting locations.
• ${\displaystyle E\subseteq L\times \Sigma \times {\mathcal {B}}(C)\to {\mathcal {B}}^{+}(L\times {\mathcal {P}}(C))}$ is the transitions function of ${\displaystyle {\mathcal {A}}}$. It is a partial function, defined as explained in the previous section.

Any Boolean expression can be rewritten into an equivalent expression in disjunctive normal form. In the representation of a ATA, each disjunction is represented by a different arrow. Each conjunct of a disjunction is represented by a set of arrows with the same tail and multiple heads. The tail is labelled by the letter and each head is labelled by the set of clocks it resets.

Run

We now define a run of an alternating timed automaton over a timed word ${\displaystyle w=(\sigma _{1},t_{1}),(\sigma _{2},t_{2}),\dots ,}$. There are two equivalent way to define a run, either as a tree or as a game.

Run as a tree

In this definition of a run, a run is not anymore a list of pairs, but a rooted tree. The node of the trooted^{[ spelling? ]} tree are labelled by pairs with a location and a clock valuation. The tree is defined as follows:

• the root of the tree is of the form ${\displaystyle (\ell _{0},\nu _{0})}$ with ${\displaystyle \ell _{0}\in L_{0}}$,
• Consider a node ${\displaystyle n}$ of the tree at depth ${\displaystyle i}$, with label ${\displaystyle (\ell ,\nu )}$. Without loss of generality, let us assume that ${\displaystyle E(a_{i+1},\ell ,c(a,\ell ,\nu ))}$ is in disjunctive normal form, i.e. it is of the form ${\displaystyle \bigvee _{i=1}^{n}\bigwedge _{j=1}^{m_{i}}(\ell _{i,j},r_{i,j})}$. Then the node ${\displaystyle n}$ has ${\displaystyle m_{i}}$ children, for some ${\displaystyle 1\leq i\leq n}$. The ${\displaystyle j}$-th child is labelled by ${\displaystyle (\ell _{i,j},(\nu +t_{i+1}-t_{i})[r_{i,j}\to 0]}$.

The definition of an accepting runs differs depending on whether the timed word is finite or infinite. If the timed word is finite, then the run is accepting if the label of each leaf contains an accepting location. If the timed word is infinite, then a run is accepting if each branch contains an infinite number of accepting location.

Run as a game

A run can also be defined as a two player game ${\displaystyle G_{A,w}}$. Let us call the two players "player" and "opponent". The goal of the player is to create an accepting run and the goal of the opponent is to create a rejecting (non-accepting) run.

Each state of the game is a tuple composed of a location, a clock valuation, a position in the word, and potentially an element of ${\displaystyle {\mathcal {B}}^{+}(L\times {\mathcal {P}}(C))}$. Intuitively, a tuple ${\displaystyle (\ell ,\nu ,i,b)}$ means that the run has read ${\displaystyle i}$ letters, is in location ${\displaystyle \ell }$, with clock value ${\displaystyle \nu }$, and that the transition will be as described by ${\displaystyle b}$. The run is defined as follow:

• The initial state is of the form ${\displaystyle (\ell _{0},\nu _{0},0)}$, for some ${\displaystyle \ell _{0}\in L_{0}}$.
• given a state ${\displaystyle (\ell ,\nu ,i)}$, if the length of the word is ${\displaystyle i}$, the run ends. Otherwise, its successor state is ${\displaystyle (\ell ,\nu ,i,c(a_{i+1},\ell ,\nu ))}$.
• The successor of a state ${\displaystyle (\ell ,\nu ,i,(\ell ',r))}$ is the state ${\displaystyle (\ell ',\nu +t_{i}-t_{i-1}[r\to 0],i+1)}$,
• The successor of a state ${\displaystyle (\ell ,\nu ,i,\phi \lor \psi )}$ is chosen by the player, it is either ${\displaystyle (\ell ,\nu ,i,\phi )}$ or ${\displaystyle (\ell ,\nu ,i,\psi )}$,
• The successor of a state ${\displaystyle (\ell ,\nu ,i,\phi \land \psi )}$ is chosen by the opponent, it is either ${\displaystyle (\ell ,\nu ,i,\phi )}$ or ${\displaystyle (\ell ,\nu ,i,\psi )}$.

The set of successive states starting in a state of the form ${\displaystyle (\ell ,\nu ,i)}$ and ending in before the next such state is called a phase.

The definition of an accepting run is the same than for timed automata.

Subclass of ATA

One clock alternating timed automaton

A one clock alternating timed automaton (OCATA) is an alternating timed automaton using a single clock.

The expressivity of OCATAs and of timed-automaton are incomparable.

For example, the language over the alphabet ${\displaystyle \{a\}}$ such that there is never exactly one time unit between two letters can not be recognized by a timed-automaton. However, the OCATA pictured nearby accepts it. In this alternating timed automaton, two branches are started. A branch restarts the clock ${\displaystyle x}$, and ensures that each time in the future when a letter is emitted, the clock ${\displaystyle x}$ is distinct from 1. This ensure that between this letter and the next ones, the time elapsed is not one. The second branch only waits for other letters to be emitted and do the same checking.

OCATA accepting the language in which no two letters occurs at 1 time unit of interval

Purely-Universal and Purely-Existential ATA

An ATA is said to be purely-universal (respectively, purely-exisential) if its transition function does not use disjunction (respectively, conjunction).

Purely-existential ATAs are as expressive as non-deterministic timed-automaton.

Closure

The class of language accepted by ATAs and by OCATAs is closed under complement. The construction is explained for the case where there is a single initial location.

Given an ATA ${\displaystyle {\mathcal {A}}=\langle \Sigma ,L,\{q_{0}\},C,F,E\rangle }$ accepting a timed language ${\displaystyle L}$, its complement language ${\displaystyle L^{c}}$ is accepted by an automaton ${\displaystyle A^{c}}$ which is essentially ${\displaystyle \langle \Sigma ,L,\{q_{0}\},C,L\setminus F,E'\rangle }$, where ${\displaystyle E'(\ell ,a,c)}$ is defined as ${\displaystyle E(\ell ,a,c))}$ where disjunction and conjunctions are reversed and ${\displaystyle E'(q_{0},a,c)}$ simulates the run from each of the locations of ${\displaystyle L_{0}}$ simultaneously.

It follows that the class of language accepted by ATAs and by OCATAs are accepted by unions and intersection. The union of two languages is constructed by taking disjoint copies of the automata accepting both language. The intersection can be constructed from union and concatenation.

Complexity

The emptiness problem, the universality problem and the containability problem for OCATA is decidable but is a nonelementary problem.

Those three problems are undecidable over ATAs.

References

1. Lasota, SƗawomir; Walukiewicz, Igor (2008). "Alternating Timed Automata". ACM Transactions on Computational Logic. 9 (2): 1–26. arXiv: 1208.5909 . doi:10.1145/1342991.1342994. S2CID   12319.