=Paper=
{{Paper
|id=None
|storemode=property
|title=On Existence of Global-in-Time Trajectories of Non-deterministic Markovian Systems
|pdfUrl=https://ceur-ws.org/Vol-848/ICTERI-2012-CEUR-WS-SMSV-paper-4-p-312-320.pdf
|volume=Vol-848
|dblpUrl=https://dblp.org/rec/conf/icteri/Ivanov12
}}
==On Existence of Global-in-Time Trajectories of Non-deterministic Markovian Systems==
https://ceur-ws.org/Vol-848/ICTERI-2012-CEUR-WS-SMSV-paper-4-p-312-320.pdf
On Existence of Global-in-Time Trajectories of
Non-deterministic Markovian Systems
Ievgen Ivanov1,2
1
Taras Shevchenko National University of Kyiv, Ukraine
2
Paul Sabatier University, Toulouse, France
ivanov.eugen@gmail.com
Abstract. We consider the following question: given a continuous-time
non-deterministic (not necessarily time-invariant) dynamical system, is it
true that for each initial condition there exists a global-in-time trajectory.
We study this question for a large class of systems, namely the class of
complete non-deterministic Markovian systems. We show that for this
class of systems, the question can be answered using analysis of existence
of locally defined trajectories in a neighborhood of each time.
Keywords. dynamical systems, non-deterministic systems, Markovian
systems, global-in-time trajectories
Key Terms. Mathematical Model, Specification Process, Verification
Process
1 Introduction
In this paper we consider the following question: given a continuous-time non-
deterministic (not necessarily time-invariant) dynamical system Σ, is it true
that for any time moment t0 and initial state x0 there exists a global-in-time
trajectory t 7→ s(t) such that s(t0 ) = x0 .
Some related problems, e.g. global existence of solutions of initial value prob-
lems for various classes of differential equations [2, 3, 7] and inclusions [4–6], ex-
istence of non-Zeno global-in-time executions of hybrid automata [8–10] are well
known. However, they have mostly been studied in the context of determinis-
tic systems (differential equations with unique solutions, deterministic hybrid
automata, etc.). Differential inclusions [5] are in principle non-deterministic sys-
tems, but for them a more common question is whether any (instead of some)
solution for each initial condition exists into future [4, 6].
For deterministic systems the existence of a global trajectory for each initial
condition implies that each partial trajectory (e.g. defined on a proper open in-
terval of the real time scale) can be extended to a global trajectory. But this is
not necessary for non-deterministic systems. For example, for each initial condi-
tion x(t0 ) = x0 the differential inclusion dx 2
dt ∈ [0, x ] has both a globally defined
On Existence of Global-in-Time Trajectories ... 313
constant trajectory x(t) = x0 and a trajectory of the equation dx 2
dt = x which
escapes to infinity in finite time. Thus it is not true that any (locally defined)
solution extends infinitely into future.
We will study our existence question for a large class of systems, namely the
class of complete non-deterministic Markovian systems. We will show that for
this class of systems, the question can be answered using analysis of existence
of locally defined trajectories in a neighborhood of each time.
Note that in this paper we use the term Markovian in the context of purely
non-deterministic (i.e. non-stochastic) systems. The formal definition will be
given below. Also note that many well-known classes of continuous-time systems
either belong to this class of can be represented by systems of this class. We will
give examples later in the paper.
2 Non-deterministic Complete Markovian Systems
The notions of a Markov process or system [12] are usually defined and studied in
the context of probability theory. However, they also make sense in a purely non-
deterministic setting, where no quantitative information is attached to events
(trajectories, transitions, etc.), i.e. each event is either possible or impossible.
General definitions of continuous-time Markovian systems of such kind have
appeared in the literature [1]. They give a large class of (not necessarily deter-
ministic) systems which can have both continuous and discontinuous (jump-like)
trajectories. Essentially, the notion of a non-deterministic Markovian system cap-
tures the idea that only the system’s current state (but not its past) determines
the set of its possible futures.
Below we define the notion of a non-deterministic (complete) Markovian
system in spirit of, but not exactly as in [1]. The main reasons for this are that
we would like to include non-time-invariant systems in the definition and focus
on partial trajectories, i.e. trajectories defined on a subset of the time scale.
We will use the following notation: N = {1, 2, 3, ...}, N0 = N ∪ {0}, f : A → B
is a total function from A to B, f : A→B ˜ is a partial function from A to B,
f |X is the restriction of a function f to a set X, 2A is the power set of a set A.
The notation f (x) ↓ (f (x) ↑) means that f (x) is defined (resp. undefined) on
the argument x, dom(f ) = {x | f (x) ↓}. Also, ¬, ∨, ∧, ⇒, ⇔ denote the logical
operations of negation, disjunction, conjunction, implication and equivalence
correspondingly. Let us denote:
– T = [0, +∞) is the (real) time scale. We assume that T is equipped with a
topology induced by the standard topology on R
– T is the set of all connected subsets of T with cardinality greater than one.
For the purpose of this paper, we will use the following definition of a dy-
namical system on the time scale T .
Definition 1. A dynamical system on T is as an abstract object M (a mathe-
matical model; in applications this may be an equation, inclusion, switched sys-
tem, etc.) together with the associated time scale T (this scale will be the same
314 Ie. Ivanov
throughout the paper), the set of states Q, and the set of (partial) trajectories T r.
A trajectory is a function s : A → Q, where A ∈ T (note that trivial trajectories
defined on singleton or empty time sets are excluded). The set T r satisfies the
property: if s : A → Q ∈ T r, B ∈ T, and B ⊆ A, then s|B ∈ T r. We will refer
to this property as ”Tr is closed under proper restrictions (CPR)”.
We will say that a trajectory s1 ∈ T r is a subtrajectory of s2 ∈ T r (denoted
as s1 v s2 ), if s1 = s2 |A for some A ∈ T. The trajectories s1 and s2 are
incomparable, if s1 is not a subtrajectory of s2 and vice versa.
According to the definition given above, for a time t0 ∈ T and q0 ∈ Q there
may exist multiple incomparable trajectories s such that s(t0 ) = q0 (as well as
one or none). In this sense a dynamical system can be non-deterministic.
It is easy to see that (T r, v) is a partially ordered set (poset).
Definition 2. A set T r (which is CPR) is
– complete, if (T r, v) is a chain-complete poset (every chain has a supremum)
– Markovian, if s ∈ T r for each s1 , s2 ∈ T r and t ∈ T such that t =
( 1 ) = inf dom(s2 ), s1 (t) ↓, s2 (t) ↓, and s1 (t) = s2 (t), where
sup dom(s
s1 (t), t ∈ dom(A)
s(t) = .
s2 (t), t ∈ dom(B)
Note that because T r is closed under restrictions to sets AS∈ T, the supremum
of a chain c in poset (T r, v) exists iff s∗ ∈ T r, where s∗ : s∈c dom(s) → Q is
defined as follows: s∗ (t) = s(t), if s ∈ c and t ∈ dom(s) (this definition is correct,
because c is a chain with respect to subtrajectory relation).
The notions of complete and Markovian sets of trajectories are illustrated in
Fig. 1 and 2.
Fig. 1. Completeness property
The following proposition gives some examples of sets of trajectories.
Proposition 1. Let Q = R. Consider the following sets of trajectories:
On Existence of Global-in-Time Trajectories ... 315
Fig. 2. Markovian property
– T rall is the set of all functions s : A → Q, A ∈ T.
– T rcont is the set of all continuous functions s ∈ T rall (on their domains)
– T rdif f is the set of all differentiable functions s ∈ T rall (on their domains)
– T rbnd is the set of all bounded functions s ∈ T rall (on their domains).
Then the following holds:
(1) ∅, T rall , T rcont , T rdif f , T rbnd , T rdif f ∩ T rbnd are CPR
(2) ∅, T rall , T rcont are complete and Markovian
(3) T rdif f is complete, but is not Markovian
(4) T rbnd is Markovian, but is not complete
(5) T rdif f ∩ T rbnd is neither complete, nor Markovian.
Definition 3. A non-deterministic complete Markovian system (NCMS) is dy-
namical system is (M, T, Q, T r) such that T r is complete and Markovian.
The following propositions 2-4 give some examples of NCMS.
Proposition 2. Let Q = Rd (d ∈ N) and M be a differential equation dy dt =
f (t, y), where f : R × Rd → Rd is a given total function. Let T r be the set of all
functions s : A → Q, A ∈ T such that s is differentiable on A and satisfies M
on A. Then (M, T, Q, T r) is a NCMS.
Proposition 3. Let M be a differential inclusion dy dt = F (t, y), where F : R ×
Rd → 2R is a given (total) function. This is not necessarily a( NCMS, but it
d
dy
=x
can be converted to a NCMS as follows. Let M 0 be the system dt ,
y ∈ F (t, x)
where x is a new variable. Let Q = Rd × Rd and T r be the set of all s : A → Q,
A ∈ T such that s is locally absolutely continuous on A and satisfies M 0 almost
everywhere on A (w.r.t. Lebesgue’s measure). Then (M, T, Q, T r) is a NCMS.
316 Ie. Ivanov
Proposition 4. Let Q be a set equipped
( with discrete topology. Let r ⊆ Q×Q be
y(t+) = y(t), / N0
t∈
a relation on Q. Let M be a system , where y denotes
(y(t), y(t+)) ∈ r, t ∈ N0
an unknown function, y(t+) denotes the right limit at t. Let T r be the set of all
piecewise-constant left-continuous functions s : A → Q (w.r.t. discrete topology
on Q) which satisfy M on A (see Fig. 3). Then (M, T, Q, T r) is a NCMS.
Fig. 3. A piecewise-constant left-continuous trajectory which models an execution of
a (discrete-time) transition system (Q, r).
Below we will describe a general complete Markovian set of trajectories (or
a system) in terms of certain local predicates.
Let us introduce the following terminology:
Definition 4. Let s1 , s2 : T →Q.
˜ Then s1 and s2 :
– coincide on a set A ⊆ T , if A ⊆ dom(s1 ) ∩ dom(s2 ) and s1 (t) = s2 (t) for
.
each t ∈ A. We denote this as s1 =A s2 .
– coincide in a left neighborhood of t ∈ T , if t > 0 and there exists t0 ∈ [0, t),
. .
such that s1 =(t0 ,t] s2 . We denote this as s1 =t− s2 .
– coincide in a right neighborhood of t ∈ T , if there exists t0 > t, such that
. .
s1 =[t,t0 ) s2 . We denote this as s1 =t+ s2 .
Let Q be a set of states. Denote by ST (Q) the set of pairs (s, t) where
s : A → Q for some A ∈ T and t ∈ A.
Definition 5. A predicate p : ST (Q) → Bool (Bool = {true, f alse}) is called
.
– left-local, if p(s1 , t) ⇔ p(s2 , t) whenever (s1 , t), (s2 , t) ∈ ST (Q) and s1 =t−
s2 , and moreover, p(s, t) whenever t is the least element of dom(s)
.
– right-local, if p(s1 , t) ⇔ p(s2 , t) whenever (s1 , t), (s2 , t) ∈ ST (Q), s1 =t+ s2 ,
and moreover, p(s, t) whenever t is the greatest element of dom(s)
On Existence of Global-in-Time Trajectories ... 317
– left-stable, if whenever t is not the least element of dom(s), p(s, t) implies
that there exists t0 ∈ [0, t) such that p(s, τ ) for all t0 ∈ [t0 , t] ∩ dom(s)
– right-stable, if whenever t is not the greatest element of dom(s), p(s, t) im-
plies that there exists t0 > t such that p(s, τ ) for all τ ∈ [t, t0 ] ∩ dom(s).
The theorems given below show how left- and right-local predicates can be
used to specify/represent a complete Markovian set of trajectories (or system).
Theorem 1. Let l : ST (Q) → Bool be a left-local predicate and r : ST (Q) →
Bool be a right-local predicate. Then the set
T r = {s : A → Q | A ∈ T ∧ (∀t ∈ A l(s, t) ∧ r(s, t))}.
is CPR, complete, and Markovian.
Theorem 2. Let T r be a CPR complete Markovian set of trajectories which take
values in the set of states Q. Then there exist unique predicates l, r : ST (Q) →
Bool such that l is left-local and left-sable, r is right-local and right-stable, and
T r = {s : A → Q | A ∈ T ∧ (∀t ∈ A l(s, t) ∧ r(s, t))}.
Let us consider an example which illustrates these theorems. Let Q = Rd and
T r be the set of all functions s : A → Q, A ∈ T such that s is differentiable on
A and satisfies a differential equation dy
dt = f (t, y) on A, where f : R × R → R
d d
is a given function. Then T r is complete and Markovian by Proposition 2.
Let us show how T r can be represented using left- and right-local predicates.
Let l, r : ST (Q) → Bool be predicates such that
– l(s, t) iff either t is the least element of dom(s), or ∂− s(t) ↓= f (t, s(t)),
– r(s, t) iff either t is the greatest element of dom(s), or ∂+ s(t) ↓= f (t, s(t)),
where ∂− s(t) and ∂+ s(t) denote the left- and right- derivative of s at t (the sym-
bol ↓ indicates that the left hand side of the equality is defined). It is not difficult
to check that l is left-local, r is right-local, and T r = {s : A → Q | A ∈ T ∧ (∀t ∈
A l(s, t) ∧ r(s, t))}. In general case, l and r are not necessarily (respectively) left-
and right-stable. But we can define another predicates l∗ , r∗ on ST (Q) such that
– l∗ (s, t) iff either t is the least element of dom(s), or there exists t0 < t such
that s is differentiable on (t0 , t] and satisfies differential equation dydt = f (t, y)
on (t0 , t] (at the time t the derivative is understood as left-derivative).
– r∗ (s, t) iff either t is the greatest element of dom(s), or there exists t0 > t
such that s is differentiable on [t, t0 ) and satisfies dy 0
dt = f (t, y) on [t, t ).
Then it is not difficult to see that l∗ is left-local and left-stable, and r∗ is right-
local and right-stable, and T r = {s : A → Q | A ∈ T ∧ (∀t ∈ A l(s, t) ∧ r(s, t))}.
318 Ie. Ivanov
3 Existence of Global-in-Time Trajectories
Let us recall our original question about global-in-time trajectories and formulate
it for non-deterministic complete Markovian systems.
Let (M, T, Q, T r) be a NCMS. Our question (let us denote it as Q0) is
whether it is true that for each t0 ∈ T , q0 ∈ Q there exists a trajectory s : T → Q
(i.e. global-in-time) such that s(t0 ) = q0 .
Note that we ask about existence of a trajectory defined in both time direc-
tions relative to t0 . The case when we are interested in existence of a trajectory
defined in one direction (e.g s : [t0 , +∞) → Q) is not considered in this paper,
but can be studied analogously.
Let us decompose Q0 into the following two questions:
Q1: Is it true that for each t0 ∈ T , q0 ∈ Q there exists a (partial) trajectory
s : A → Q such that t0 is an interior point of A (relative to the topology on
T , e.g. 0 is considered an interior point of [0, 1]) and s(t0 ) = q0 ?
Q2: Is it true that for each partial trajectory s : A → Q such that A is a
compact segment there exists a trajectory s0 : T → Q such that s = s0 |A ?
Proposition 5. The answer to the question Q0 is positive iff the answers to
Q1 and Q2 are positive.
The question Q1 is about existence of a local-in-time trajectories. We will not
study it in this paper and assume that it can be answered using domain-specific
methods. Our aim is to answer Q2 using only information about existence of
locally defined trajectories in the neighborhood of each time moment.
Let us introduce several definitions. Let Σ = (M, T, Q, T r) be a fixed NCMS.
Definition 6. – A right dead-end path (in Σ) is a trajectory s : A → Q such
that A has a form [a, b), where a, b ∈ T . and there is no s0 : [a, b] → Q ∈ T r
such that s = s0 |dom(s) (i.e. s cannot be extended to a trajectory on [a, b]).
The value b is called the end of this path.
– A left dead-end path (in Σ) is a trajectory s : A → Q such that A has a
form (a, b], where a, b ∈ T . and there is no s0 : [a, b] → Q ∈ T r such that
s = s0 |dom(s) . The value a is called the end of this path.
– A dead-end path is either a right dead-end path, or a left dead-end path.
Let f : [0, +∞) → [0, +∞) be a positive-definite (i.e. f (0) = 0, f (x) > 0 when
x > 0), monotonously non-decreasing, and continuous function (e.g. f (x) = x).
Definition 7. – A right dead-end path s : [a, b) → Q is called f -Ob -escapable,
where Ob is a connected neighborhood of b, if there exists c ∈ (a, b) ∩ Ob ,
d ∈ [b + f (b − c), +∞), and a trajectory s0 : [c, d] ∩ Ob → Q such that
s(c) = s0 (c).
– A left dead-end path s : (a, b] → Q is called f -Ob -escapable, where Ob is a
connected neighborhood of b, if there exists c ∈ (a, b) ∩ Ob , d ∈ [0, max{a −
f (c − a), 0}], and a trajectory s0 : [d, c] ∩ Ob → Q such that s(c) = s0 (c).
– A right- or left- dead-end path is called f -escapable, if it is f -T -escapable.
On Existence of Global-in-Time Trajectories ... 319
This definition is illustrated in Fig. 4. Note that a suffix of a right dead-end path
s : [a, b) → Q (i.e. a restriction of the form s|[a0 ,b) , where a0 ∈ [a, b)) is a right
dead-end path. Analogously, a prefix of a left dead-end path s : (a, b] → Q (i.e.
a restriction of the form s|(a,b0 ] , where b0 ∈ (a, b]) is a left dead-end path.
Let Σ = (M, T, Q, T r) be a NCMS. For each t ∈ T let Ot ⊆ T be some
connected neighborhood of t and Dt be the set of all dead-end paths s (in Σ)
such that t is the end of s and dom(s) ⊆ Ot .
Theorem 3. The following conditions are equivalent:
(1) for each partial trajectory s : A → Q such that A is a compact segment there
exists a trajectory s0 : T → Q such that s = s0 |A
(2) each dead-end path (in Σ) is f -escapable
(3) for each t ∈ T and s ∈ Dt , s is f -Ot -escapable.
Note that this theorem holds for an arbitrary fixed f and arbitrary fixed choice
of neighborhoods Ot , t ∈ T .
This theorem gives an answer to the question Q2. The condition 3 of this
theorem shows in which sense Theorem 3 reduces the question of global-in-time
existence of trajectories to the analysis of local existence of trajectories in the
neighborhood of each time moment.
Fig. 4. An f -escapable right dead-end path.
4 Conclusion
We have studied the question of existence of global-in-time trajectories for each
initial condition of a (non-time-invariant) non-deterministic complete Markovian
system. We have shown that this question can be answered using analysis of
existence of locally defined trajectories in a neighborhood of each time. The
results can be useful for studying the problems of well-posedness and reachability
for continuous and discrete-continuous (hybrid) dynamical systems.
320 Ie. Ivanov
References
1. Willems, J.: Paradigms and Puzzles in the Theory of Dynamical Systems. IEEE
Transactions on automatic control. 36, 259–294 (1991)
2. Coddington, E., Levinson, N.: Theory of ordinary differential equations. McGraw-
Hill, New York (1955)
3. Fillipov, A.: Differential equations with discontinuous right-hand sides. AMS
Trans. 42, 199–231 (1964)
4. Tangiguchi, T.: Global existence of solutions of differential inclusions. Journal of
mathematical analysis and applications. 166, 41–51 (1992)
5. Aubin, A., Cellina, A.: Differential inclusions. Springer-Verlag, Berlin (1984)
6. Seah, S.W.: Existence of solutions and asymptotic equilibrium of multivalued
differential systems. J. Math. Anal. Appl. 89, 648–663 (1982)
7. Gliklikh, Y.: Necessary and sufficient conditions for global-in-time existence of
solutions of ordinary, stochastic, and parabolic differential equations. Abstract
and Applied Analysis. 2006, 1–17 (2006)
8. Heemels, W., Camlibel, M., Van der Schaft, A.J., Schumacher, J.M.: On the
existence and uniqueness of solution trajectories to hybrid dynamical systems. In:
Johansson, R., Rantzer, A. (eds.) Nonlinear and Hybrid Control in Automotive
Applications. pp. 391–422. Springer, Berlin (2003)
9. Goebel, R., Sanfelice, R., Teel, R.: Hybrid dynamical systems. IEEE Control
Systems Magazine. 29, 29–93 (2009)
10. Henzinger, T.: The theory of hybrid automata. IEEE Symposium on Logic in
Computer Science. 278–292 (1996)
11. Constantin, A.: Global existence of solutions for perturbed differential equations.
Annali di Matematica Pura ed Applicata. 168, 237–299 (1995)
12. Doob, J.B.: Stochastic processes. Wiley-Interscience (1990)