30 July 2021
AperTO - Archivio Istituzionale Open Access dell'Università di Torino
Original Citation:
Probabilistic Timed Automata with Clock-Dependent Probabilities
Published version:
DOI:10.3233/FI-2021-2000
Terms of use:
Open Access
(Article begins on next page)
Anyone can freely access the full text of works made available as "Open Access". Works made available under a Creative Commons license can be used according to the terms and conditions of said license. Use of all other works requires consent of the right holder (author or publisher) if not exempted from copyright protection by the applicable law.
Availability:
This is the author's manuscript
Probabilistic Timed Automata with Clock-Dependent
Probabilities
Jeremy Sproston
Dipartimento di Informatica, University of Turin, Italy
sproston@di.unito.it
Abstract
Probabilistic timed automata are classical timed automata extended with discrete probability distributions over edges. We introduce clock-dependent probabilistic timed automata, a variant of probabilistic timed automata in which transition probabilities can depend linearly on clock values. Clock-dependent probabilistic timed automata al-low the modelling of a continuous relationship between time passage and the likelihood of system events. We show that the problem of deciding whether the maximum probabil-ity of reaching a certain location is above a threshold is undecidable for clock-dependent probabilistic timed automata. On the positive side, we show that the maximum and min-imum probability of reaching a certain location in clock-dependent probabilistic timed automata can be approximated using a region-graph-based approach.
1
Introduction
Reactive systems are increasingly required to satisfy a combination of qualitative criteria (such as safety and liveness) and quantitative criteria (such as timeliness, reliability and per-formance). This trend has led to the development of techniques and tools for the formal verification of both qualitative and quantitative properties. In this paper, we consider a for-malism for real-time systems that exhibit randomised behaviour, namely probabilistic timed automata (PTA) [1, 2]. PTA extend classical Alur-Dill timed automata [3] with discrete probabilistic branching over automata edges; alternatively a PTA can be viewed as a Markov decision process [4] or a Segala probabilistic automaton [5] extended with timed-automata-like clock variables and constraints over those clocks. PTA have been used previously to model case studies including randomised protocols and scheduling problems with uncertainty [6, 7], some of which have become standard benchmarks in the field of probabilistic model checking. We recall briefly the behaviour of a PTA: as time passes, the model stays within a particular discrete state, and the values of its clocks increase at the same rate; at a certain point in time, the model can leave the discrete state if the current values of the clocks satisfy a constraint (called a guard) labelling one of the probability distributions over edges leaving the state; then a probabilistic choice as to which discrete state to then visit is made according to the chosen distribution over edges. In the standard presentation of PTA, any dependencies between time and probabilities over edges must be defined by utilising multiple distributions enabled with different sets of clock values. For example, to model the fact that a packet loss is more likely as time passes, we can use clock x to measure time, and two distributions µ1 and µ2 assigning
probability λ1 and λ2 (for λ1 < λ2), respectively, to taking edges leading to a discrete state
corresponding to packet loss, where the guard of µ1 is x ≤ c and the guard of µ2 is x > c,
loss occurs with probability λ1, otherwise it occurs with probability λ2. A more direct way
of expressing the relationship between time and probability would be letting the probability of making a transition to a discrete state representing packet loss be dependent on the value of the clock, i.e., let the value of this probability be equal to f (x), where f is an increasing function from the values of x to probabilities. We note that such a kind of dependence of discrete branching probabilities on values of continuous variables is standard in the field of stochastic hybrid systems, for example in [8].
In this paper we consider such a formalism based on PTA, in which all probabilities used by edge distributions can be expressed as functions of values of the clocks used by the model: the resulting formalism is called clock-dependent probabilistic timed automata (cdPTA). We focus on a simple class of functions from clock values to probabilities, namely those that can be expressed as sums of continuous linear functions, and consider a basic problem in the context of probabilistic model checking, namely probabilistic reachability: determine whether the maximum (respectively, minimum) probability of reaching a certain set of discrete states from the initial state is above (respectively, below) a threshold. After introducing cdPTA (in Section 2), our first result (in Section 3) is that the probabilistic reachability problem is undecidable for cdPTA with a least three clocks. This result is inspired from recent related work on stochastic timed Markov decision processes [9]. Furthermore, we give an example of cdPTA with one clock for which the maximal probability of reaching a certain discrete state involves a particular edge being taken when the clock has an irrational value. This suggests that classical techniques for partitioning the state space into a finite number of equivalence classes on the basis of a fixed, rational-numbered time granularity, such as the region graph [3] or the corner-point abstraction [10], cannot be applied directly to the case of cdPTA to obtain optimal reachability probabilities, because they rely on the fact that optimal choices can be made either at or arbitrarily closely to clock values that are multiples of the chosen rational-numbered time granularity. In Section 4, we present a conservative approximation method for cdPTA, i.e., maximum (respectively, minimum) probabilities are bounded from above (respectively, from below) in the approximation. This method is based on the region graph but uses concepts from the corner-point abstraction to define transition distributions. We show that successive refinement of the approximation, obtained by increasing the time granularity by a constant factor, does not lead to a more conservative approximation: in practice, in many cases such a refinement can lead to a substantial improvement in the computed probabilities, as we show using a small example. Furthermore, we show that, for the class of cdPTA for which the target states can only be reached within a bounded number of steps, for any time granularity, we can obtain a bound on the difference of the probabilities computed on the approximation and those of the cdPTA, and that increasing the time granularity results in a quantifiable improvement in the bound. This final result, together with proofs of all results and additional examples, extends the workshop version of the paper [11]. This paper is a post-print version of [12].
2
Clock-Dependent Probabilistic Timed Automata
2.1
Preliminaries
We use R≥0 to denote the set of non-negative real numbers, Q to denote the set of rational
numbers and N to denote the set of natural numbers. A (discrete) probability distribution over a countable set Q is a function µ : Q → [0, 1] such that P
q∈Qµ(q) = 1. For a function
µ : Q → R≥0 we define support(µ) = {q ∈ Q : µ(q) > 0}. For an uncountable set Q we
set and µ restricted to support(µ) is a (discrete) probability distribution. Given q ∈ Q, we use {q 7→ 1} to denote the distribution that assigns probability 1 to the single element q. Let {µi}i∈I ⊆ Dist(Q) be a set of distributions and {λi}i∈I be a set of weights such that λi > 0 for
all i ∈ I and P
i∈Iλi = 1. Then we write
L
i∈Iλi· µi to refer to the distribution over Q such
that (L
i∈Iλi· µi)(q) =
P
i∈Iλi· µi(q) for each q ∈ Q.
A probabilistic transition system (PTS) T = (S, s, Act , ∆) comprises the following compo-nents: a set S of states with an initial state s ∈ S, a set Act of actions, and a probabilistic transition relation ∆ ⊆ S × Act × Dist(S). The sets of states, actions and the probabilistic transition relation can be uncountable. Transitions from state to state of a PTS are performed in two steps: if the current state is s, the first step concerns a nondeterministic selection of a probabilistic transition (s, a, µ) ∈ ∆; the second step comprises a probabilistic choice, made according to the distribution µ, as to which state to make the transition (that is, a transition to a state s0 ∈ S is made with probability µ(s0)). We denote such a completed transition by
s −→ sa,µ 0. We assume that for each state s ∈ S there exists some (s, a, µ) ∈ ∆.
An infinite run of the PTS T is an infinite sequence of consecutive transitions r = s0 a0,µ0
−−−→ s1
a1,µ1
−−−→ · · · (i.e., the target state of one transition is the source state of the next). Similarly, a finite run of T is a finite sequence of consecutive transitions r = s0
a0,µ0
−−−→ s1 a1,µ1
−−−→ · · ·−−−−−−→an−1,µn−1 sn. We use InfRunsT to denote the set of infinite runs of T , and FinRunsT the set of finite
runs of T . If r is a finite run, we denote by last (r) the last state of r. For any infinite run r and i ∈ N, let r(i) = si be the (i + 1)th state along r. Let FinRunsT(s) and InfRunsT(s)
refer to the set of finite and infinite runs of T , respectively, commencing in state s ∈ S. A strategy of a PTS T is a function σ mapping every finite run r ∈ FinRunsT to a distribution in Dist(∆) such that (s, a, µ) ∈ support(σ(r)) implies that s = last (r). From [13, Lemma 4.10], without loss of generality we can assume henceforth that strategies map to distributions assigning positive probability to finite sets of elements, i.e., strategies σ for which |support(σ(r))| is finite for all r ∈ FinRunsT. Let ΣT be the set of strategies of T ; when clear from the context, we write simply Σ. For any strategy σ, let FinRunsσ and InfRunsσ denote the set of finite and infinite runs, respectively, resulting from the choices of σ. For a state s ∈ S, let FinRunsσ(s) = FinRunsσ∩ FinRunsT(s) and InfRunsσ(s) = InfRunsσ ∩ InfRunsT(s).
Given a strategy σ and a state s ∈ S, we define the probability measure Prσs over InfRunsσ(s) in the following, standard way [14]. A Markov chain (MC) M = (S, s, P) com-prises a set S of states with the initial state s ∈ S, and a probabilistic transition function P : S × S → [0, 1], such that P
s0∈SP(s, s0) = 1 for all s ∈ S. Given a PTS T = (S, s, Act , ∆),
a state s ∈ S, and a strategy σ ∈ Σ, we can define a countably infinite-state MC Mσ s =
(FinRunsσ(s), s, Pσs), where Pσs is defined in the following way: for r, r0 ∈ FinRunsσ(s), we let Pσ
s(r, r
0) = σ(r)(last (r), a, µ) · µ(s0) if r0 = r −→ sa,µ 0, and we let Pσ s(r, r
0) = 0 otherwise.
For a finite path r ∈ FinRunsσ(s), where r = s0 a0,µ0 −−−→ s1 a1,µ1 −−−→ · · · −−−−−−→ san−1,µn−1 n, and i ≤ n let r ↓i= s0 a0,µ0 −−−→ s1 a1,µ1
−−−→ · · · −−−−−→ sai−1,µi−1 i. Then we let Pσs(r) = Pσs(r ↓0, r ↓1) · Pσs(r ↓1, r ↓2
) · . . . · Pσ
s(r↓n−1, r↓n). Let Cyl(r) ⊆ InfRunsσ(s) be the set of infinite runs with r as a prefix,
and let Prσs be the unique measure such that Prσs(Cyl(r)) = Pσs(r).
Given a set SF ⊆ S, define 3SF = {r ∈ InfRunsT : ∃i ∈ N s.t. r(i) ∈ SF} to be
the set of infinite runs of T such that some state of SF is visited along the run. Given
a set Σ0 ⊆ Σ of strategies, we define the maximum value over Σ0 with respect to S F as
PmaxT ,Σ0(SF) = supσ∈Σ0 Prσs(3SF). Similarly, the minimum value over Σ0 with respect to SF is
defined as Pmin
T ,Σ0(SF) = infσ∈Σ0 Prσ
s(3SF). The maximal reachability problem for T , SF ⊆ S,
Σ0 ⊆ Σ, ∈ {≥, >} and λ ∈ [0, 1] is to decide whether Pmax
T ,Σ0(SF) λ. Similarly, the minimal
reachability problem for T , SF ⊆ S, Σ0 ⊆ Σ, ∈ {≤, <} and λ ∈ [0, 1] is to decide whether
PminT ,Σ0(SF) λ.
the union of states contained in some set of equivalence classes of ≡. Given two distributions µ, µ0 over S, we write µ ≡ µ0 if P
s∈Cµ(s) =
P
s∈Cµ
0(s) for all equivalence classes C of ≡. A
combined transition from state s ∈ S is a pair ({(s, ai, µi)}i∈I, {λi}i∈I) such that (s, ai, µi) ∈ ∆
and λi > 0 for all i ∈ I, and
P
i∈Iλi = 1. Let A ⊆ Act be a set of actions. Then a probabilistic
simulation respecting ≡ and A is a relation ⊆ S ×S such that s t implies that (1) s ≡ t, and (2) for each transition (s, a, µ) ∈ ∆, there exists a combined transition ({(t, ai, µi)}i∈I, {λi}i∈I)
such that µ ≡L
i∈Iλi· µi, {ai}i∈I ⊆ A if a ∈ A, and {ai}i∈I ⊆ Act \ A if a ∈ Act \ A.1
Next, we consider strategies that alternate between actions in a certain set A ⊆ Act and actions in the complement set Act \ A. Formally, an A-alternating strategy σ is a strategy such that, for finite run r ∈ FinRunsT that has s−→ sa,µ 0 as its final transition, then {a0 ∈ Act :
(s, a0, µ) ∈ support(σ(r))} ⊆ A if a ∈ Act \ A, and {a0 ∈ Act : (s, a0, µ) ∈ support(σ(r))} ⊆
Act \ A if a ∈ A. Let ΣTA be the set of A-alternating strategies of T ; when the context is clear, we write simply ΣA rather than ΣTA.
Given two PTSs T1 = (S1, s1, Act1, ∆1) and T2 = (S2, s2, Act2, ∆2), their disjoint union is
defined as the PTS (S1] S2, , Act1] Act2, ∆1] ∆2) (where the initial state is irrelevant and is
hence omitted). The following result is essentially identical to [13, Lemma 3.17, Lemma 3.18] (which in turn relies on [5, Theorem 8.6.1]).
Proposition 1. [13] Let A1 ⊆ Act1, let A2 ⊆ Act2, and let ≡ be an equivalence relation over
S1] S2 that respects SF . If s1 s2 for a probabilistic simulation respecting ≡ and A1] A2,
then Pmax
T1,ΣA1(SF) ≤ PmaxT2,ΣA2(SF) and PT1min,ΣA1(SF) ≥ PminT2,ΣA2(SF).
2.2
Clock-Dependent Probabilistic Timed Automata
Let X be a finite set of real-valued variables called clocks, the values of which increase at the same rate as real-time and which can be reset to 0. A function v : X → R≥0 is referred to as
a clock valuation and the set of all clock valuations is denoted by RX≥0. For v ∈ RX≥0, t ∈ R≥0
and X ⊆ X , we use v+t to denote the clock valuation that increments all clock values in v by t, and v[X:=0] to denote the clock valuation in which clocks in X are reset to 0. Formally, (v+t)(x) = v(x)+t for all x ∈ X , v[X:=0](x) = 0 for all x ∈ X, and v[X:=0](x) = v(x) for all x ∈ X \ X.
For a set Q, a distribution template d : RX≥0 → Dist(Q) gives a distribution over Q for
each clock valuation. In the following, we use notation d[v], rather than d(v), to denote the distribution corresponding to distribution template d and clock valuation v. Let Templates(Q) be the set of distribution templates over Q.
The set CC (X ) of clock constraints over X is defined as the set of conjunctions over atomic formulae of the form x ∼ c, where x ∈ X , ∼∈ {<, ≤, ≥, >} and c ∈ N. A clock valuation v satisfies a clock constraint ψ, denoted by v |= ψ, if ψ resolves to true when substituting each occurrence of clock x with v(x).
A clock-dependent probabilistic timed automaton (cdPTA) P = (L, ¯l, X , inv , prob) com-prises the following components:
• a finite set L of locations with an initial location ¯l ∈ L; • a finite set X of clocks;
1 Our notion of probabilistic simulation respecting an equivalence relation is stronger than that of
proba-bilistic simulation of [5], because in our setting we require that the distributions referred to in the definition assign the same probability to equivalence classes, whereas the standard definition of probabilistic simulation requires that corresponding transitions should be related by a weight function based on the probabilistic sim-ulation preorder. Also note that we do not require actions to be matched in the definition of probabilistic simulation respecting ≡, although we do require that matching actions are either all in A or all in Act \ A: in this paper, we use actions in later sections only to clarify aspects of correctness proofs.
TL x ≤ 2 y ≤ cmax TR x ≤ 2 y ≤ cmax BL x ≤ 3 y ≤ cmax BR x ≤ 0 7 X x ≥ 1 x ≥ 1 x − 1 {x} 2 − x {x} {x} x − 1 2 − x {x} x ≥ 1 {x} x−1 2 1 −x−12 {x} x ≥ 2 x − 2 {x} 3 − x {x} x = 0 1 −cy max y cmax y = cmax
Figure 1: A cdPTA modelling a simple robot example.
• a function inv : L → CC (X ) associating an invariant condition with each location; • a set prob ⊆ L × CC (X ) × Templates(2X × L) of probabilistic edges.
A probabilistic edge (l, g, p) ∈ prob comprises: (1) a source location l; (2) a clock constraint g, called a guard ; and (3) a distribution template p with respect to pairs of the form (X, l0) ∈ 2X × L (i.e., pairs consisting of a set X of clocks to be reset and a target location l0).
The behaviour of a cdPTA takes a similar form to that of a standard probabilistic timed automaton [1, 2]: in any location time can advance as long as the invariant holds, and the choice as to how much time elapses is made nondeterministically; a probabilistic edge can be taken if its guard is satisfied by the current values of the clocks, and the choice as to which probabilistic edge to take is made nondeterministically; for a taken probabilistic edge, the choice of which clocks to reset and which target location to make the transition to is probabilistic. The key difference with cdPTA is that the distribution used to make this probabilistic choice depends on the probabilistic edge taken and on the current clock valuation.
Example 1. In Figure 1 we give an example of a cdPTA modelling a simple robot that must reach a certain geographical area and then carry out a particular task. The usual conventions for the graphical representation of timed automata are used in the figure. Black squares denote the distributions of probabilistic edges, and expressions on probabilities used by distribution templates are written with a grey background labelling their outgoing arcs. Edges without black squares correspond to probabilistic edges assigning probability 1 to a single clock set/target location pair. The robot can be in one of four geographical areas, which can be thought of as cells in a 2 × 2 grid, each of which corresponds to a cdPTA location. The robot begins in the top-left cell (corresponding to location TL), and its objective is to reach the bottom-right cell (location BR). From the top-left cell, the robot can move either to the top-right cell (location TR), or to the bottom-left cell (location BL). In each cell, the robot must wait a certain amount of time (1 time units in the top cells and 2 time units in the bottom-left cell) before attempting to leave the cell (for example, to recharge solar batteries), after which it can spend at most 1 time unit attempting to leave the cell. With a certain probability, the attempt to leave the cell will fail. The more time dedicated to an attempt to leave the cell, the more likely the attempt will succeed. If the attempt to leave the cell fails, the robot must wait before trying to leave the cell again. Although passing through the top-right cell is not slower than passing through the bottom-left cell, the probability of leaving the cell successfully increases at a slower rate than in other cells (hence, the top-right cell could represent a short route to the bottom-right cell, but
through terrain in which the robot finds it difficult to navigate). On arrival in the bottom-right cell, the robot successfully carries out its task with a probability that is inversely proportional to the total time elapsed (for example, the robot could be transporting medical supplies, the efficacy of which may be inversely proportional to the time elapsed). The clock x is used to represent the amount of time used by the robot in its attempt to move from cell to cell, whereas the clock y represents the total amount of time since the start of the robot’s mission. If the clock y reaches its maximum amount cmax, then the mission fails (as denoted by the edge to
the location denoted by 7, which is available in locations TL, TR, BL and BR, as indicated by the dashed box). The objective of the robot’s controller is to maximise the probability of reaching the location denoted by X. Note that there is a trade-off between dedicating more time to movement between the cells, which increases the probability of successful navigation and therefore progress towards the target point, and spending less time on the overall mission, which increases the probability of carrying out the required task at the target point.
A state of a cdPTA is a pair comprising a location and a clock valuation satisfying the location’s invariant condition, i.e., (l, v) ∈ L × RX≥0 such that v |= inv (l). In any state (l, v),
either a certain amount of time δ ∈ R≥0 elapses, or a probabilistic edge is traversed. If time
elapses, then the choice of δ requires that the invariant inv (l) remains continuously satisfied while time passes. The resulting state after this transition is (l, v+δ). A probabilistic edge (l0, g, p) ∈ prob can be chosen from state (l, v) if l = l0 and it is enabled, i.e., the clock constraint g is satisfied by v. Once a probabilistic edge (l, g, p) is chosen, a set of clocks to reset to 0 and a successor location are selected at random, according to the distribution p[v]. Note that the fundamental difference between cdPTA and the standard PTA formalism concerns the fact that, in PTA, the third component of edges is a distribution, rather than a distribution template, and hence the probabilities used in a PTA do not depend on valuations.
We make a number of assumptions concerning the cdPTA models considered. These as-sumptions are standard for PTA, and enable the definition of (cd)PTA semantics. Firstly, we restrict our attention to cdPTA for which it is always possible to take a probabilistic edge, either immediately or after letting time elapse. This condition holds generally for PTA models in practice [6]. A sufficient syntactic condition for this property has been presented formally in [15]. Secondly, in the standard manner for PTA [7], we assume that all possible target states of probabilistic edges satisfy their invariants: for all probabilistic edges (l, g, p) ∈ prob, for all clock valuations v ∈ RX≥0 such that v |= g, and for all (X, l0) ∈ 2X × L, we have that
p[v](X, l0) > 0 implies v[X := 0] |= inv (l0). Thirdly, we assume that any clock valuation that satisfies the guard of a probabilistic edge also satisfies the invariant of the source location: this can be achieved, without changing the underlying semantic PTS, by replacing each probabilis-tic edge (l, g, p) ∈ prob by (l, g ∧ inv (l), p). Finally, we consider cdPTA that feature invariant conditions that prevent clock values from exceeding some bound: formally, for each location l ∈ L, we have that inv (l) contains a constraint of the form x ≤ c or x < c for each clock x ∈ X (this assumption is not necessary for the definition of the semantics of cdPTA, but will simplify the material in subsequent sections).2
Let 0 ∈ RX≥0 be the clock valuation that assigns 0 to all clocks in X . The semantics of the
cdPTA P = (L, ¯l, X , inv , prob) is the PTS [[P]] = (S, s, Act , ∆) where: • S = {(l, v) : l ∈ L and v ∈ RX
≥0 s.t. v |= inv (l)} and s = {(¯l, 0)};
• Act = R≥0∪ prob;
2 Note that we relax some of these assumptions when depicting cdPTA graphically. For example, we
generally depict final locations, and sink locations that cannot reach a target location, without invariant conditions or outgoing edges. To satisfy the above assumptions, we can equip each such a location with an invariant condition x ≤ M for some clock x, where M is the greatest constant featured in guards or invariant conditions of the cdPTA, and with a self-loop probabilistic edge with guard x ≤ M and a clock reset set {x}.
• ∆ =−→∆ ∪ b∆, where −→∆ ⊆ S × R≥0× Dist(S) and b∆ ⊆ S × prob × Dist(S) such that:
– −→∆ is the smallest set such that ((l, v), δ, {(l, v + δ) 7→ 1}) ∈ −→∆ if there exists δ ∈ R≥0 such that v + δ0 |= inv (l) for all 0 ≤ δ0 ≤ δ;
– b∆ is the smallest set such that ((l, v), (l, g, p), µ) ∈ b∆ if 1. v |= g;
2. for any (l0, v0) ∈ S, we have µ(l0, v0) = P
X∈Reset(v,v0)p[v](X, l0), where
Reset(v, v0) = {X ⊆ X | v[X := 0] = v0}.
When considering maximum and minimum values for cdPTA, we henceforth consider strategies that alternate between transitions from −→∆ (time elapse transitions) and transitions from b∆ (probabilistic edge transitions). Formally, a cdPTA strategy σ is a strategy such that, for a finite run r ∈ FinRuns[[P]] that has s−→ sa,µ 0 as its final transition, either (s, a, µ) ∈−→∆ and
support(σ(r)) ⊆ b∆, or (s, a, µ) ∈ b∆ and support(σ(r)) ⊆−→∆ . We write Σ for the set of cdPTA strategies of [[P]]. Given a set F ⊆ L of locations, subsequently called target locations, we let SF = {(l, v) ∈ S : l ∈ F }. Let ∈ {≥, >}, ∈ {≤, <} and λ ∈ [0, 1]: then the maximal
(respectively, minimal) reachability problem for cdPTA is to decide whether Pmax[[P]],Σ(SF) λ
(respectively, Pmin
[[P]],Σ(SF) λ).
2.3
Linear Clock Dependencies
In this paper, we concentrate on a particular subclass of distribution templates based on linear functions. Let x ∈ X be a clock and ψ ∈ CC (X ) be a clock constraint. Let Iψ
x be the interval
containing the values of x of clock valuations that satisfy ψ: formally Ixψ = {v(x) ∈ R≥0 : v ∈
RX≥0 s.t. v |= ψ}. Let I ψ
x be the closure of Ixψ. For example, for ψ = (x ≥ 3)∧(x < 5)∧(y ≤ 8),
we have Ixψ = [3, 5), Ixψ = [3, 5] and Iyψ = I ψ
y = [0, 8]. We equip each probabilistic edge
p = (l, g, p) ∈ prob, clock set/location pair e = (X, l0) ∈ 2X × L and clock x ∈ X , with a pair (cp,e
x , dp,ex ) ∈ Q2 of rational constants. We then define the linear function fxp,e with domain
Ixg by fxp,e(γ) = cp,ex + dp,ex · γ for all γ ∈ Ixg. We make the following assumptions for each
probabilistic edge p ∈ prob:
1. P x∈Xf p,e x (v(x)) ∈ [0, 1] for each e ∈ 2 X × L and v ∈ RX ≥0 such that v |= g; 2. P e∈2X×L P
x∈Xfxp,e(v(x)) = 1 for each v ∈ R X
≥0 such that v |= g.
Then we say that the probabilistic edge p is linear if, for each e ∈ 2X×L and each v ∈ RX≥0such that v |= g, we have p[v](e) = P
x∈Xf p,e
x (v(x)). We assume henceforth that all probabilistic
edges of cdPTA are linear.3
Example 2. Standard methods for the analysis of timed automata typically consist of a finite-state system that represents faithfully the original model. In particular, the region graph [3]
3 The original version of the paper [11] featured piecewise linear clock dependencies, where the functions
defining clock dependencies are linear over intervals of clock values that are bounded by rationals. The version of clock dependencies presented in this paper is no less expressive, because such piecewise linear clock dependencies can be modelled by (1) scaling up all constants in guards, invariants and the endpoints of intervals used to define over which clock dependencies are linear so that the intervals used for defining clock dependencies have natural numbered endpoints, and (2) modelling a probabilistic edge with piecewise linear clock dependencies by multiple probabilistic edges with linear clock dependencies, where the guards of the new probabilistic edges encode the (scaled-up) intervals over which the original piecewise linear clock dependency functions were linear.
A x < 1 B x < 1 C x < 1 D E x > 0 x 1 − x x > 0 1 − x x x > 0 1 − x 2 x 2
Figure 2: A one-clock cdPTA for which the maximum probability is attained by a time delay corresponding to an irrational number.
and the corner-point abstraction [10] both involve the division of the state space according to a fixed, rational-numbered granularity. The example of a one-clock cdPTA P of Figure 2 shows that such an approach cannot be used for the exact computation of optimal reachability probabilities in cdPTA, because optimality may be attained when the clock has an irrational value. For an example of the formal description of a linear probabilistic edge, consider the probabilistic edge from location C, which we denote by pC: then we have IxpC = (0, 1), with
cpC,(∅,D)x = 1, dpC,(∅,D)x = −12, cpC,(∅,E)x = 0, and dpC,(∅,E)x = 12. Now consider the maximum
probability of reaching location D (that is, Pmax
[[P]],Σ(S{D})). Intuitively, the longer the cdPTA
remains in location A, the lower the probability of making a transition to location E from A, but the higher the probability of making a transition to E from B and C. Note that, after A is left, the choice resulting in the maximum probability of reaching D is to take the outgoing transitions from B and C as soon as possible (delaying in B and C will increase the value of x, therefore increasing the probability of making a transition to E). Denoting by δ the amount of time elapsed in A, the maximum probability of reaching D is equal to δ(1 − δ)(1 −δ2), which (within the interval [0, 1)) reaches its maximum at 1 −
√ 3
3 . Hence, this example indicates
that abstractions based on the optimality of choices made at (or arbitrarily close to) rational-numbered clock values (such as the region graph or corner-point abstraction) do not yield exact analysis methods for cdPTA.
3
Undecidability of Maximal Reachability for cdPTA
Theorem 1. The maximal reachability problem is undecidable for cdPTA with at least 3 clocks.
Proof. We proceed by reducing the non-halting problem for two-counter machines to the maximal reachability problem for cdPTA. The reduction has close similarities to a reduction presented in [9].
A two-counter machine M = (L, C) comprises a set L = {`1, ..., `n} of instructions and a
set C = {c1, c2} of counters. The instructions are of the following form (for i, j, k ∈ {1, ..., n}
and m ∈ {1, 2}):
1. `i : cm := cm+ 1; goto `j (increment cm);
2. `i : cm := cm− 1; goto `j (decrement cm);
3. `i : if (cm > 0) then goto `j else goto `k (zero check cm);
4. `n: HALT (halting instruction).
A configuration (`, v1, v2) of a two-counter machine comprises an instruction ` and values
v1 and v2 of counters c1 and c2, respectively. The instruction of a configuration describes
ow the counter values are to be updated and what is the next instruction to be executed (for example, an instruction `8 : c2 := c2 + 1; goto `3 taken from configuration (`8, 6, 4)
x1=21c1 `i x1, x2≤ 1 B x2≤ 1, x1, x3< 1 C x2, x3≤ 1 `j D x2= 0 E x2= 0 F G H x1= 1 {x1} x2= 1, {x2} 0 < x1, x3< 1 x2= 1, {x2} 1 2 {x1} 1 2 {x2} x3= 1 {x3} x2= 1, {x2} x2= 0 1 2(x1+ x3) 1 −1 2(x1+ x3) x2= 0 1 −1 2(x1+ x3) 1 2(x1+ x3)
Figure 3: The cdPTA module for simulating an increment instruction for counter c1.
results in the configuration (`3, 6, 5)). A run of a two-counter machine consists of a finite or
infinite sequence of configurations, starting from configuration (`1, 0, 0), and where subsequent
configurations are successively generated by following the instruction specified in the associated configuration. A run is finite if and only if the final instruction visited along the run is `n
(the halting instruction). The halting problem for two-counter machines concerns determining whether the unique run of the two-counter machine is finite, and is undecidable [16]; hence the non-halting problem (determining whether the unique run of the two-counter machine is infinite) is also undecidable.
Consider a two-counter machine M. We reduce the non-halting problem for M to the maximal reachability problem of a cdPTA in the following way. We construct a cdPTA PM
with three clocks {x1, x2, x3} by considering modules for each form that the instructions of a
two-counter machine can take. On entry to each module, we have that x1 = 21c1, x2 = 21c2 and
x3 = 0. The module for simulating an increment instruction for c1 is shown in Figure 3. In
location `i, there is a delay of 1 −21c1, and hence the values of the clocks on entry to location
B are x1 = 0, x2 = 21c2 + 1 − 1
2c1 mod 1 and x3 = 1 − 21c1. A nondeterministic choice is then
made concerning the amount of time that elapses in location B: note that this amount must be in the interval (0,21c1). In order to correctly simulate the increment of counter c1, the choice
of delay in location B should be equal to 2c1+11 . On leaving location B, a probabilistic choice is made: the rightward outcome corresponds to continuing the simulation of the two-counter machine, whereas the downward outcome corresponds to checking that the delay in location B was correctly 2c1+11 . We write the delay in location B as 2c1+11 + , where −2c1+11 < < 2c1+11 : hence, for a correct simulation of the increment of c1, we require that = 0.
Consider the case in which the downward outcome (from the outgoing probabilistic edge of location B) is taken: then the cdPTA fragment from location D has the role of checking whether = 0. Note that, after entering location D, no time elapses in locations D and E (as enforced by the reset of x2 to zero and the invariant condition x2 = 0), and hence both clocks
x1 and x3 retain the same values as they had when location B was left. We show that the
probability of reaching the target location G from location D is 14 − 2, and hence equal to 1 4
if and only if = 0. To see that the probability of reaching G from D is 14 − 2, observe that
the probability is equal to 1
2(x1+ x3) = 1 2(
1
2c1+1 + + (1 − 2c1+11 ) + ) = 12 + multiplied by
1 −12(x1+ x3) = 12− , i.e., equal to 14− 2. Hence the probability of reaching location G from
location D is equal to 14 if and only if = 0 (otherwise, the probability is strictly less than 14). The module for simulating a decrement instruction for counter c1 is shown in Figure 4.
In a similar manner to the cdPTA fragment in Figure 3 for the simulation of an increment instruction, the only nondeterministic choice made is with regard to the amount of time spent
x1=21c1, x3= 0 `i x1, x3< 1 B x2≤ 1 `j C x1≤ 1 D x1= 0 E x1= 0 G F H x1= 1 1 2 {x1} 1 2 {x2} x3= 1 {x3} x2= 1, {x2} x1= 1 {x1} x1= 0 1 2(x2+ x3) 1 −1 2(x2+ x3) x1= 0 1 −12(x2+ x3) 1 2(x2+ x3)
Figure 4: The cdPTA module for simulating a decrement instruction for counter c1.
x1=21c1, x3= 0 `i x3= 0 x3= 0 `k `j x1= 1 x1< 1 1 2 1 2 1 2 1 2 1 4 3 4
Figure 5: The cdPTA module for simulating a zero-test instruction for counter c1.
in a location, in this case location `i. This amount of time is denoted by δ. For the correct
simulation of the decrement instruction, δ should equal 1 − 2c1−11 . The rightward outcome is taken from the probabilistic edge leaving location `i corresponds to the continuation of
the simulation of the two-counter machine: hence, on entry to location B, we have x1 = 0,
x2 = 21c2+ δ and x3 = δ; then, on entry to location `j, we have x1 = 1 − δ, x2 = 21c2 and x3 = 0.
Let δ = 1 − 2c1−11 + . For the correct simulation of the decrement instruction, we require that = 0. The downward outcome from the probabilistic edge leaving location `i corresponds
to checking that = 0, and takes a similar form to the analogous downward edge of the cdPTA fragment for the increment instruction, as shown in Figure 3. Note that, on entry to location C, we have that x1 = 1−21c1+, x2 = 0 and x3 = 1−2c1−11 +. Then, on entry to location D, we
have that x1 = 0, x2 = 21c1− and x3 = 1−21c1. As no time elapses in locations D and E, we have
that target location F is then reached with probability 12(x2+ x3) = 12(21c1− + 1 − 1 2c1) = 1 2+ 2
multiplied by the probability 1 −12(x2+ x3) = 21 −2, which equals 14 − 2
4. Hence we conclude
that the probability of reaching location F from location C is equal to 14 if = 0, and is strictly less than 14 otherwise.
Finally, the module for a zero test instruction `i : if (c1 > 0) then goto `j else goto `k
is shown in Figure 5. After entry to location `i, two probabilistic edges are enabled: the
upper one is taken if c1 = 0 (i.e., if x1 = 210 = 1), whereas the lower one is taken otherwise.
Both probabilistic edges involve an outcome leading to location `j or `k (depending on which
probabilistic edge was taken) with probability 12, leading to a target location with probability
1 2 ·
1
4, and leading to a sink, non-target location with probability 1 2 ·
3
4, in exactly the same
Given the construction of a cdPTA simulating the two-counter machine using the modules described above, we can now proceed to show Theorem 1. The reasoning is the same as that of Lemma 5 of [9]. First note that, in the module of the cdPTA for simulating an instruction of the two-counter machine, if the strategy of the cdPTA simulates correctly a single step of the two-counter machine, then a target location is reached with probability 1
2 · 1
4 (i.e., probability 1
2 for deciding to check the amount of time elapsed in a particular location multiplied by
probability 14 for the probability of reaching a target location when checking the amount of time elapsed, in both the increment and decrement modules, and probability 1
2 · 1
4 in the
zero-test module, regardless of the value of the tested counter). If the two-counter machine halts in k steps, and the strategy of the cdPTA correctly simulates the two-counter machine the probability of reaching a target location will be 1
2 · 1 4 + ( 1 2) 2 · 1 4 + ... + ( 1 2) k · 1 4 < 1 4. If
the two-counter machine halts in k steps, and the strategy of the cdPTA does not correctly simulate the two-counter machine, then this means that the probability of reaching a target location is strictly less than that corresponding to correct simulation, given that deviation from simulation of a certain step corresponds to reaching the target locations with probability strictly less than 14 in that step; hence the overall probability of reaching a target location will be strictly less than . 1
2 · 1 4 + ( 1 2) 2· 1 4 + ... + ( 1 2) k· 1 4 < 1
4. Now consider the case in which the
two-counter machine does not halt: in this case, faithful simulation in the cdPTA corresponds to reaching target locations with probability P∞
i=1( 1 2) i· 1 4 = 1
4, whereas unfaithful simulation
in the cdPTA corresponds to reaching the target locations with probabilityP∞
i=1( 1 2)
i· γ
i where
γi ≤ 14 for all i ∈ N and γj < 14 for at least one j ∈ N, and hence
P∞ i=1( 1 2) i· γ i < 14. Therefore
the two-counter machine does not halt if and only if there exists a strategy in the constructed cdPTA that reaches the target locations with probability at least 1
4, concluding the proof of
Theorem 1.
4
Approximation of Reachability Probabilities
We now consider the approximation of maximal and minimal reachability probabilities of cdPTA. Our approach is to utilise concepts from the corner-point abstraction [10]. Recall that the standard corner-point abstraction is a finite-state system that extends the classical region graph by encoding regions and corner points within its states; for example, the state (l, 0 < x < 1, x = 1) represents the situations in which the system is in location l, and the value of the clock x is in the interval (0, 1) and is “close” to 1. The corner-point abstraction can be used to obtain a quantitative measure that is arbitrarily close to the actual one; this is typical in the context of weighted (or priced) timed automata (see [17] for a survey). Instead, in the context of cdPTA, as indicated by Example 2 and the undecidability results presented in Section 3, such a construction cannot be used directly to obtain maximal or minimal reachability probabilities that are arbitrarily close to those of the cdPTA under consideration. Hence we present a method that conservatively approximates maximal and minimal reachability probabilities (i.e., the computed maximal probability bounds the actual maximal probability from above, and the computed minimal probability bounds the actual minimal probability from below), and show that successive refinement of regions leads to finite-state systems that approximate the actual maximal and minimal probabilities at least as accurately. The states of our finite-state system correspond to location-region pairs, rather than to location-region-corner point triples as in the standard corner-point abstraction, and we use corners of regions only to define available distributions.
First we define regions and corner points. Let P = (L, ¯l, X , inv , prob) be a cdPTA, which we assume to be fixed throughout this section, and let M ∈ N denote the upper bound on clocks in P. We choose k ∈ N, which we will refer to as the (time) granularity, and let
[k] = {kc : c ∈ N} be the set of multiples of 1k. A k-region (h, [X0, ..., Xn]) over X comprises:
1. a function h : X → ([k] ∩ [0, M ]) assigning a multiple of 1k no greater than M to each clock and
2. a partition [X0, ..., Xn] of X , where Xi 6= ∅ for all 1 ≤ i ≤ n and h(x) = M implies
x ∈ X0 for all x ∈ X .
Given clock valuation v ∈ RX≥0 such that v(x) ≤ M for all x ∈ X , and granularity k, the
k-region R = (h, [X0, ..., Xn]) containing v, written v ∈ R, satisfies the following conditions:
1. bk · v(x)c=k · h(x) for all clocks x ∈ X ;
2. v(x)=h(x) for all clocks x ∈ X0;
3. k · v(x) − bk · v(x)c ≤ k · v(y) − bk · v(y)c if and only if x ∈ Xi and y ∈ Xj with i ≤ j,
for all clocks x, y ∈ X .
Note that, rather than considering regions delimited by valuations corresponding to natural numbers, in our definition regions are delimited by valuations corresponding to multiples of
1
k. We use Regsk to denote the set of k-regions. For R, R0 ∈ Regsk and clock constraint
ψ ∈ CC (X ), we say that R0 is a ψ-satisfying time successor of R if, for all v ∈ R, there exists δ ∈ R≥0, such that (v+δ) ∈ R0 and (v+δ0) |= ψ for all 0 ≤ δ0 ≤ δ. We write R |= ψ if all
valuations v ∈ R are such that v |= ψ (note that the definition of k-regions implies that either v |= ψ for all v ∈ R or v 6|= ψ for all v ∈ R). For a given k-region R ∈ Regsk, we let R[X := 0] be the k-region that corresponds to resetting clocks in X to 0 from clock valuations in R (that is, R[X := 0] contains valuations v[X := 0] for v ∈ R). We use R0 to denote the k-region that
contains the valuation 0.
A corner point α = haii0≤i≤n∈ ([k] ∩ [0, M ])n of k-region (h, [X0, ..., Xn]) is defined by:
ai(x) =
h(x) if x ∈ Xj with j ≤ i
h(x) + k1 if x ∈ Xj with j > i .
Note that a k-region (h, [X0, ..., Xn]) is associated with n + 1 corner points. Let CP(R) be the
set of corner points of k-region R. Given granularity k, we let CornerPointsk be the set of all
corner points of k-regions.
Next we define the clock-dependent region graph with granularity k as the finite-state PTS Ak= (Sk, s, Actk, Γk), where Sk = L × Regsk, s = (¯l, R0), Actk = {τ } ∪ (CornerPointsk× prob),
and Γk =
− →
Γk∪ cΓk where
−→
Γk ⊆ Sk× {τ } × Dist(Sk) and cΓk ⊆ Sk× CornerPointsk× prob × Dist(Sk)
are such that:
• −Γ→k is the smallest set of transitions such that ((l, R), τ, {(l, R0) 7→ 1}) ∈
−→
Γk if (l, R0) is
an inv (l)-satisfying time successor of (l, R);
• cΓk is the smallest set such that ((l, R), (α, (l, g, p)), ν) ∈ cΓk if:
1. R |= g; 2. α ∈ CP(R);
3. for any (l0, R0) ∈ Sk, we have that ν(l0, R0) =
P
X∈Reset(R,R0)p[α](X, l0), where
(A, x = 0, x = 0) (A, 0 < x < 1, x = 0) (A, 0 < x < 1, x = 1) (B, 0 < x < 1, x = 0) (E, 0 < x < 1, x = 0) (B, 0 < x < 1, x = 1) (E, 0 < x < 1, x = 1) (C, 0 < x < 1, x = 1) (E, 0 < x < 1, x = 1) τ τ 0 1 1 0 0 1
Figure 6: A finite-state PTS showing that a direct approach encoding corner points in states does not lead to a conservative overapproximation of the cdPTA with regard to reachability probabilities. (A, x = 0) (A, 0 < x < 1) (B, 0 < x < 1) (E, 0 < x < 1) (C, 0 < x < 1) (E, 0 < x < 1) (D, 0 < x < 1) (E, 0 < x < 1) τ 0 1 1 0 1 0 0 1 1 0 0 1
Figure 7: The clock-dependent region graph of Example 2 for k = 1.
Hence the clock-dependent region graph of a cdPTA encodes corner points within (probabilistic-edge-based) transitions, in contrast to the corner-point abstraction, which en-codes corner points within states. In fact, a literal application of the standard corner-point abstraction, as presented in [17], does not result in a conservative approximation, which we now explain with reference to Example 2.
Example 3. Recall that the states of the corner-point abstraction comprise a location, a region and a corner point of the region, and each transition maintains consistency between the corner points of the transition’s source and target states. For example, for the cdPTA of Figure 2, consider the state (A, 0 < x < 1, x = 1), where 0 < x < 1 is used to refer to the state’s region component and x = 1 is used to refer to the state’s corner point. Then the probabilistic edge leaving location A is enabled (because the state represents the situation in which clock x is in the interval (0, 1) and arbitrarily close to 1). Standard intuition on the corner-point abstraction (adapted from weights in [17] to probabilities in distribution templates in this paper) specifies that, when considering probabilities of outgoing probabilistic edges, the state (A, 0 < x < 1, x = 1) should be associated with probabilities corresponding to the valuation for which x = 1. Hence the probability of making a transition to location B is 1, and the target corner-point-abstraction state is (B, 0 < x < 1, x = 1). However, now consider the probabilistic edge leaving location B: in this case, given that the corner point under consideration is x = 1, the probability of making a transition to location C is 0, and hence the target location D is reachable with probability 0. Furthermore, consider the state (A, 0 < x < 1, x = 0): in this case, if the probabilistic edge leaving location A is taken, then location B is reached with probability 0, and hence location D is again reachable with
probability 0. Following this approach of encoding corner points within states, we obtain the finite-state PTS in Figure 6. For emphasis, we show (with dashed lines) transitions that correspond to probability 0; vice versa, for simplicity we do not show transitions from states reached with probability 0 or from the location E, and duplicate the state (E, 0 < x < 1, x = 1). We can conclude that such a direct application of the corner-point abstraction to cdPTA is not a conservative approximation of the cdPTA, because the maximum probability of reaching location D in the corner-point abstraction is 0, i.e., less than the maximum probability of reaching location D in the cdPTA (which we recall is 1 −
√ 3 3 ).
Instead, in our definition of the clock-dependent region graph, we allow “inconsistent” corner points to be used in successive transitions: for example, from location A, the outgoing probabilistic edge can be taken using the value of x corresponding to the corner point x = 1; then, from locations B and C, the outgoing probabilistic edge can be taken using corner point x = 0. This approach, with k = 1, yields the finite-state PTS shown in Figure 7; as above, we show transitions with probability 0 with dashed lines, and for simplicity duplicate the state (E, 0 < x < 1) and omit self-loops labelled with τ . The distributions depicted in the top part of the figure correspond to the corner point with x = 0, whereas the distributions of the bottom part correspond to the corner point with x = 1. It can be observed that the maximum probability of reaching the target location D in this clock-dependent region graph is 1 (i.e., greater than 1 −
√ 3
3 , as required by a conservative approximation approach).
Analogously to the case of cdPTA strategies, we consider strategies of clock-dependent region graphs that alternate between transitions from −→Γk (time elapse transitions) and
transi-tions from cΓk (probabilistic edge transitions). Formally, a region graph strategy π is a strategy
of Aksuch that, for a finite run r ∈ FinRunsAk that has (l, R) a,ν
−→ (l0, R0) as its final transition,
either ((l, R), a, ν) ∈−Γ→k and support(π(r)) ⊆ cΓk, or ((l, R), a, ν) ∈ cΓk and support(π(r)) ⊆
−→ Γk.
We write Πk for the set of region graph strategies of Ak.
Let F ⊆ L be a set of target locations, which we assume to be fixed in the following. Recall that SF = {(l, v) ∈ L × RX≥0 : l ∈ F } and let RegsFk = {(l, R) ∈ Sk: l ∈ F }. The remainder of
this section is dedicated to showing that clock-dependent region graphs can be used to provide a technique for approximating maximal and minimum probability for reaching target locations. We first show in Proposition 2 that, for any k ≥ 1, the maximum (minimum) probability for reaching target locations from the initial state of a cdPTA is bounded from above (from below, respectively) by the corresponding maximum (minimum, respectively) probability in the clock-dependent region graph with granularity k. Then we show in Proposition 3 that, similarly, the maximum (minimum) probability computed in the clock-dependent region graph of granularity k is an upper (lower, respectively) bound on the maximum (minimum, respectively) probability computed in the clock-dependent region graph of granularity 2k.
4.1
Approximating a cdPTA with a clock-dependent region graph
In this subsection, we show that we can use Ak, the clock-dependent region graph with
granu-larity k, to approximate the cdPTA P. In order to show the required result, we first consider the following intermediate lemmata.
The first lemma specifies that the sets of clocks that, when reset to 0, are used to transform valuation v to valuation v0 are the same as the sets of clocks used to transform the k-region containing v to the k-region containing the valuation v0.
Lemma 1. Let k ∈ N and v, v0 ∈ RX
≥0 such that, for each clock x ∈ X , either v0(x) = v(x) or
v0(x) = 0. Using R, R0 ∈ Regsk to denote the k-regions such that v ∈ R and v0 ∈ R0, we have
Proof. Let Xv0 be the set of clocks that are equal to 0 in v, and let Xv00 be the set of clocks that
are equal to 0 in v0. Similarly, let X0
R be the set of clocks that are equal to 0 in all valuations in
R, and let X0
R0 be the set of clocks that are equal to 0 in all valuations in R0. By the definition
of k-regions, for any clock x ∈ X , we have v(x) = 0 if and only if v00(x) = 0 for all v00 ∈ R, and v0(x) = 0 if and only if v00(x) = 0 for all v00 ∈ R0. Hence X0
v = XR0 and Xv00 = XR00. Given
that either v0(x) = v(x) or v0(x) = 0 for each x ∈ X , we have that X ∈ Reset(v, v0) if and only if Xv00 \ Xv0 ⊆ X ⊆ Xv00. Similarly, X ∈ Reset(R, R0) if and only if XR00 \ XR0 ⊆ X ⊆ XR00.
Therefore we have that X ∈ Reset(v, v0) if and only if X0
v0 \ Xv0 ⊆ X ⊆ Xv00 if and only if
X0
R0\ XR0 ⊆ X ⊆ XR00 if and only if X ∈ Reset(R, R0). Hence Reset(v, v0) = Reset(R, R0).
Recall that we denote a set of weights by a finite set {θi}i∈I, where θi ∈ (0, 1] for each i ∈ I
and P
i∈Iθi = 1. In the following, we use an interpretation of valuations and corner points
as points in R|X |≥0-space, allowing the use of operations such as θ · v and v + v 0
(interpreted as (θ · v)(x) = θ · v(x) and (v + v0)(x) = v(x) + v0(x) for all clocks x ∈ X , respectively).
Lemma 2. Let v ∈ RX≥0, let k ∈ N and let R ∈ Regsk be the unique k-region such that v ∈ R.
Then there exists a set of weights {θα}α∈CP(R) such that v =Pα∈CP(R)θα· α.
Proof. Observe that the convex hull of corner points CP(R) corresponds to a superset of the valuations contained in R. Hence, given that v ∈ R, we have that v is in the set of valuations induced by the convex hull of CP(R), and hence there exists {θα}α∈CP(R) with the required
property.
In the following, for a state (l, v) ∈ S of [[P]], we use h[l, v]ik to denote the unique pair
(l0, R) ∈ L × Regsk such that l = l0 and v ∈ R.
Lemma 3. Let (l, v) ∈ S be a state, let k ∈ N, let R ∈ Regsk be the k-region such that v ∈ R,
and let (l, g, p) ∈ prob be a probabilistic edge such that v |= g. Then there exists a set of weights {θα}α∈CP(R) such that, for any (X, l0) ∈ 2X × L:
p[v](X, l0) = X
α∈CP(R)
θα· p[α](X, l0) .
Proof. Let {θα}α∈CP(R) be the set of weights such that v =
P
α∈CP(R)θα · α, which exists by
Lemma 2. Let e = (X, l0) ∈ 2X × L. Then we have: p[v](e) = X x∈X fxp,e(v(x)) = X x∈X (cp,ex + dp,ex · v(x)) = X x∈X (cp,ex + dp,ex · X α∈CP(R) θα· α(x)) = X α∈CP(R) θα X x∈X cp,ex + X α∈CP(R) θα X x∈X dp,ex · α(x) (from X α∈CP(R) θα = 1) = X α∈CP(R) θα( X x∈X cp,ex +X x∈X dp,ex · α(x)) . Recall that Ip
x has natural-numbered endpoints, and that α(x) is a rational number. Note
that Ixp may not include α(x) in the case that Ixp is open or half-open. Given that fxp,e is a continuous function, we have that fp,e
(a) · · · l x, y < 1 lt lb · · · · · · x+y 2 1 −x+y2 (b) y x 1 1 1 2 2 3 v α00 α10 α11 (c) y x 1 1 1 2 1 2 α α00 α10 α11
Figure 8: (a) The cdPTA fragment of Example 4. (b) 1-region for x, y ∈ (0, 1) and y < x, and valuation v with v(x) = 23 and v(y) = 12. (c) 1-region for x, y ∈ (0, 1) and y < x, and 2-regions contained within the 1-region.
that α(x) must belong to the closure of Ixp, we conclude the following:
X α∈CP(R) θα( X x∈X cp,ex +X x∈X dp,ex · α(x)) = X α∈CP(R) θα X x∈X fxp,e(α(x)) = X α∈CP(R) θα· p[α](e) .
Hence we have shown that p[v](e) =P
α∈CP(R)θα· p[α](e), which concludes the proof.
Example 4. We illustrate Lemma 2 and Lemma 3 with regard to the cdPTA fragment shown in Figure 8(a), where the cdPTA has two clocks, x and y. Consider the state (l, v), i.e., the state for which the cdPTA is in location l with valuation v, where v(x) = 23 and v(y) = 12. The valuation v and the unique 1-region (which is characterised by x, y ∈ (0, 1) and y < x) containing v are shown in Figure 8(b). The corner points of the 1-region are α00, α10 and
α11, where α00(x) = α00(y) = 0, α10(x) = 1 and α10(y) = 0, and α11(x) = α11(y) = 1. Now
consider Lemma 2. The weights θα00 = 13, θα10 = 16, and θα11 = 12 correspond to v, from the
following reasoning: (θα00 · α00+ θα10 · α10+ θα11 · α11)(x) = θα00· α00(x) + θα10 · α10(x) + θα11· α11(x) = 13 · 0 + 1 6 · 1 + 1 2 · 1 = 2 3 = v(x) ,
(θα00 · α00+ θα10 · α10+ θα11 · α11)(y) = θα00· α00(y) + θα10· α10(y) + θα11 · α11(y)
= 13 · 0 + 1 6 · 0 + 1 2 · 1 = 1 2 = v(y) .
Next, we consider Lemma 3, and use p to denote the probabilistic edge from location l. First note that p[v](∅, lt) = 12·(v(x)+v(y)) = 12·(23+21) = 127, and p[v](∅, lb) = 1−12·(v(x)+v(y)) = 125.
Now considering the corner points, we have:
p[α00](∅, lt) = 12 · (α00(x) + α00(y)) = 12 · (0 + 0) = 0 , p[α00](∅, lb) = 1 − 12 · (α00(x) + α00(y)) = 1 −12 · (0 + 0) = 1 , p[α10](∅, lt) = 12 · (α10(x) + α10(y)) = 12 · (1 + 0) = 12 , p[α10](∅, lb) = 1 − 12 · (α10(x) + α10(y)) = 1 −12 · (1 + 0) = 12 , p[α11](∅, lt) = 12 · (α11(x) + α11(y)) = 12 · (1 + 1) = 1 , p[α11](∅, lb) = 1 − 12 · (α11(x) + α11(y)) = 1 −12 · (1 + 1) = 0 .
We conclude Example 4 by observing that the equality of Lemma 3 holds: P α∈CP(h[l,v]i1)θα· p[α](∅, lt) = θα00· p[α00](∅, lt) + θα10 · p[α10](∅, lt) + θα11 · p[α11](∅, lt) = 13 · 0 + 1 6 · 1 2 + 1 2 · 1 = 127 = p[v](∅, lt) , P α∈CP(h[l,v]i1)θα· p[α](∅, lb) = θα00· p[α00](∅, lb) + θα10 · p[α10](∅, lb) + θα11 · p[α11](∅, lb) = 13 · 1 + 1 6 · 1 2 + 1 2 · 0 = 125 = p[v](∅, lb) .
We now use the previous three lemmata to show that, from a state (l, v) of the semantics of a cdPTA, a distribution derived from a particular probabilistic edge can be obtained as a weighted sum of distributions, derived from the same probabilistic edge, available at the corner points of the k-region containing (l, v).
Lemma 4. Let (l, v) ∈ S be a state, let k ∈ N, and let R ∈ Regsk be the k-region such
that v ∈ R. For each transition ((l, v), (l, g, p), µ) ∈ b∆ of [[P]], there exists a set of transitions {(h[l, v]ik, (α, (l, g, p)), να)}α∈CP(R) ⊆ cΓk of Ak and weights {θα}α∈CP(R) such that, for each state
(l0, v0) ∈ S:
µ(l0, v0) = X
α∈CP(R)
θα· να(h[l0, v0]ik) .
Proof. Let {θα}α∈CP(R) be the set of weights such that v = Pα∈CP(R)θα · α, which exists by
Lemma 2, and let R, R0 ∈ Regsk be the k-regions such that v ∈ R and v0 ∈ R0. By definition
of [[P]], we have: µ(l0, v0) = X X∈Reset(v,v0) p[v](X, l0) = X X∈Reset(v,v0) X α∈CP(R) θα· p[α](X, l0) (by Lemma 3) = X X∈Reset(R,R0) X α∈CP(R) θα· p[α](X, l0) (by Lemma 1) = X α∈CP(R) θα X X∈Reset(R,R0) p[α](X, l0) = X α∈CP(R) θα· νi(h[l0, v0]ik) .
The next lemma specifies that any time elapse transition of [[P]] can be mimicked by a transition of Ak.
Lemma 5. Let (l, v) ∈ S be a state, and let k ∈ N. For each transition ((l, v), δ, {(l, v + δ) 7→ 1}) ∈−→∆ of [[P]], there exists a transition (h[l, v]ik, τ, {h[l, v + δ]ik 7→ 1}) ∈
−→
Γk of Ak.
Proof. The lemma follows directly from the definition of −Γ→k and of inv (l)-satisfying time
successors.
The following lemma specifies that, for any transition of [[P]], any two distinct states within its distribution’s support set have valuations belonging to different k-regions.
Lemma 6. Let (l, v) ∈ S be a state, let k ∈ N, and let ((l, v), (l, g, p), µ) ∈ b∆ be a transition of [[P]]. For each pair (l1, v1), (l2, v2) ∈ support(µ) such that (l1, v1) 6= (l2, v2), we have h[l1, v1]ik 6=
h[l2, v2]ik.
Proof. Let (l1, v1), (l2, v2) ∈ support(µ) such that (l1, v1) 6= (l2, v2). First observe that if l1 6= l2
then trivially h[l1, v1]ik 6= h[l2, v2]ik. Now consider the case in which l1 = l2 and v1 6= v2. Note
that the definition of [[P]] specifies that v1 = v[X1 := 0] and v2 = v[X2 := 0] for some clock
sets X1, X2 ⊆ X such that X1 6= X2. Hence v1 and v2 differ only in terms of which clocks
are equal to 0. Intuitively, by the definition of k-regions, any two valuations that differ only in terms of which clocks are equal to 0 belong to different k-regions. For completeness, we now explain this formally. Denote the sets of clocks that are equal to 0 in v1 by X10 and in v2
by X20 (note that X1 ⊆ X10, X2 ⊆ X20 and that X 0 1 6= X
0
2 because v1 6= v2). Let the k-region
component of h[l1, v1]ikbe denoted by (h1, [X1,0, X1,1, ..., X1,n1]) and let the k-region component
of h[l2, v2]ik be denoted by (h2, [X2,0, X2,1, ..., X2,n2]). Given that X10 6= X20, either there exists
clock x ∈ X10 \ X0
2 such that h1(x) = 0 and x ∈ X1,0 but either h2(x) 6= 0 or x 6∈ X2,0, or there
exists clock x ∈ X20 \ X0
1 such that h2(x) = 0 and x ∈ X2,0 but either h1(x) 6= 0 or x 6∈ X1,0.
Hence we have either h1 6= h2 or X1,0 6= X2,0, and therefore h[l1, v1]ik6= h[l2, v2]ik.
Lemma 6 specifies that, for each transition ((l, v), a, µ) ∈ ∆ of [[P]] and for each (l0, R) ∈ Sk,
there exists at most one valuation v0 ∈ R such that (l0, v0) ∈ support(µ). If such a valuation v0
exists, we set vµ,(l0,R) = v0, otherwise vµ,(l0,R) can be set to an arbitrary valuation. From this
fact, together with Lemma 4 and Lemma 5, we obtain the following lemma.
Lemma 7. Let (l, v) ∈ S be a state, and let k ∈ N. For each transition ((l, v), a, µ) ∈ ∆ of [[P]], there exists a combined transition ({(h[l, v]ik, ai, νi)}i∈I, {λi}i∈I) of Ak such that, for each
(l0, R0) ∈ Sk, we have: 1. µ(l0, vµ,(l0,R0)) =P i∈Iλi· νi(l 0, R0); 2. P v0∈R0µ(l0, v0) = P i∈Iλi· νi(l0, R0).
Proof. We first consider part (1). Let R ∈ Regsk be the unique region such that v ∈ R. We consider the following two cases.
Case a ∈ prob. Let p = a. By Lemma 4, there exist {((l, R), (α, p), να)}α∈CP(R) ⊆ cΓk of Ak
and weights {θα}α∈CP(R) such that µ(l0, vµ,(l0,R0)) = P
α∈CP(R)θα· να(h[l0, vµ,(l0,R0)]ik). Hence we
let I = CP(R) and λα = θα for each α ∈ CP(R), concluding that µ(l0, vµ,(l0,R0)) = P
α∈CP(R)θα·
να(l0, R0) =
P
i∈Iλi· νi(l0, R0).
Case a ∈ R≥0. Let δ = a. Note that, by definition of [[P]], for the unique (l0, R0) ∈ Sk such
that l = l0and v+δ ∈ R0, we must have vµ,(l0,R0) = v+δ, i.e., µ(l0, vµ,(l0,R0)) = µ(l0, v+δ) = 1. By
Lemma 5, there exists ((l, R), τ, {h[l, v + δ]ik 7→ 1}) ∈
−→
Γk: hence we let |I| = 1 and let {λi}i∈I
be the set containing a single weight equal to 1. Then we conclude that µ(l0, vµ,(l0,R0)) =
µ(l0, v + δ) = 1 = {h[l, v + δ]ik7→ 1}(h[l, v + δ]ik) =
P
i∈Iλi· νi(l0, R0).
Part (2) of the lemma then follows from part (1) and Lemma 6, which establishes that P
v00∈R0µ(l0, v00) = µ(l0, vµ,(l0,R0)) for (l0, R0) ∈ Sk such that there exists a valuation v0 ∈ R0 with
(l0, v0) ∈ support(µ).
Consider equivalence ≡⊆ (S ] Sk)2 over the states of the disjoint union of [[P]] and Ak
defined as the smallest equivalence satisfying the following conditions:
• for states (l, v), (l0, v0) ∈ S, we have (l, v) ≡ (l0, v0) if h[l, v]i
k = h[l0, v0]ik (i.e., l = l0, and v
• for (l, v) ∈ S, (l0, R) ∈ S
k, we have (l, v) ≡ (l0, R) if h[l, v]ik = (l0, R) (i.e., l = l0 and v
belongs to R).
Then the following corollary is a direct consequence of part (2) of Lemma 7.
Corollary 1. Let (l, v) ∈ S be a state, and let k ∈ N. For each transition ((l, v), a, µ) ∈ ∆ of [[P]], there exists a combined transition ({(h[l, v]ik, ai, νi)}i∈I, {λi}i∈I) of Ak such that µ ≡
L
i∈Iλi · νi and either ai = τ for all i ∈ I if a ∈ R≥0, and {ai}i∈I ⊆ CornerPointsk× prob
otherwise.
We now state the main result of this section.
Proposition 2. Let k ∈ N. Then: Pmax[[P]],Σ(SF) ≤ PmaxAk,Πk(Regs
F
k), and Pmin[[P]],Σ(SF) ≥ PminAk,Πk(Regs F k) .
Proof. Consider ⊆ (S ] Sk)2 such that is the smallest relation satisfying the following
property: for (l, v) ∈ S, (l0, R) ∈ Sk, we have (l, v) (l0, R) if h[l, v]ik = (l0, R). By Corollary 1,
is a probabilistic simulation respecting ≡ and {τ } ∪ R≥0. Then, by Proposition 1, we
have that Pmax
[[P]],ΣR≥0(SF) ≤ P max Ak,Σ{τ }(Regs F k) and Pmin[[P]],ΣR≥0(SF) ≥ P min Ak,Σ{τ }(Regs F k). Noting that
Σ = ΣR≥0 and Πk = Σ{τ }, we have that Pmax[[P]],Σ(SF) ≤ PmaxAk,Πk(Regs F
k) and Pmin[[P]],Σ(SF) ≥
PminAk,Πk(Regs F k).
4.2
Approximating a clock-dependent region graph with
granular-ity 2k with a clock-dependent region graph with granulargranular-ity
k
In this subsection, we show that Ak, the clock-dependent region graph with granularity k
approximates A2k, the clock-dependent region graph with granularity 2k. The results of this
subsection can be adapted to hold for granularity ck rather than 2k, for any c ∈ N \ {0, 1}: we consider only the case of c = 2 for simplicity. Before presenting the main result on approximating the case of granularity 2k by that of granularity k, we consider a number of intermediate lemmata, which have similarities with the intermediate lemmata presented in Section 4.1.
For 2k-region R ∈ Regs2k and k-region R0 ∈ Regsk, we write R ⊆ R0 if every valuation that is contained in R is also contained in R0 (i.e., if {v ∈ RX≥0 : v ∈ R} ⊆ {v ∈ RX≥0 : v ∈ R0}). Note that, for a given 2k-region R ∈ Regs2k there is exactly one k-region R0 ∈ Regsksuch that R ⊆ R0. In the following, given the 2k-region R, we use [R]k to denote the unique k-region
such that R ⊆ [R]k. We now adapt Lemma 1 to the case of 2k-regions and k-regions: that is,
the sets of clocks that, when reset to 0, are used to transform 2k-region R to 2k-region R0 are the same as the sets of clocks used to transform the k-region containing the 2k-region R to the k-region containing the 2k-region R0. The proof of the lemma proceeds in an analogous manner to that of Lemma 1, and is therefore omitted.
Lemma 8. Let k ∈ N and let R2k, R02k ∈ Regs2k such that R02k = R2k[X := 0] for some X ⊆ X .
Using Rk, R0k ∈ Regsk to denote the unique k-regions such that R2k ⊆ Rk and R02k ⊆ R0k, we
have Reset(R2k, R02k) = Reset(Rk, R0k).
The following result specifies that every corner point of R ∈ Regs2k is either a corner point of [R]k or can be obtained from a weighted combination of corner points of [R]k.
Lemma 9. Let k ∈ N and let R ∈ Regs2k. For each corner point α ∈ CP(R), there exist a set
of weights {θα0}α0∈CP([R]k) such that α =P
Proof. Note that the convex hull of corner points in CP([R]k) is a superset of the convex hull
of corner points in CP(R). Hence, any corner point α ∈ CP(R) is in the set of valuations induced by the convex hull of CP([R]k), and hence there exists the required {θα0}α0∈CP([R]k)
such that α =P
α0∈CP([R]k)θα0 · α0.
We note that the corner points of R ∈ Regs2k are either also corner points of the unique R0 ∈ Regsk such that R ⊆ R0, or they are mid-points of edges of the polyhedron induced by the convex hull of the corner points of R0.
Lemma 9 allows us to state the following lemma (which is an analogue of Lemma 3).
Lemma 10. Let k ∈ N, let R ∈ Regs2k, let (l, g, p) ∈ prob be a probabilistic edge such
that R |= g, and let α ∈ CP(R) be a corner point of R. Then there exists a set of weights {θα0}α0∈CP([R]k) such that, for any (X, l0) ∈ 2X × L, we have:
p[α](X, l0) = X
α0∈CP([R]k)
θα0 · p[α0](X, l0) .
Proof. By Lemma 9, it is possible that α ∈ CP([R]k), in which case we let θα = 1 and trivially
we have:
p[α](X, l0) = θα· p[α](X, l0) =
X
α0∈CP([R]k)
θα0 · p[α0](X, l0) .
Now consider the case in which α 6∈ CP([R]k). We proceed in a similar manner to the proof
of Lemma 3. By Lemma 9, we have the existence of a set of weights {θα0}α0∈CP([R]k) such that
α =P
α0∈CP([R]k)θα0· α0. Let e = (X, l0) ∈ 2X × L. Then we have:
p[α](e) = X x∈X fxp,e(α(x)) = X x∈X (cp,ex + dp,ex · α(x)) = X x∈X (cp,ex + dp,ex · X α0∈CP([R]k) θα0 · α0(x)) = X α0∈CP([R]k) θα0 X x∈X cp,ex + X α0∈CP([R]k) θα0 X x∈X dp,ex · α0(x) = X α0∈CP([R]k) θα0( X x∈X cp,ex +X x∈X dp,ex · α0(x)) = X α0∈CP([R]k) θα0 X x∈X fxp,e(α0(x)) = X α0∈CP([R]k) θα0 · p[α0](e)
(where the fourth equation follows from P
α0∈CP([R]k)θα0 = 1, and the penultimate equation
follows from the fact that fxp,e is a continuous function, as in the proof of Lemma 3), which concludes the proof.
Example 5. Recall the cdPTA example of Figure 8(a). In Figure 8(c), we show the 1-region corresponding to x, y ∈ (0, 1) and y < x, together with the 2-regions contained within this 1-region. Consider Lemma 9, and recall this lemma specifies that the corner points of a 2-region are either corner points of the 1-2-region that it is contained within, or are equal to the weighted combination of corner points of that 1-region. As an example, take the corner point
