





\section{Conclusion}\label{sec-conc}
In this paper, we have described an algorithm, which given a timed automaton $A$, produces another timed automaton $A_4$ with the smallest number of clocks that is timed bisimilar to $A$.
Since $A_4$ is timed bisimilar to $A$, it also accepts the same timed language as $A$.
The problem appears in a different form
in \cite{LLW1} where it was left open.
In \cite{LLW1}, this problem has been described as 
given a timed automaton $A$ and a set $C$ of clocks,
whether there exists a timed automaton that is
timed bisimilar to the original automaton $A$ and has $|C|$ clocks.
It is easy to see that a solution to our problem solves
the problem in \cite{LLW1} and vice versa.

For reducing the number of clocks of the timed automaton, we rely on a semantic representation of the timed automaton rather than its syntactic form as in \cite{DY1}. This helps us to reason about the behaviour of the timed automaton more effectively.
We could just as well have used a region graph construction,
the asymptotic complexity would remain the same.
However, the zone graph we use in our approach is usually much smaller in size than the region graph.
Besides, the size of the zone graph is independent of the constants used in the timed automaton.
There is an exponential increase in the number of locations while producing the TA with the minimal number of clocks.
However, there is no addition of new valuations to the underlying state space of the timed automaton in stage 2,
since the splitting of a location $l$,
described in stage 2, involves distributing the zones of $l$ across the locations $l$ is split into.

We note that pre-stability of the zones with respect to transitions is essential for the operations in stage 2.
Notice that regions are inherently pre-stable \cite{Sri1} and therefore the region graph construction would work here as well
though the number of locations obtained through splitting would be larger than in the case of zone graphs.

Our algorithm has a 2-EXPTIME upper bound,
however, it needs to be used only once to reduce the number of clocks.
Reachability analysis and often model checking
for timed automata like TCTL model checking are PSPACE-complete \cite{AD1,AL1,ACD1}.
Since reachability analysis and model checking the timed automata
are usually performed several times to verify different properties,
we may consider first reducing the number of clocks before doing the model checking.
With fewer clocks, the DBM representation of a zone will also be smaller in size
which may as well contribute towards reducing the computation time for model checking.
\chapter{Clock Reduction while Preserving Timed Bisimulation} \label{chap-clockred}

\section{Introducton} \label{sec-clockredIntro}
Timed automata \cite{AD1} is a formalism for modelling and analyzing real time systems. The complexity of model checking is dependent on the number of clocks of the timed automaton (TA) \cite{AD1,ACD1}. 
Model checkers use the region graph or a zone graph construction
for analysing reachability and other properties in timed automata.
These graphs have sizes exponential in the number of clocks of the timed automaton.
The algorithms for model checking in turn depend on the sizes of these graphs.
Hence it is desirable to construct a timed automaton with the minimum number of clocks that preserves some property of interest
(such as timed language equivalence or timed bisimilarity).
Here we show that checking the existence of a timed automaton with fewer clocks
that is timed bisimilar to the original timed automaton is decidable.
Our method is constructive and we provide a 2-EXPTIME algorithm to construct the timed bisimilar automaton with the least possible number of clocks. 
We also note that if the constructed TA has a smaller number of clocks,
then it implies that there exists an automaton with a smaller number of clocks accepting the same timed language.

\textbf{Related work:} 
In \cite{DY1}, an algorithm has been provided to reduce the number of clocks of a given timed automaton.
It produces a new timed automaton that is timed bisimilar to the original one. The algorithm detects a set of \emph{active clocks} at every location and partitions these active clocks into classes such that all the clocks belonging to a class in the partition always have the same value.
However, this may not result in the minimum possible number of clocks.
The algorithm described in the paper \cite{DY1} works on the timed automaton directly rather than on its semantics.
For instance, if a constraint associated with clock $x$ implies a constraint
associated with clock $y$, and the conjunction of the two constraints appears on an edge,
then the constraint associated with clock $y$
may be eliminated.
However, the algorithm of \cite{DY1} does not capture such implication.
Also by considering 
constraints on more than one outgoing edge from a location,
e.g.  $l_0 \to{a, x \le 3, \emptyset} l_1$ and $l_0 \to{a, x > 3, \emptyset} l_2$
collectively, we may sometimes eliminate the constraints
that may remove some clock. This too has not been accounted for by the algorithm of \cite{DY1}.

In a related line of work
\cite{Trip1}, it has been shown that no algorithm can decide the
following two things together.
\begin{enumerate}[(i)]
\item minimality of the number of clocks while preserving the timed language and 
\item for the non-minimal case finding a timed language equivalent automaton with fewer clocks.
\end{enumerate}
Also as mentioned earlier, for a given timed automaton,
the problem of determining whether there exists another TA with fewer clocks accepting the same timed language is undecidable\index{clock reduction!preserving timed language} \cite{Fin1}.

Another result appearing in \cite{LLW1} which uses the region-graph construction is the following.
A $(C, M)$-automaton\index{(C, M)-automaton} is one with $\lvert C \lvert$ clocks and $M$ is the largest integer appearing in the timed automaton.
Given a timed automaton $A$, a set of clocks $C$ and an integer $M$, checking the existence of a ($C, M$)-automaton that is timed bisimilar to $A$ is shown to be decidable.
The method described there constructs a logical formula called the \emph{characteristic formula} and checks whether there exists a $(C,M)$-automaton that satisfies it.
Further, it is shown that a pair of automata satisfying the same characteristic formula are timed bisimilar.
The paper also considers the following problem $P$ and leaves it open.
\begin{quote}
Does there exist a timed automaton with $|C|$ clocks
that is timed bisimilar to $A$?
\end{quote}
We solve the following problem $Q$.
\begin{quote}
Given a timed automaton $A$, construct a timed bisimilar automaton $B$
with the least number of clocks.
\end{quote}
Solving the problem $Q$ also solves the problem $P$ and vice versa.
If $B$ has say $|C'|$ clocks and $|C| \ge |C'|$,
then the answer to the problem $P$ is in the affirmative.
For the problem $P$, if the answer is `yes' for $|C|$ clocks
but the answer is `no' for $|C|-1$ clocks,
then it is clear that the timed automaton
with the minimum possible number of clocks that is timed bisimilar to $A$
can have no less than $\lvert C \lvert$ clocks.

The rest of the paper is organized as follows: in Section \ref{sec-ta}, we describe timed automata and introduce several concepts that will be used in the paper. We also describe the construction of the zone graph
in Section \ref{sec-zoneGraph} used in reducing the number of clocks.
This construction of the zone graph has also been used in \cite{GKNA1}
for deciding several timed and time abstracted relations.
In Section \ref{sec-method}, we discuss our approach in detail along with a few examples. Section \ref{sec-conc} is the conclusion.

\section{Clock Reduction} \label{sec-method}\index{clock reduction}
Unlike the method described in \cite{DY1}, which works on the syntactic structure of the timed automaton, we use a semantic representation as given by the zone graph described in Section \ref{sec-ta} to capture the behaviour of the timed automaton. This helps us to reduce the number of clocks in a more effective way. For a given TA $A$, we first describe a sequence of stages
to construct a TA $A_4$ that is timed bisimilar to $A$.
Later we prove the minimality in terms of the number of clocks for the TA $A_4$.
The operations involved in our procedure use a \emph{difference bound matrix} \index{difference bound matrix (DBM)} representation of the zones.
The following  are important considerations in reducing the number of clocks.
\begin{itemize}
\item There may be some clock constraints on an edge of the TA that are never enabled.
Such edges and constraints may be removed. (Stage 1)
\item Splitting some locations may lead to a reduction in the number of the clocks. (Stage 2)
\item At some location, some clocks whose values may be expressed in terms of other clock values, may be removed. (Stage 2) 
\item Two or more constraints on edges outgoing from a location
when considered collectively may lead to the removal of some constraints. (Stage 3)
\item An efficient way of renaming the clocks across all locations can reduce the total number of clocks further. (Stage 4)
\end{itemize}
Given a TA $A$, we apply the above operations in sequence to obtain the TA $A_4$. These operations are detailed below.

\input{stage1}
\input{stage2_new}
\input{stage3_new}
\input{stage4}
In the presence of an invariant condition, considering an edge $l \to{g, a, R} l'$, a zone $Z'$ of $l'$ is initially created 
from zone $Z$ of $l$ such that $Z'=(Z \cap g)_{[R \leftarrow \overline{0}]}\!\!\uparrow \cap I(l')$, if $(Z \cap g)_{[R \leftarrow \overline{0}]}\!\!\uparrow \cap I(l') \neq \emptyset$, where $I(l')$ is the invariant on location $l'$.
The edge can be removed from the timed automaton if for all zones $Z$ of $l$, $(Z \cap g)_{[R \leftarrow \overline{0}]}\uparrow \cap I(l') = \emptyset$. 
The invariant condition on location $l'$ can be entirely removed if for every incoming edge $l \to{g, a, R} l'$ and for each zone $Z$ of $l$, $(Z \cap g)_{[R \leftarrow \overline{0}]}\uparrow \cap I(l') = (Z \cap g)_{[R \leftarrow \overline{0}]}\uparrow$ holds.
Considering the clock relations in the zones of a location, an elementary constraint in the invariant too is removed if it is implied by the rest of the elementary constraints in the invariant.
In stage 4, for computing the set of active clocks $act(l)$ in location $l$, $clk(l)$ is defined as the 
union of the set of clocks appearing in the constraints on the outgoing edges from $l$ and the set of clocks appearing in $I(l)$.

\input{proof3}









\section{Timed Automata}\label{sec-ta}
Formally, a \emph{timed automaton} (TA) \cite{AD1} is defined as a tuple $A=(L, Act, l_0, C, E)$ where
$L$ is a finite set of locations, $Act$ is a finite set 
of visible actions, $l_0 \in L$ is the initial location,
$C$ is a finite set of clocks and $E \subseteq L \:\times\: \mathcal{B}(C) \:\times\: Act \:\times\: 2^C \:\times\: L$
is a finite set of \emph{edges}. The set of constraints or guards on the edges, denoted $\mathcal{B}(C)$, is 
given by the grammar $g ::= \; x \bowtie k \:|\: g \wedge g$,
where $k \in \mathbb{N}$ and $x \in C$ and $\bowtie \: \in \: \{\le, <, =, >, \ge\}$.
Given two locations $l, l'$, a transition from $l$ to $l'$ is of the form 
$(l, g, a, R, l')$ i.e. a transition from $l$ to $l'$  on action $a$ is possible if the constraints 
specified by $g$ are satisfied; $R \subseteq C$ is a set of clocks which are reset to zero during  
the transition.

The semantics of a timed automaton(TA) is described by a \emph{timed labelled
transition system} (TLTS) \cite{LAKJ1}. The timed labelled transition system $T(A)$ generated by $A$ is defined as 
$T(A) = (Q, Lab, Q_0, \{\stackrel{\alpha}{\longrightarrow} | \alpha \in Lab\})$, where 
$Q \: = \: \{(l,v)\:|\: l \in L, v \in {\mathbb{R}_{\ge 0}}^{|C|}\}$ is the set of  \emph{states}, each of which is of the form $(l,v)$, where $l$ is a location of the timed automaton 
and $v$ is a valuation in $|C|$ dimensional real space
where each clock is mapped to a unique dimension in this space;
$Lab = Act \cup \mathbb{R}_{\ge 0}$ is the set of labels. 
Let $v_0$ denote the valuation such that $v_0(x)=0$ for all 
$x \in C$. $Q_0=(l_0, v_0)$ is the initial state of $T(A)$.
A transition may occur in one of the following ways:\\ 
(i) \emph{Delay transitions} : $(l,v)\stackrel{d}{\longrightarrow}(l, v+d)$. Here, $d \in \mathbb{R}_{\ge 0}$ and $v + d$ is the valuation
in which the value of every clock is incremented by $d$. \\
(ii) \emph{Discrete transitions} : $(l,v) \stackrel{a}{\longrightarrow} (l', v')$ if for an edge 
$e=(l,g,a,R,l') \in \: E$,
$v$ satisfies the constraint $g$, (denoted $v \models g$),
$v' = v_{[R \leftarrow \overline{0}]}$,
where $v_{[R \leftarrow \overline{0}]}$ denotes that every clock in $R$ has been reset to 0, while the remaining clocks are unchanged.
From a state $(l,v)$, if $v \models g$, then there exists an $a$-transition to a state $(l', v')$; 
after this,  the clocks in $R$ are reset while those in $C\backslash R$ remain unchanged. 

For simplicity, we do not consider annotating 
locations with clock constraints (known as \emph{invariant conditions} \cite{HNSY1}). Our results extend in a
straightforward manner to timed automata with invariant conditions.
In Section \ref{sec-method}, we provide the modifications to our method for dealing with location invariants.
We now define various concepts that will be used in the rest of the paper.
\begin{definition} 
Let $A=(L, Act, l_0, E, C)$ be a timed automaton, and $T(A)$ be the TLTS corresponding to $A$. 
\begin{enumerate}
\item \textbf{Timed trace}: A sequence of delays and visible actions $d_1 a_1 d_2 a_2 \dots d_n a_n$
is called a timed trace of the timed automaton $A$ iff there is a sequence of transitions 
$p_0 \to{d_1} p_1 \to{a_1} p_1'\to{d_2}p_2\to{a_2}p_2'\cdots \to{d_n}p_n\to{a_n}p_n'$ in $T(A)$, 
where each $p_i$ and $p_i'$, $0 \le i \le n$
are timed automata states and are of the form $(l, v)$.
$p_0$ is the initial state of the timed automaton.
Given a timed trace $tr = d_1 a_1 d_2 a_2 \dots d_n a_n$,
$untime(tr)$ denotes its projection on $Act$, i.e.
$untime(tr) = a_1 a_2 \dots a_n$.
\item \textbf{Zone and difference bound matrix (DBM)}: A zone $Z$ is a set of valuations $\{v \in \mathbb{R}_{\ge 0}^{|C|} \mid v \models \beta\}$, where 
$\beta$ is of the form $\beta ::= \; x \bowtie k \:|\: x-y \bowtie k \:|\: \beta \wedge \beta$,
$k$ is an integer, $x,y \in C$ and $\bowtie \: \in \: \{\le, <, =, >, \ge\}$.
$Z \!\!\uparrow$ denotes the future of the zone $Z$.
$Z\!\!\uparrow=\{v+d \mid v \in Z, d \geq 0\}$ is the set of all valuations 
reachable from $Z$ by delay transitions.
A zone is a convex set of clock valuations.
A difference bound matrix is a data structure used to
represent zones.
A DBM  \cite{BM1,Dill1} for a set $C = \{x_1, x_2, \dots, x_n\}$ of $n$ clocks is an $(n+1)$ square matrix $\Xi$
where an extra variable $x_0$ is introduced such that the value of $x_0$ is always $0$.
An element $\Xi_{ij}$ is of the form $(m_{ij}, \prec)$ where $\prec \in \{<, \le\}$ 
such that $x_i - x_j \prec m_{ij}$.
Thus an entry $m_{i0}$ denotes the constraint $x_i - x_0 \prec m_{i0}$ which is equivalent to $x_i \prec m_{i0}$.
\item \textbf{Canonical decomposition}: Let $\displaystyle{g =\bigwedge_{i=1}^n \gamma_i \in \mathcal{B}(C)}$, where 
each $\gamma_i$ is an \emph{elementary constraint} of the form $x_i \bowtie k_i$,
such that $x_i \in C$ and $k_i$ is a non-negative integer.
A canonical decomposition of a zone $Z$ with respect to  $g$ 
is obtained by splitting $Z$ into a set of zones $Z_1, \dots, Z_m$ such that 
for each $1 \leq j \leq m$, and $1 \leq i \leq n$, either $\forall v \in Z_j, v \models \gamma_i$ or $\forall v \in Z_j$, $v \not \models \gamma_i$.
For example, consider the zone $Z=x \geq 0 \wedge y \geq 0$ and the guard  $x \le 2 \wedge y > 1$. 
$Z$ is split with respect to $ x \le 2$, and then with respect to $y > 1$, hence 
into four zones : 
$x \le 2 \wedge y \le 1$, $x > 2 \wedge y \le 1$, $x \le 2 \wedge y > 1$ and $x > 2 \wedge y > 1$.
An elementary constraint $x_i \bowtie k_i$ induces the hyperplane $x_i = k_i$ in a zone graph of the timed automaton.
\item \textbf{Zone graph}:
Given a timed automaton $A= (L, Act, l_0, C, E)$, a \emph{zone graph} $\mathcal{G}_A$ of $A$
is a transition system $(S, s_0, Lep, \rightarrow)$, 
that is a finite representation of $T(A)$.
Here $Lep = Act \cup \{\varepsilon\}$.
$S \subseteq L \times \mathcal{Z}$ is the set of nodes of $\mathcal{G}_A$, $\mathcal{Z}$ being the set of zones.
The node $s_0 = (l_0, Z_0)$ is the initial node such that $v_0 \in Z_0$.
$(l_i, Z) \to{a} (l_j, Z')$ iff $l_i \to{g, a, R} l_j$ in $A$ and $Z' \subseteq ([Z \cap g]_{R \leftarrow \overline{0}})\!\!\uparrow$ obtained after canonical decomposition of $([Z \cap g]_{R \leftarrow \overline{0}})$.
For any $Z$ and $Z'$, $(l_i, Z) \to{\varepsilon}(l_i, Z')$ iff there exists a delay $d$ and a valuation $v$ such that $v\in Z$, $v+d \in Z'$ and $(l_i,v)\stackrel{d}{\longrightarrow}(l_i, v+d)$ is in $T(A)$. Here the zone $Z'$ is called a \emph{delay successor} of zone $Z$, while $Z$ is called the \emph{delay predecessor} of $Z'$.
Every node has an $\varepsilon$ transition to itself and the $\varepsilon$ transitions are also transitive.
The relation $\to{\varepsilon}$ is reflexive and transitive and so is the \emph{delay successor} relation.
We denote the set of delay successor zones of $Z$ by $ds(Z)$.
A zone $Z' \neq Z$  is called the \emph{immediate delay successor} of a zone $Z$ iff $Z' \in ds(Z)$ and
$\forall Z'' \in ds(Z): Z'' \neq Z$ and $Z'' \neq Z'$, $Z'' \in ds(Z')$.
We call a zone $Z$ corresponding to a location to be a \emph{base zone} if $Z$ does not have a delay predecessor
other than itself.
For both $a$ and $\varepsilon$ transitions, if $Z$ is a zone then $Z'$ is also a zone, i.e. $Z'$ is a convex set.
\item A hyperplane $x = k$ is said to \emph{bound} a zone $Z$ from above if 
$\exists v \in Z \:[\:\forall d \in \mathbb{R}_{\ge 0} \:[\: (v+d)(x) \succ k \iff (v+d)(x) \notin Z \:]\:]$, where $\succ \in \{>, \ge \}$.
A zone, in general, can be bounded above by several hyperplanes.
A hyperplane $x = k$ is said to \emph{bound} a zone $Z$ fully from above if 
$\forall v \in Z \:[\:\forall d \in \mathbb{R}_{\ge 0} \:[\: (v+d)(x) \succ k \iff (v+d)(x) \notin Z \:]\:]$.
Analogously, we can also say that a hyperplane $x = k$ bounds a zone from below if
$\exists v \in Z \:[\:\forall d \in \mathbb{R}_{\ge 0} \:[\: (v-d)(x) \prec k \iff (v-d)(x) \notin Z \:]\:]$, where $\prec \in \{<, \le \}$.
We can also define a hyperplane bounding a zone fully from below in a similar manner.

When not specified otherwise, in this paper, a hyperplane bounding a zone implies
that it bounds the zone from above.
A zone $Z$ is bounded above if it has an immediate delay successor zone.
\item \textbf{Pre-stability}: A zone $Z_1$ of location $l_1$ is pre-stable with respect to a transition $\eta \in Lep$
leading to a zone $Z_2$ of location $l_2$ if\\
i) for $\eta = a \in Act \: :$ $\forall v_1 \in Z_1, \exists v_2 \in Z_2$ such that $(l_1, v_1) \to{a} (l_2, v_2)$ or
$\forall v_1 \in Z_1, \not\!\exists v_2 \in Z_2$ such that $(l_1, v_1) \to{a} (l_2, v_2)$. \\
ii) for $\eta = \varepsilon \: :$ $\forall v_1 \in Z_1, \exists v_2 \in Z_2, \exists d \in \mathbb{R}_{\ge 0}$ such that $(l_1, v_1) \to{d} (l_2, v_2)$ or
$\forall v_1 \in Z_1$, $\not\!\exists v_2 \in Z_2$ such that $(l_1, v_1) \to{d} (l_2, v_2)$, for any $d \in \mathbb{R}_{\ge 0}$. \\
A zone graph is said to be pre-stable if the zones corresponding to each of the nodes
of the zone graph are pre-stable with respect to their outgoing transitions.
For example zone $Z_1$ in Figure \ref{fig-delayZone} is pre-stable with respect to zone $Z_4$,
however, $Z_1 \cup Z_2 \cup Z_3$ is not pre-stable with respect to zone $Z_4$
since $\exists v \in Z_3$ and hence $v \in Z_1 \cup Z_2 \cup Z_3$ such that for all $d \in \mathbb{R}_{\ge 0}$, $v + d \notin Z_4$.
\item \textbf{corner point and corner point traces}: A corner point\index{corner point} of a zone in the zone graph is a state
where corresponding to each clock $x$, a hyperplane of the form $x = c$ bounding a zone intersects
another hyperplane defining the zone.
Considering $M$ to be the largest constant appearing in the constraints or the location invariants of the timed automaton,
each coordinate of a corner point is of the form $n, n + \delta$ or $n - \delta$ where 
$n \in \{0, 1, \dots, M\}$ and $\delta$ is a symbolic value for an infinitesimally small quantity.
In a zone $Z$, there can be two kinds of corner points, an \emph{entry}\index{corner point!entry} corner point and an \emph{exit}\index{corner point!exit} corner point. For an entry corner point, there is a unique exit corner point, that can be reached from the entry corner point by performing a delay $d$ such that any delay more than $d$ will lead to a state that is in a delay successor zone of $Z$. 

For a zone, it is possible to have a pair of such entry and exit corner points that are not distinct, for example, in Figure \ref{fig-delayZone}, in zone $Z_4$, the corner point ($x = 5 + \delta, y = 7$) is both an entry as well as an exit corner point, while the corner point ($x = 5 + \delta, y = 5+\delta$) is another entry corner point for the same zone $Z_4$ and the corresponding exit corner point is $(x = 7, y = 7)$.
If the entry and the exit corner points are distinct,
then a non-infinitesimally small delay can be performed from the entry corner point
to reach the corresponding exit corner point whereas an infinitesimally small delay from the exit corner point causes it to evolve into an entry corner point of the immediate delay successor zone.
A zone that is not bounded above does not have any exit corner point.

For an entry corner point, the corresponding exit corner point is the \emph{next delay corner point} whereas for an exit corner point, the entry corner point in the immediate delay successor zone is the \emph{next delay corner point}.

Let $c_1$ and $c_2$ be constraints of the form $x \succ k_1$ and $y \prec k_2$ respectively,
where $k_1, k_2 \in \{0,1, \dots, M\}$
and $\succ \:\in \: \{>, \ge \}$ and $\prec \: \in \: \{<, \le \}$.

We consider delays of the form $d_{c_1, c_2}$ and $d_{c_2, c_1}$.
$d_{c_1, c_2}$ is the delay made from an entry corner point to reach an exit corner point
while $d_{c_2, c_1}$ is the delay
made from the exit corner point to reach an entry corner point of a delay successor zone.
For example, the delay $d_{x \ge 5, y < 7}$ denotes a delay
made from a state $p'$ with $p'(x) = 5$ and after making this delay
it evolves to state $p''$ such that $p''(y) = 7 - \delta$.
Delays of the form mentioned above are called \emph{corner point delays}\index{corner point delay} or \emph{cp-delays}.

A corner point trace\index{corner point trace} (cp-trace) is a timed trace ending at a corner point through delays and visible actions such that each delay takes the trace from one corner point to the next delay corner point.
All the delay actions present in a corner point trace are cp-delays.
\end{enumerate}
\end{definition}
We create a zone graph such that for any location $l$, the zones $Z$ and $Z'$ of
any two nodes $(l, Z)$ and $(l, Z')$ in the zone graph are disjoint and all zones of the zone graph are pre-stable.
This zone graph is constructed in two phases in time exponential in the number of the clocks.
The first phase performs a forward analysis of the timed automaton while the second phase
ensures pre-stability in the zone graph.
The forward analysis may cause a zone graph to become infinite \cite{BBFL1}. Several kinds of abstractions
have been proposed in the literature \cite{DT1,BBFL1,BBLP1} to make the zone graph finite.
We use \emph{location dependent maximal constants}
abstraction \cite{BBFL1} in our construction.
In phase 2 of the zone graph creation, the zones are further split to ensure that the resultant zone graph is pre-stable.

Some approaches for preserving convexity and implementing pre-stability have been discussed in \cite{TY1}. 
As an example, consider the timed automaton in Figure \ref{fig-delayZone}. The pre-stable zones of location $l_1$ are shown in the right side of the figure.
In this paper, from now on, unless stated otherwise, \emph{zone graph} will refer to this form of the pre-stable zone graph that is described above.
An algorithmic procedure for the construction of the zone graph is given in \cite{GKNA1}.

A relation $\mathcal{R} \subseteq Q \times Q$ is a \emph{timed simulation} relation if the following conditions hold
for any two timed states $(p, q) \in \mathcal{R}$. \\
$\forall$ $a \in Act$, $p \to{a}p' \implies \exists q'$ : $q \to{a}q'$ and $(p', q') \in \mathcal{R}$ and \\
$\forall d \in \mathbb{R}_{\ge 0}$, $p \to{d}p' \implies \exists q'$ : $q \to{d}q'$ and $(p', q') \in \mathcal{R}$.\\
A \emph{timed bisimulation} relation is a symmetric timed simulation. Two timed automata are timed bisimilar if and only if their initial states are timed bisimilar. Using a product construction on region graphs,
timed bisimilarity for timed automata was shown to be decidable in EXPTIME \cite{Cer1}.
In \cite{WL1}, a product construction on zone graph was used
for deciding timed bisimulation relation for timed automata.
 \begin{figure}[t]
 \centering
 \begin{minipage}[b]{0.46\linewidth}
 \includegraphics[width=0.9\textwidth]{delayZone.pdf}
 \caption{\label{fig-delayZone} a timed automaton and the zones for location $l_1$}
 \end{minipage}
 \begin{minipage}[b]{0.49\linewidth}
 \includegraphics[width=0.95\textwidth]{zg.pdf}
 \caption{\label{fig-zoneGraph} zone graph for the TA in Figure \ref{fig-delayZone}}
 \end{minipage}
 \end{figure}

\section{Zone Graph}\label{sec-zoneGraph}\index{zone graph}
\begin{algorithm}
\caption{Construction of Zone Graph\newline 
\emph{Input: Timed automaton $A$ \newline
Output: Zone  graph corresponding to $A$}
}\label{algo-zonegraph}
\begin{algorithmic}[1]
{\small
\State Calculate $max_x^l$ for each location $l \in L$ and each clock $x \in C$. \Comment{\textsf{\tiny This is required 
for abstraction to ensure finite number of zones in the zone graph.}}
\State Initialize $Q$ to an empty queue.
\State $Enqueue(Q, \langle l_0, \emptyset \rangle)$. \Comment{\textsf{\tiny Every element is a pair consisting of a location and its parent}}
\State $successors\_added = false$. \Comment{\textsf{\tiny flag set to true whenever  successors of a location are added to $Q$}}
\While {Q not empty}
\State $\langle l, l_p \rangle = dequeue(Q)$
\If {$l_p\neq \emptyset$}, 
\State For the edge $l_p \to{g, a, R'} l$ in $A$, for each existing zone $Z_{l_p}$ of $l_p$, create
the zone $Z = (Z_{l_p} \uparrow \cap \:g_{[R' \leftarrow \overline{0}]})$ of $l$, when $Z \neq \emptyset$.
\State Abstract each of the newly created zones if necessary and for any newly created zone $Z$, for location $l$,
if $\exists Z_1$ of same location such that $Z \cap Z_1 \neq \emptyset$, then merge $Z$ and $Z_1$.
\State Update edges from zones of $l_p$ to zones of $l$ appropriately.
\State If {a new zone of $l$ is added or an existing zone of $l$ is modified} for all successors $l_j$ of $l$,
enqueue $\langle l_j, l \rangle$ to Q.
\State $successors\_added := true$.
\EndIf
\State $new\_zone\_l := true$. \Comment{\textsf{\tiny flag set to false when the canonical decomposition does not produce further zones}}
\While {$new\_zone\_l$}
\State Split the existing zones $Z$ of $l$ based on the canonical decomposition of the guards on the
outgoing edges of $l$ \Comment{\textsf{\tiny It is not always necessary for a split to happen.}}
\State For every zone $Z$ of $l$, consider $Z \uparrow$ and split it further based on the canonical
decomposition of the guards on the outgoing edges of $l$
\Comment{\textsf{\tiny Note that the zones created from this split are convex.}}
\State Abstract each of the newly created zones if necessary and update edges appropriately.
\If {new zones are not created} set $new\_zone\_l$ to $false$.
\EndIf
\EndWhile
\If {any new zones of $l$ are created or any existing zones of $l$ are modified due to the canonical
decomposition of the outgoing edges of $l$ and $successors\_added = false$} 
\State for all the successor locations $l_j$ of $l$ to Q, enqueue $\langle l_j, l \rangle$ to Q.
\EndIf
\EndWhile
\State  /* \textsf{Phase 2 :  In this phase, pre-stability is enforced} */
\State $new\_zone = true$
\While {$new\_zone$}
\State $new\_zone  = false$
\ForAll {edges $l_i \to{g, a, R'} l_j$}
\ForAll {pairs of zones $Z_{lik}$, $Z_{ljm}$ such that $Z_{lik} \to{\alpha}Z_{ljm}$ is an edge in the 
zone graph where $\alpha \in Act \cup \mathbb{R}_{\ge 0}$}
\If {$Z_{lik}$ is not pre-stable with respect to $Z_{ljm}$,}
Split $Z_{lik}$ to make it pre-stable with respect to $Z_{ljm}$.   \Comment{\textsf{\tiny Note that this split still maintains 
convexity of $Z_{lik}$ since the zone is split entirely along an axis that is parallel to the diagonal in 
the $\lvert C\lvert$-dimensional space.}}
\State $new\_zone := true$
\State Update the incoming and the outgoing edges for the newly created zones.
\EndIf
\EndFor
\EndFor
\EndWhile
}
\end{algorithmic}
\end{algorithm}

The detailed algorithm for creating the zone graph has been described in Algorithm \ref{algo-zonegraph}
and consists of two phases, the first one being a forward analysis of the timed automaton while the second phase
ensures pre-stability in the zone graph.
The presence of an edge to a location $l'$ in the timed automaton does not
imply that the the action of the edge can be performed or
location $l'$ is reachable.
For an edge $l \to{g, a, R} l'$, if for all zones $Z$ of $l$,
$Z \cap g = \emptyset$, then action $a$ cannot be performed at $l$
and $l'$ cannot be reached at $l$.
Such edges can be removed from the timed automaton.
For a location $l'$, if the actions corresponding to none of
the incoming edges can be performed, then the location $l'$
is unreachable and it can be removed along with its incoming and
outgoing transitions.

The set of valuations for every 
location is initially split into zones based on the canonical decomposition of its outgoing transition\delete{as discussed in
\cite{TY1}}. 

After phase 2, pre-stability ensures the following: For a node $(l, z)$ in the zone graph, with $v \in z$,
\delete{such that for a $v \models z$,}for a timed trace $tr$,
if $(l, v) \to{tr} (l'', v'')$, with $v'' \in z''$, then 
$\forall v' \; \delete{\models}\mbox{in}\; z$, $\exists tr'.(l, v') \to{tr'} (l'', \tilde{v})$, with
$untime(tr') = untime(tr)$ and $\tilde{v} \in z''$.
\delete{Here $untime(tr)$ represents the sequence of visible actions in $tr$.}According to the construction given
in algorithm \ref{algo-zonegraph}, for a particular location of the timed automaton, the zones corresponding 
to any two nodes are disjoint. Convexity of the zones and pre-stability property \delete{of the zones}together ensure
that a zone with elapse of time is intercepted by a single hyperplane of the form $x = h$,
where $x \in C$ and $h \in \mathbb{N}$\delete{in the future}.
This is stated formally in Lemma \ref{lem-pre-stability}.
Some approaches for preserving convexity and implementing pre-stability have been discussed \delete{in detail}in \cite{TY1}. 
As an example consider the timed automaton in Figure \ref{fig-delayZone}. The zones corresponding to location $l_1$ as produced through algorithm \ref{algo-zonegraph} are shown in the right side of the figure.

For a state $q \in T(A)$, $\mathcal{N}(q)$ represents the node
 of the zone \delete{valuation}graph with the same location as that of $q$ such that the zone corresponding to $\mathcal{N}(q)$ includes 
 the valuation of $q$. We often say that a state $q = (l, v)$ is in node $s = (l, Z)$ to indicate that $v \in Z$. For two zone \delete{valuation}graphs, 
 $\mathcal{G}_{A_1} = (S_1,s_0,Lep,\rightarrow_1)$, $\mathcal{G}_{A_2} = (S_2,s_0',Lep,\rightarrow_2)$ and a relation
 $\mathcal{R}\subseteq S_1\times S_2$, $\mathcal{G}_{A_1}\:\mathcal{R}\:\mathcal{G}_{A_2}$ iff $(s_p,s_q)\in \mathcal{R}$. 
An $\varepsilon$ transition represents a delay $d \in \mathbb{R}_{\ge 0}$.
\subsection{Creating pre-stable zones}

We describe below a procedure for splitting a zone $Z_1$ into a set $\mathcal{Z}_1$ of zones w.r.t a zone $Z_2$
such that the following properties are satisfied.
\begin{enumerate}
\item Each zone $Z_i$ in $\mathcal{Z}_1$ should either be a subset of $Z_2$ or disjoint from $Z_2$.
\item The DBMs in $\mathcal{Z}_1$ are mutually exclusive and disjoint.
\item The union of the DBMs in $\mathcal{Z}_1$ is $Z_1$.
\end{enumerate}

A naive approach would be to populate $\mathcal{Z}_1$ with two DBMs, 
namely the (set) intersection and (set) difference of $Z_1$ with $Z_2$.
This ensures that the properties 1, 2 and 3 hold. 
However, while the intersection of two DBMs is always a DBM, this cannot be said for their difference. 
Thus, we seek to refine our process by replacing the difference of $Z_1$ and $Z_2$
with some DBMs which are mutually exclusive and which cover the difference of $Z_1$ and $Z_2$,
so that properties 2 and 3 continue to hold.

One naive way to achieve this is to initially populate $\mathcal{Z}_1$ with only $Z_1$,
and then iterate through all the elementary clock constraints $c_{ij}$ of $Z_2$. 
The element $m_{ij}$ in the DBM is a constraint of the form $x_i - x_j < k$ or $x_i - x_j \le k$.
In each iteration, we replace each DBM in $\mathcal{Z}_1$ with two DBMs, namely its intersection and difference with $c_{ij}$.
Note that the complement of an elementary clock constraint is always an elementary clock constraint 
and thus the difference can be calculated by simply taking the intersection 
with the complement of the elementary constraint, which implies that 
both the intersection and the difference considering a single elementary constraint as above are DBMs. 
Of course, some of the DBMs thus produced may be empty, and we do not add these to $\mathcal{Z}_1$. 
The theoretical bound on the number of DBMs in $\mathcal{Z}_1$ at the end is
$2^{\mbox{(number of elementary clock constraints in dbm2)}}$, 
that is, $2^{O((n+1)^2)}$.
The term $(n+1)^2$ comes from the fact that there are $(n+1)^2$ entries in $Z_2$ 
each of which is an elementary clock constraint. 
The above exponential bound is because of the fact that, in the worst case, 
we double the number of DBMs in $\mathcal{Z}_1$ in each iteration.
This leaves us with a set of mutually exclusive zones which satisfies properties 1, 2 and 3.

However, this is inefficient in that it generates too many zones. 
So, we refine the process of iterating through the elementary clock constraints $c_{ij}$.
We start with an empty $\mathcal{Z}_1$ and a pointer which initially points to $Z_1$. 
At each iteration, we evaluate the intersection of $c_{ij}$ and the zone pointed to by the pointer
and also their difference which too is a zone since the difference is calculated
by taking the intersection with the complement of $c_{ij}$.
The pointer is then updated to point to the intersection DBM, 
while the difference DBM is added to $\mathcal{Z}_1$. 
This procedure continues until all the $c_{ij}$ have been seen.
In the end, if the pointer's target is non-empty, we add it to $\mathcal{Z}_1$. 
At this point, the zones in $\mathcal{Z}_1$ still cover $Z_1$ and also satisfy properties 1 and 2. 
This method leads to a maximum of one zone being added to $\mathcal{Z}_1$ for each $c_{ij}$,
and one zone being added at the end, which gives us a maximum of $O((n + 1)^2 + 1)$ zones in $\mathcal{Z}_1$.

Algorithm \ref{algo-splitZone} describes the procedure mentioned above formally.

\begin{algorithm}
\caption{This algorithm returns the intersection and the difference of two zones.\newline 
\emph{Input: Two zones $Z_1$ and $Z_2$ \newline
Output: i) $Z$ which is $Z_1 \cap Z_2$ and ii) $\mathcal{Z}_1$, a set of zones whose union is $Z_1 - Z_2$}
}\label{algo-splitZone}
\begin{algorithmic}[1]
{\small
\State $Z := Z_1 \cap Z_2$
\State $\mathcal{Z}_1 := \emptyset$, $p := Z_1$ \Comment{\textsf{\tiny $p$ is a pointer pointing to a zone.}}
\ForAll {$i \in [0, n]$}
\ForAll {$j \in [0, n]$}
\State Let $c_{ij}$ be the constraint $x_i - x_j \prec m_{ij}$, where $(m_{ij}, \prec)$ is the corresponding entry in the DBM
of $Z_2$.
\State Let $\overline{c_{ij}}$ be the complement of the constraint $c_{ij}$.
\State $Z_{11} := p \cap c_{ij}$, $Z_{12} := p \cap \overline{c_{ij}}$
\If {$Z_{12} \neq \emptyset$}
\State $\mathcal{Z}_1 := \mathcal{Z}_1 \cup Z_{12}$
\EndIf
\If {$Z_{11} \neq \emptyset$}
\State $p := Z_{11}$
\EndIf
\EndFor
\EndFor
\If {$Z_{11} \neq \emptyset$} 
\State $\mathcal{Z}_1 = \mathcal{Z}_1 \cup Z_{11}$
\EndIf
}
\end{algorithmic}
\end{algorithm}

Pre-stability is ensured corresponding to both \emph{delay} and \emph{discrete} transitions in the zone graph.
\begin{itemize}
\item {\bf Pre-stabilizing zones corresponding to delay transitions:} 
Consider two nodes in the zone graph $(l, Z) \to{\varepsilon} (l, Z')$ such that $Z$ is not pre-stable w.r.t $Z'$.
The procedure involves splitting $Z$ w.r.t $Z'\!\!\downarrow$ such that each newly created zones 
obtained by splitting $Z$ is pre-stable w.r.t. $Z'$.

We follow the procedure given in Algorithm \ref{algo-splitZone} to split a zone $Z$ w.r.t the zone $Z'$.
\item {\bf Pre-stabilizing zones corresponding to discrete transitions  in the zone graph:} 
Consider two nodes in the zone graph $(l, Z) \to{a} (l', Z')$ such that $a \in Act$  and $Z$ is not pre-stable w.r.t $Z'$.
The method involving the pre-stabilization operation is similar to the $Pre_e(Z')$ operator used in backward analysis
of the timed automaton, where $e$ is an edge between say location $l$ and $l'$ of the timed automaton and $Z'$ is a zone of $l'$.
Formally for an edge $l \to{g, a, R} l'$ $Pre_e(Z')$ is defined as the following:
\begin{center}
$Pre_e(Z') = \{v \in \mathbb{R}_{\ge 0}^{\lvert C \lvert}\ \lvert \exists v' \in Z', \: \exists t \in \mathbb{R}_{\ge 0} \mbox{ such that }
v + t \models g \mbox{ and }$ \\
$[R\leftarrow 0] (v + t) = v'\}$
\end{center}
Let $\sembrack{R = 0}$ denotes the set of all clock valuations $v$
such that $v(x) = 0$ when $x \in R$ and $v(x) \in \mathbb{R}_{\ge 0}$ when $x \notin R$. $v(x)$ denotes the valuation of clock $x$.
In our case, we define the zone $\widehat{Z'}$ as follows:\\
$\widehat{Z'} = [R \leftarrow 0]^{-1}(Z' \cap \sembrack{R = 0})$.
Now $Z$ is split w.r.t $\widehat{Z'}$ following Algorithm \ref{algo-splitZone} that
makes all the newly created zones pre-stable w.r.t $Z'$.
\end{itemize}

The following lemma states an important property of the zone graph which will further be used for clock reduction.
\begin{lemma} \label{lem-pre-stability}
Pre-stability ensures that
if the zone $Z$ in any node $(l, Z)$ in the zone graph
is bounded above, then it is bounded fully from above
by a hyperplane $x = h$, where $x \in C$ and $h \in \mathbb{N}$.
\end{lemma}
\begin{proof}
We show the proof for two clocks. The same argument holds for arbitrary number of clocks.
Consider a $\lvert C \lvert$ dimensional zone $Z$.
Since $\lvert C \lvert = 2$, a zone $Z$ that is bounded above is of the form $k_{xy_2} \prec x - y \prec k_{xy_1}$,
$k_{x_1} \prec x \prec k_{x_2}$ and $k_{y_1} \prec y \prec k_{y_2}$,
where $x$ and $y$ are the two clocks, $\prec \in \{<, \le\}$.
Let $Z$ be bounded above by two hyperplanes $x = k_{x_2}$ and  $y = k_{y_2}$.
As can be seen from Figure \ref{fig-pre-proof}, there are two zones $Z_1$ and $Z_2$ such that
$Z_1$ is defined by the inequations $x-y \prec k_{xy_1}$, $k_{x_2} \prec x$ and $y \prec k_{y_2}$,
while $Z_2$ is defined as $k_{xy_2} \prec x-y$, $x \prec k_{x_2}$ and $k_{y_2} \prec y$.
Making $Z$ pre-stable will divide it into two parts:
\begin{itemize}
\item $Z'$ defined by the inequations
$k_{x_2} -  k_{y_2} \prec x - y \prec k_{xy_1}$, $k_{x_1} \prec x \prec k_{x_2}$ and $k_{y_1} \prec y$ and
\item $\widehat{Z}$ define by the inequations
$k_{xy_2} \prec x - y \prec k_{x_2} -  k_{y_2}$, $k_{x_1} \prec x$ and $y \prec k_{y_2}$
\end{itemize}
$Z'$ is bounded fully from above by the hyperplane $k_{x_2}$ while $\widehat{Z}$ is bounded fully from above by the hyperplane $k_{y_2}$.
Note that the inequations defining the zones $Z'$ and $\widehat{Z}$ may vary depending on
the relation among the various constants $k_{xy_1}, k_{xy_2}, k_{x_1}, k_{x_2}, k_{y_1}$ and $k_{y_2}$.
In all cases, pre-stability will ensure that there exists a single hyperplane that fully bounds a zone from above.
\end{proof}
\begin{figure}
\centering
\vspace{-10pt}
\includegraphics[width=0.3\textwidth]{pre-stability.pdf}
\caption{\label{fig-pre-proof}For every zone, there exists a hyperplane that bounds it fully from above in a pre-stable zone graph}
\vspace{-10pt}
\end{figure}
