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)