Introduction

In this paper we consider the following question: given a continuous-time nondeterministic (not necessarily time-invariant) dynamical system Σ, is it true that for any time moment t 0 and initial state x 0 there exists a global-in-time trajectory t → s(t) such that s(t 0 ) = x 0 . Some related problems, e.g. global existence of solutions of initial value problems for various classes of differential equations [2,3,7] and inclusions [4][5][6], existence of non-Zeno global-in-time executions of hybrid automata [8][9][10] are well known. However, they have mostly been studied in the context of deterministic systems (differential equations with unique solutions, deterministic hybrid automata, etc.). Differential inclusions [5] are in principle non-deterministic systems, 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 interval 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 condition x(t 0 ) = x 0 the differential inclusion dx dt ∈ [0, x 2 ] has both a globally defined constant trajectory x(t) = x 0 and a trajectory of the equation dx dt = x 2 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.

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 nondeterministic 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 deterministic) systems which can have both continuous and discontinuous (jump-like) trajectories. Essentially, the notion of a non-deterministic Markovian system captures 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, ...}, N 0 = 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, 2 A 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 dynamical system on the time scale T . Definition 1. A dynamical system on T is as an abstract object M (a mathematical model; in applications this may be an equation, inclusion, switched system, etc.) together with the associated time scale T (this scale will be the same 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 s 1 ∈ T r is a subtrajectory of s 2 ∈ T r (denoted as

s 1 s 2 ), if s 1 = s 2 | A for some A ∈ T.

The trajectories s 1 and s 2 are incomparable, if s 1 is not a subtrajectory of s 2 and vice versa.

According to the definition given above, for a time t 0 ∈ T and q 0 ∈ Q there may exist multiple incomparable trajectories s such that s(t 0 ) = q 0 (as well as one or none). In this sense a dynamical system can be non-deterministic.

It is easy to see that (T r, ) is a partially ordered set (poset).

Definition 2. A set T r (which is CPR) is -complete, if (T r, ) is a chain-complete poset (every chain has a supremum) -Markovian, if s ∈ T r for each s 1 , s 2 ∈ T r and t ∈ T such that t = sup dom(s 1 ) = inf dom(s 2 ), s 1 (t) ↓, s 2 (t) ↓, and s 1 (t) = s 2 (t),wheres(t) = s 1 (t), t ∈ dom(A) s 2 (t), t ∈ dom(B) .

Note that because T r is closed under restrictions to sets A ∈ T, the supremum of a chain c in poset (T r, ) 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. -T r cont is the set of all continuous functions s ∈ T r all (on their domains) -T r dif f is the set of all differentiable functions s ∈ T r all (on their domains) -T bnd is the set of all functions s ∈ T r all (on their domains).

Then the following holds:

(1) ∅, T r all , T r cont , T r dif f , T r bnd , T r dif f ∩ T r bnd are CPR (2) ∅, T r all , T r cont are complete and Markovian (3) T r dif f is complete, but is not Markovian (4) T r bnd is Markovian, but is not complete (5) T r dif f ∩ T r bnd is neither complete, nor Markovian. Definition 3. A non-deterministic complete Markovian system (NCMS) is dynamical 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 = R d (d ∈ N)

and M be a differential equation dy dt = f (t, y), where f : R × R d → R d 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 × R d → 2 R d

is a given (total) function. This is not necessarily a NCMS, but it can be converted to a NCMS as follows. Let M be the system , where y denotes 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. Below we will describe a general complete Markovian set of trajectories (or a system) in terms of certain local predicates.

dy dt = x y ∈ F (t, x) , where x is a new variable. Let Q = R d × R d and T r be the set of all s : A → Q, A ∈ T such

Let us introduce the following Definition 4. Let s 1 , s 2 : T →Q. Then s 1 and s 2 :

-coincide on a set A ⊆ T , if A ⊆ dom(s 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(s 1 , t) ⇔ p(s 2 , t) whenever (s 1 , t), (s 2 , t) ∈ ST (Q) and s 1 . = t− s 2 ,

and moreover, p(s, t) whenever t is the least element of dom(s) -right-local, if p(s 1 , t) ⇔ p(s 2 , t) whenever (s 1 , t), (s 2 , t) ∈ ST (Q), s 1 . = t+ s 2 , and moreover, p(s, t) whenever t is the greatest element of dom(s) -left-stable, if whenever t is not the least element of dom(s), p(s, t) implies that there exists t ∈ [0, t) such that p(s, τ ) for all t ∈ [t , t] ∩ dom(s) -right-stable, if whenever t is not the greatest element of dom(s), p(s, t) implies that there exists t > t such that p(s, τ ) for all τ ∈ [t, t ] ∩ 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 = : 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 = R d 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 d → R 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 symbol ↓ 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) leftand 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 t < t such that s is differentiable on (t , t] and satisfies differential equation dy dt = f (t, y) on (t , 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 t > t such that s is differentiable on [t, t ) and satisfies dy 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 rightlocal and right-stable, and T r = {s :

A → Q | A ∈ T ∧ (∀t ∈ A l(s, t) ∧ r(s, t))}.

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 t 0 ∈ T , q 0 ∈ Q there exists a trajectory s : T → Q (i.e. global-in-time) such that s(t 0 ) = q 0 . Note that we ask about existence of a trajectory defined in both time directions relative to t 0 . The case when we are interested in existence of a trajectory defined in one direction (e.g s : [t 0 , +∞) → 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 t 0 ∈ T , q 0 ∈ Q there exists a (partial) trajectory s : A → Q such that t 0 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(t 0 ) = q 0 ? Q2: Is it true that for each partial trajectory s : A → Q such that A is a compact segment there exists a trajectory s : T → Q such that s = s | 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. 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 -O b -escapable, where O b is a connected neighborhood of b, if there exists c ∈ (a, b) ∩ O b , d ∈ [b + f (b − c), +∞), and a trajectory s : [c, d] ∩ O b → Q such that s(c) = s (c). -A left dead-end path s : (a, b] → Q is called f -O b -escapable, where O b is a connected neighborhood of b, if there exists c ∈ (a, b) ∩ O b , d ∈ [0, max{a − f (c − a),0}

], and a trajectory s : Let Σ = (M, T, Q, T r) be a NCMS. For each t ∈ T let O t ⊆ T be some connected neighborhood of t and D t be the set of all dead-end paths s (in Σ) such that t is the end of s and dom(s) ⊆ O t . Theorem 3. The following conditions are equivalent:

[d, c] ∩ O b → Q such that s(c) = s (c). -A right-or left-dead-end path is called f -escapable, if it is f -T -escapable.

(1) for each partial trajectory s : A → Q such that A is a compact segment there exists a trajectory s : T → Q such that s = s | A (2) each dead-end path (in Σ) is f -escapable (3) for each t ∈ T and s ∈ D t , s is f -O t -escapable.

Note that this theorem holds for an arbitrary fixed f and arbitrary fixed choice of neighborhoods O t , 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.

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.