Alberto Bressan

Marco Mazzola
email: marco.mazzola@imj-prg.fr

Khai T Nguyen

Markovian Solutions to Discontinuous ODEs

Given a possibly discontinuous, bounded function f : R → R, we consider the set of generalized flows, obtained by assigning a probability measure on the set of Carathéodory solutions to the ODE ẋ = f (x). The paper provides a complete characterization of all such flows which have a Markov property in time. This is achieved in terms of (i) a positive, atomless measure supported on the set f -1 (0) where f vanishes, (ii) a countable number of Poisson random variables, determining the waiting times at points in f -1 (0), and (iii) a countable set of numbers θ k ∈ [0, 1], describing the probability of moving up or down, at isolated points where two distinct trajectories can originate.

Introduction

Consider a scalar ODE with possibly discontinuous right hand side: ẋ = f (x).

(1.1)

Given an initial condition

x(0) = x 0 , (1.2)
we recall that t → x(t) is a Carathéodory solution of the Cauchy problem (1.1)-(1.2) if

x(t) = x 0 + t 0 f (x(s)) ds for all t ≥ 0 .

(1.3)

When the function f is not Lipschitz continuous, it is well known that this Cauchy problem can admit multiple solutions. Because of this non-uniqueness, in [START_REF] Vanden-Eijnden | A note on generalized flows[END_REF] it was proposed to study "generalized flows", described by a probability measure on the set of all Carathéodory solutions. See also [START_REF] Flandoli | Markov attractors: a probabilistic approach to multivalued flows[END_REF] for a related approach. In this direction, the main goal of the present paper is to describe all stochastic flows compatible with the ODE, which have the Markov property. Toward this goal, in the first part of the paper we describe all possible deterministic semigroups:

Definition 1.1 By a deterministic semigroup compatible with the ODE (1.1) we mean a map S : R × R + → R, with the properties (i) S t (S s (x 0 )) = S t+s (x 0 ), S 0 (x 0 ) = x 0 .

(ii) For each x 0 ∈ R, the map t → S t x 0 is a solution to the Cauchy problem (1.1)- (1.2).

Notice that here we do not require any continuity w.r.t. the initial point x 0 . Throughout the following, as basic assumptions we consider:

(A1) The function f : R → R is bounded and regulated, i.e. it admits left and right limits f (x-), f (x+) at every point x.

(A2) If y is a point where either f (y-) • f (y+) = 0 or else f (y-) > 0 > f (y+), then f (y) = 0.

Remark 1. [START_REF] Alberti | A uniqueness result for the continuity equation in two dimensions[END_REF] The assumption (A2) corresponds to the "no-jamming" condition used in [START_REF] Binding | The differential equation ẋ = f • x[END_REF].

It is needed to rule out examples such as

ẋ = f (x) =    1 if x < 0, -1 if x > 0, a if x = 0,
x(0) = 0, which has no Carathéodory solution if a = 0.

Remark 1.2 It is well known that every regulated function has at most countably many points of discontinuity. Namely, the set

D f = x ∈ R ; f (x-) = f (x+) or f (x-) = f (x+) = f (x) (1.4)
is at most countable. We observe that, under the assumptions (A1)-(A2), the set of zeroes

f -1 (0) = x ∈ R ; f (x) = 0 (1.5)
is closed. Indeed, assume that f (x n ) = 0 for a strictly increasing sequence x n → x. By (A1) this implies that the left limit exists and satisfies f (x-) = 0. Hence (A2) yields f (x) = 0. Similarly, if x n decreases to x, then f (x+) = 0 and hence (A2) again implies f (x) = 0.

In Section 3, we will show that, in order to uniquely determine a deterministic semigroup compatible with (1.1), three additional ingredients are needed:

(Q1) A continuum (i.e., atomless) positive measure µ supported on the set of zeroes (1.5) of f . Strictly increasing trajectories t → x(t) = S t (x 0 ) of the semigroup are then defined by the identity t =

x(t)

x 0 dy f (y) + µ [x 0 , x(t)] , (1.6)
while a similar formula holds for decreasing ones. Notice that, if f -1 (0) is countable, then necessarily µ = 0.

(Q2) A countable set of points S ⊆ f -1 (0), where the dynamics is forced to stop. Among the (possibly many) solutions of (1.1) starting from x 0 ∈ S, we thus choose S t (x 0 ) = x 0 .

(Q3) A map Φ : Ω * → {-1, 1}, defined on a set Ω * ⊂ R of isolated points from where both an increasing and a decreasing solution of (1.1) can originate. For x 0 ∈ Ω * , setting Φ(x 0 ) = 1 selects the increasing solution, while Φ(x 0 ) = -1 selects the decreasing one.

In the second part of the paper we study Markov processes, whose sample paths are solutions to (1.1). Given a deterministic semigroup compatible with (1.1), in Section 4 we show that a Markov semigroup can be obtained by adding two more ingredients to the list (Q1)-(Q3).

Namely:

(Q4) A countable set S * ⊂ f -1 (0) and a map Λ : S * → ]0, +∞[ , describing the random waiting time of a trajectory which reaches a point y j ∈ S * . More precisely, we assume that a solution initially at y j ∈ S * remains at y j for a random waiting time Y j ≥ 0, then starts moving. All these random times will be mutually independent, with Poisson distribution: Prob.{Y j > s} = e -λ j s with λ j = Λ(y j ).

(1.7) (Q5) A map Θ : Ω * → [0, 1], defined on the countable set Ω * ⊂ R of points from which both an increasing and a decreasing solution of (1.1) can originate. For x k ∈ Ω * , the value θ k = Θ(x k ) gives the probability that, when the solution starting from x k begins to move, it will be increasing. Of course, 1 -θ k is then the probability that the solution will be decreasing.

Conversely, in Section 5 we prove that every Markov semigroup whose sample paths are solutions to (1.1) can be obtained by first constructing a deterministic semigroup S as in (Q1)-(Q3), and then adding the random waiting times Y j in (Q4) and the upward vs. downward probabilities θ k in (Q5).

Example 1.1 Given 0 < α < 1, consider the ODE ẋ = |x| α 1 -α . (1.8)
This provides a classical example of an ODE with continuous right hand side, with multiple solutions starting at the origin. This ODE is compatible with two deterministic semigroups S, S : R × R + → R. The first one satisfies S t (0) = 0 for all t ≥ 0, while the second one satisfies S t (0) = t A random solution starting at x = 0 remains at the origin up to time T , then it is strictly increasing for t > T , namely x(t) = (t -T ) Example 1.2 Let C ⊂ [0, 1] be the Cantor set, which we write in the form

C = [0, 1] \ ∞ n=0 2 n k=1 I n k (1.9)
where n+1) . We define

I n k = ]a n k , b n k [ are disjoint open intervals with length 3 -(
f (x) =    0 if x ∈ C ∪ ] -∞, 0] ∪ [1, +∞[ , min x -a n k 1/3 , x -b n k 1/3 if x ∈ I n k .
In this case the ODE (1.1) is compatible with infinitely many deterministic semigroups, corresponding to different choices of countable sets S ⊆ f -1 (0), where the dynamics is forced to stop. Furthermore, in this example the set of zero points of f where multiple solutions can initiate is uncountable (see Remark 3.2). As a consequence, this set can support nontrivial atomless measures µ that generate deterministic semigroups S : R × R + → R, whose strictly increasing trajectories t → x(t) = S t (x 0 ) satisfy (1.6).

The remainder of the paper is organized as follows. In Section 2 we briefly review some basic properties of scalar ODEs with discontinuous right hand side. For the main results on existence and uniqueness of solutions we refer to [START_REF] Binding | The differential equation ẋ = f • x[END_REF]. These are based on the elementary solution formula

x(t) x 0 1 f (y) dy = t , (1.10)
valid on intervals where f has a.e. the same sign, and 1/f is integrable.

Section 3 is concerned with deterministic semigroups. Theorem 3.1 describes the most general semigroup S : R ×R + → R compatible with the ODE (1.1). In Section 4 we construct a family of Markov semigroups whose sample paths are solutions to (1.1). Each of these semigroups is determined by the additional data introduced at (Q1)-(Q5). Finally, Theorem 5.1 in Section 5 shows that every Markov semigroup compatible with (1.1) is one of the above family.

In the companion paper [START_REF] Bressan | Diffusion approximations of Markovian solutions to discontinuous ODEs[END_REF], the authors show that every deterministic semigroup compatible with (1.1) can be obtained as the pointwise limit of the flows generated by a sequence of ODEs ẋ = f n (x) with smooth right hand sides. Moreover, every Markovian semigroup can be obtained as limit of a sequence of diffusion processes with smooth drifts and with diffusion coefficients approaching zero.

Ordinary differential equations with discontinuous right hand side have been studied for their own interest [START_REF] Binding | The differential equation ẋ = f • x[END_REF][START_REF] Bressan | Unique solutions for a class of discontinuous differential equations[END_REF][START_REF] Bressan | Existence and continuous dependence for discontinuous O.D.E's, Boll[END_REF][START_REF] Filippov | Differential Equations with Discontinuous Right-Hand Sides[END_REF][START_REF] Sentis | Équations différentielles à second membre mesurable[END_REF], as well as for their several applications to feedback control [START_REF] Ancona | Patchy vector fields and asymptotic stabilization[END_REF][START_REF] Clarke | Nonsmooth Analysis and Control Theory[END_REF][START_REF] Marigo | Regular syntheses and solutions to discontinuous ODEs[END_REF][START_REF] Piccoli | Regular synthesis and sufficiency conditions for optimality[END_REF]. They also play a key role in the theory of transport equations [START_REF] Alberti | A uniqueness result for the continuity equation in two dimensions[END_REF][START_REF] Ambrosio | Existence, uniqueness, stability and differentiability properties of the flow associated to weakly differentiable vector fields[END_REF][START_REF] Colombini | Uniqueness in the Cauchy problem for transport in R 2 and R 1+2[END_REF][START_REF] Diperna | Ordinary differential equations, transport theory and Sobolev spaces[END_REF], and in the analysis of solutions to hyperbolic conservation laws by the method of characteristics [START_REF] Bressan | Uniqueness for discontinuous O.D.E. and conservation laws[END_REF][START_REF] Colombo | A Hölder continuous ODE related to traffic flow[END_REF][START_REF] Dafermos | Generalized characteristics and the structure of solutions of hyperbolic conservation laws[END_REF][START_REF] Dafermos | Generalized characteristics in hyperbolic systems of conservation laws[END_REF]. For a survey of numerical methods we refer to [START_REF] Dieci | A survey of numerical methods for IVPs of ODEs with discontinuous right-hand side[END_REF].

Among the motivations for the present study we observe that, by constructing a semigroup of solutions to (1.1), one obtains a natural way to solve the continuity equation

d dt µ t + D x f (x) µ t = 0, µ 0 = µ. (1.11)
Indeed, if {S t ; t ≥ 0} is a semigroup compatible with the ODE (1.1), then one can define the measure µ t as the push-forward of µ w.r.t. the map x → S t (x). This will provide a measurevalued solution to the Cauchy problem (1.11). In several space dimensions, under stronger regularity assumptions on the vector field f , the existence and uniqueness of solutions to (1.11) has been studied in several papers; see [START_REF] Ambrosio | Existence, uniqueness, stability and differentiability properties of the flow associated to weakly differentiable vector fields[END_REF] for a survey. Our study of the one-dimensional case yields examples where uniqueness fails and multiple semigroups are found. This gives a glimpse of the far greater complexities that can be encountered in a multi-dimensional setting.

Review of scalar discontinuous ODEs

As a preliminary, we collect here some basic results on the existence and properties of solutions to a Cauchy problem with possibly discontinuous right hand side. In the following theorem, the first two statements can already be found in [START_REF] Binding | The differential equation ẋ = f • x[END_REF], where a more general setting was considered. However, the closure of the solution set strongly relies on the assumption (A1) that the function f is regulated.

Theorem 2.1 Consider the Cauchy problem (1.1)-(1.2), assuming that (A1)-(A2) hold. Then (i) For every x 0 ∈ R there exists at least one Carathéodory solution, defined for all times t ≥ 0.

(ii) Every solution is monotone (either increasing or decreasing).

(iii) The set of all solutions is nonempty and closed w.r.t. the topology of uniform convergence on bounded sets.

Proof. 1. We begin by proving that (1.1)-(1.2) admits a Carathéodory solution. By the assumption (A1) there exists a constant M > 0 such that

|f (x)| ≤ M for all x ∈ R. (2.1)
Let any x 0 ∈ R be given. If f (x 0 ) = 0 then trivially x(t) ≡ x 0 is a solution of (1.1). On the other hand, if f (x 0 ) = 0, then by the assumption (A2) we must have

either f (x 0 +) > 0 or f (x 0 -) < 0 .
To fix the ideas, assume f (x 0 +) > 0, the other case being entirely similar. We can then find δ, h > 0 such that

h ≤ f (x) ≤ M for all x ∈ ]x 0 , x 0 + δ].
The map

x → t(x) . = x x 0 dy f (y)
is thus strictly increasing in the interval [x 0 , x 0 + δ]. Indeed, for the above inequality, for all

x 0 ≤ x 1 < x 2 ≤ x 0 + δ it holds x 2 -x 1 M ≤ t(x 2 ) -t(x 1 ) = x 2 x 1 dy f (y) ≤ x 2 -x 1 h .
This implies that the inverse map t → x(t) is strictly increasing and Lipschitz continuous. Hence it is absolutely continuous, and satisfies

ẋ(t) = d dx t(x) -1 = f (x(t)) for a.e. t ∈ [t(x 0 ), t(x 0 + δ)].
Thus, x(t) is a solution of (1.1), defined on the interval [t(x 0 ), t(x 0 + δ)].

We claim that this solution can be extended for all t ∈ [0, +∞[ . Indeed, if [0, T [ is a maximal domain where the solution can be constructed, since f is bounded by M , the limit x(T ) . = lim t→T -x(t) exists. By the previous arguments, the solution can then be extended to [0, T +δ] for some δ > 0, contradicting the maximality assumption.

2.

To prove that every solution is monotone, let t → x(t) be a Carathéodory solution of (1.1). Assume, on the contrary, that x(•) is neither monotone increasing nor decreasing. Without loss of generality we can assume that

x(t 1 ) = x(t 2 ) < x( t)
for some t 1 < t < t 2 .

Since x(•) is absolutely continuous, there exists

τ 1 ∈ ]t 1 , t 2 [ such that x(•) is differentiable at τ 1 and ẋ(τ 1 ) > 0, x(t 1 ) < x(τ 1 ) < x( t) .
Therefore there exists δ 0 > 0 such that x(τ 1 ) < x(τ 1 + s) for all s ∈ ]0, δ 0 [ . Since f has a right limit at x(τ 1 ), we deduce

0 < ẋ(τ 1 ) = lim h→0+ 1 h h 0 f (x(τ 1 + s)) ds = f (x(τ 1 )+). (2.2)
On the other hand, since x(t 2 ) < x(τ 1 ) < x( t), we consider the time

τ 2 . = min t ≥ t : x(t) = x(τ 1 ) .
The above definition implies x(t) > x(τ 1 ) for all t ∈ [ t, τ 2 [ while

x(τ 2 ) = lim t→τ 2 - x(t) = x(τ 1 ).
As a consequence, we have

f (x(τ 1 )+) = lim h→0+ 1 h 0 -h f (x(τ 2 + s)) ds = lim h→0+ x(τ 2 ) -x(τ 2 -h) h ≤ 0,
reaching a contradiction with (2.2).

3.

To prove (iii), consider a sequence of solutions x n (•) of (1.1), converging to a function x(•) uniformly on bounded sets. We claim that x is also a Carathéodory solution. To fix the ideas, assume that all solutions x n are monotone increasing. Hence x is monotone increasing as well.

We need to show that

x(b) = x(a) + b a f (x(s)) ds (2.3)
for any interval [a, b]. Toward this goal, consider the set of times

I 0 = t ∈ [a, b] ; there exists ε > 0 such that x(•) is constant either on [t, t + ε] or on [t -ε, t] .
We claim that x(t) ∈ f -1 ({0}) for all t ∈ I 0 .

(2.4) Indeed, by the definition of I 0 , for any t 0 ∈ I 0 there exist t 1 < t 2 with t 0 ∈ [t 1 , t 2 ] such that

x(t) = x(t 0 ) for all t ∈ [t 1 , t 2 ] .
Hence,

lim n→∞ t 2 t 1 f (x n (t)) dt = lim n→∞ x n (t 2 ) -x n (t 1 ) = 0 .
Since x n is monotone increasing, we have f (x n (s)) = x n (s) ≥ 0 for a.e. s. This implies

lim n→∞ f (x n ) L 1 ([t 1 ,t 2 ]) = 0 .
By possibly taking a subsequence, this yields the pointwise convergence f

(x n (t)) → 0 for a.e. t ∈ [t 1 , t 2 ].
As a consequence, one of the three following cases must hold:

(i) f (x(t 0 )) = 0, (ii) f (x(t 0 )-) = 0, (iii) f (x(t 0 )+) = 0.
By the assumption (A2), both (ii) and (iii) imply (i), proving our claim (2.4). In particular, this implies lim

n→∞ f (x n (t)) = f (x(t)) = 0 for a.e. t ∈ I 0 . (2.5)
Next, from the definition of I 0 it follows that the function x(•) is one-to-one (strictly increasing) on [a, b]\I 0 . In particular, this implies that the set

t ∈ [a, b] \ I 0 ; x(t) ∈ D f is at most countable. Since f is continuous outside D f and x n (t) converges to x(t) for every t ∈ [a, b], we have lim n→∞ f (x n (t)) = f (x(t)) for a.e. t ∈ [a, b] \ I 0 . (2.6) By (2.5)-(2.6), the dominated convergence theorem yields lim n→∞ b a f (x n (t)) ds = b a f (x(t)) dt .
This proves (2.3).

Example 2.1 To appreciate the importance of the assumption (A1), consider the following Cauchy problem, proposed in [START_REF] Binding | The differential equation ẋ = f • x[END_REF].

ẋ = f (x) = 0 if x = 1, 1 2 , 1 3 , . . . 1 otherwise, x(0) = 0. (2.7)
Then for every n ≥ 1 the function

x n (t) = min 1 n , t
is a Carathéodory solution, but the uniform limit x(t) = lim n→∞

x n (t) = 0 does not satisfy (2.7). Notice that the function f in (2.7) is not regulated.

Semigroups compatible with the ODE

In general, the Cauchy problem for the discontinuous ODE (1.1)-(1.2) admits several different solutions. Our present goal is to study all possible semigroups S : R × R + → R compatible with the ODE (1.1), in the sense of Definition 1.1.

We first introduce a few definitions. For any function f , denote

f + (x) . = max{f (x), 0}, f -(x) = min{f (x), 0}.
If f is regulated, so are f + , f -. Moreover, we define the sets

R -. = x ∈ R ; x x-ε 1 f -(y)
dy > -∞ for some ε > 0 ,

R + . = x ∈ R ; x+ε x 1 f + (y) (3.1)
dy < +∞ for some ε > 0 .

Notice that x ∈ R -if there exists a strictly decreasing Carathéodory solution to (1.1), say

x : [0, τ ] → R, with τ > 0, such that x(0) = x. Similarly, x ∈ R + if there exists a strictly increasing Carathéodory solution to (1.1) which starts at x.

From the above definitions, it immediately follows that R -is open to the left and R + is open to the right. Namely

x ∈ R - =⇒ ]x -δ, x] ⊂ R - for some δ > 0, x ∈ R + =⇒ [x, x + δ[⊂ R + for some δ > 0.
For future use, we also define the sets

Ω * . = R -∩ R + , Ω 0 . = R \ R -∪ R + ). (3.3)
Notice that Ω * is the set of points from which two distinct solutions of (1.1) can initiate: one strictly decreasing, and one strictly increasing. On the other hand, Ω 0 is a set of points from which neither an increasing nor a decreasing solution can initiate. If x 0 ∈ Ω 0 , the unique solution to the Cauchy problem (1.1)-(1.2) is the constant one: x(t) = x 0 for all t ≥ 0.

Remark 3.1 By (A2), the set of zeroes f -1 (0) is closed. Moreover, the assumptions (A1)-(A2) imply the inclusion Ω 0 ⊆ f -1 (0). We also observe that the set Ω * consists of isolated points. Therefore, there can be at most countably many such points.

Remark 3.2 In general, the set

f -1 (0) ∩ (R + ∪ R -) (3.4)
has measure zero, hence its interior is empty. However, it may well be uncountable. For instance let f be defined as in Example 1.2. It is easy to check that f is continuous and

[0,1]\C 1 f (x) dx = ∞ n=0 2 n k=1 I n k 1 f (x) dx = 3 ∞ n=0 2 n k=1 3 -(n+1) 2 2/3 = 3 1/3 2 2/3 • ∞ n=0 2 3 2/3 n < + ∞.
This provides an example where the set f -1 (0) ∩ R + = C\{1} is uncountable.

We now consider the ODE (1.1), together with a positive, atomless measure µ supported on f -1 (0), a countable set S ⊆ f -1 (0), and a map Φ : Ω * → {-1, 1}, as described at (Q1)-(Q3) in the Introduction. We claim that these assignments uniquely determine a semigroup S : R × R + → R, compatible with the ODE (1.1). • If α i / ∈ S and, for some ε > 0

Definition 3.1 We say that an open interval

]a, b[ is a domain of increase if ]a, b[ ∩ S = ∅, µ([c, d]) + dx f + (x) < + ∞ for all [c, d] ⊂ ]a, b[ . (3.5) Similarly, we say that ]a, b[ is a domain of decrease if ]a, b[ ∩ S = ∅, µ([c, d]) - d c dx f -(x) < + ∞ for all [c, d] ⊂ ]a, b[ . (3.6)
µ([α i , α i + ε]) + α i +ε α i dx f + (x) < + ∞, (3.7)
we then consider the half-open interval

I + i . = [α i , β i [ . Otherwise, we let I + i be an open interval: I + i . = ]α i , β i [ . • If δ i / ∈ S and, for some ε > 0 µ([δ i -ε, δ i ]) - δ i δ i -ε dx f -(x) < + ∞, (3.8)
we then consider the half-open interval

I - i . = ]γ i , δ i ] .
Otherwise, we let I - i be an open interval:

I - i . = ]γ i , δ i [ .
For each i ∈ I + , we now describe the increasing dynamics on the intervals I + i . Given x 0 ∈ I + i , we consider the time

τ + (x 0 ) . = µ([x 0 , β i ]) + β i x 0 dy f + (y) ∈ ]0, +∞].
We then set

S + t (x 0 ) . = x(t), (3.9)
where x(t) is implicitly defined by

µ([x 0 , x(t)]) + x(t) x 0 dy f + (y) = t if t < τ + (x 0 ), x(t) = β i if t ≥ τ + (x 0 ). (3.10)
The construction of the decreasing dynamics on the intervals I - i is entirely similar. Given x 0 ∈ I - i , we consider the time

τ -(x 0 ) . = µ([γ i , x 0 ]) - x 0 γ i dy f + (y) ∈ ]0, +∞].
We then set

S - t (x 0 ) . = x(t), (3.11)
where x(t) is implicitly defined by

µ([x(t), x 0 ]) - x 0 x(t) dy f -(y) = t if t < τ -(x 0 ), x(t) = γ i if t ≥ τ -(x 0 ). (3.12)
We can now combine together the above solutions, and define the semigroup S on the whole real line, as follows.

S t (x 0 ) =          x 0 if x 0 / ∈ i I + i ∪ i I - i , S + t (x 0 ) if x 0 ∈ i I + i \ i I - i , S - t (x 0 ) if x 0 ∈ i I - i \ i I + i . (3.13)
To complete the definition, it remains to define S t (x 0 ) in the case

x 0 ∈ i I - i ∩ i I + i .
Notice that this can happen only if

x 0 = α i = δ j where I + i = [α i , β i [ and I - j = ]γ j , δ j ]
are half-open intervals where the dynamics is increasing and decreasing, respectively. By our definitions, this implies x 0 ∈ Ω * . Recalling (Q3), we thus define

S t (x 0 ) = S + t (x 0 ) if Φ(x 0 ) = 1, S - t (x 0 ) if Φ(x 0 ) = -1. (3.14)
We claim that the above map S defines a semigroup compatible with the ODE (1.1). Toward this goal, we first prove 2) if and only if there exists a positive, atomless Borel measure µ, supported on the set f -1 (0), such that

x(t) x 0 1 f (s) ds + µ [x 0 , x(t)] = t (3.15)
for all t ∈ [0, τ ]. Proof. 1. Assume that x(•) is a Carathéodory solution to (1.1)-(1.2). Set x 0 = x(0) and x = x(τ ). Define a positive Borel measure µ on [x 0 , x] by setting µ([x 0 , y]) = meas {t ∈ [0, t(y)] ; f (x(t)) = 0} , (3.16)
where t(y) is the unique time such that x(t(y)) = y. Of course, the right hand side of (3.16) refers to Lebesgue measure. Since f -1 (0) is closed, for every x ∈]x 0 , x[\f -1 (0) there exists δ > 0 such that ]x -δ, x + δ[⊂]x 0 , x[\f -1 (0) and this yields

µ(]x -δ, x + δ[) = 0.
Hence µ is supported on the set f -1 (0). By the continuity and the strict monotonicity property of the function x(•), the map y → µ([x 0 , y]) is continuous. This implies that µ is an atomless measure.

To prove (3.15) we observe that, for every t ∈ [0, τ ], the set

T 0 (t) = {s ∈ [0, t] ; f (x(s)) = 0} (3.17) is closed. Hence ]0, t[\T 0 (t)
t = meas {s ∈ [0, t] ; f (x(s)) = 0} + meas {s ∈ [0, t] ; f (x(s)) = 0} = meas ]0, t[\T 0 (t) + µ [x 0 , x(t)] = i t i s i 1dt + µ [x 0 , x(t)] = i t i s i ẋ(t) f (x(t)) dt + µ [x 0 , x(t)] = i x(t i ) x(s i ) 1 f (y) dy + µ [x 0 , x(t)] = x(t) x 0 1 f (y) dy + µ [x 0 , x(t)] ,
proving (3.15).

2.

Conversely, let µ be a positive, atomless Borel measure on [x 0 , x] = [x(0), x(τ )], and assume that t → x(t) is a strictly increasing function, implicitly defined by (3.15) for all t ∈ [0, τ ]. For every finite sequence of pairwise disjoint sub-intervals ]s i , t i [ ⊆ ]0, τ [, we estimate

N i=1 |t i -s i | = N i=1 x(t i ) x(s i ) 1 f (y) dy + µ [x(s i ), x(t i )] ≥ 1 M • N i=1 |x(t i ) -x(s i )|.
This implies that x(•) is absolutely continuous on [0, τ ]. In particular, x(•) is differentiable almost everywhere in [0, τ ] and

x(t) = x(s) + t s ẋ(r)dr for all s < t ∈ [0, τ ]. (3.18)
As in (1.4), we denote by D f the set of points where f is discontinuous. For any

s 0 ∈]0, τ [ such that x(•) is differentiable at s 0 and x(s 0 ) / ∈ f -1 (0) ∪ D f , one has lim ε→0+ 1 ε • x(s 0 +ε) x(s 0 ) 1 f (y) dy = ẋ(s 0 ) f (x(s 0 ))
.

Since µ is supported on the closed set f -1 (0), we have µ([x(s 0 ), x(s 0 + δ)]) = 0 for some δ > 0. Thus, (3.15) implies

1 = lim ε→0+ 1 ε • x(s 0 +ε) x(s 0 ) 1 f (y) dy + µ([x(s 0 ), x(s 0 + ε)]) ε = ẋ(s 0 ) f (x(s 0 ))
.

Since D f is countable, one has ẋ(s) = f (x(s)) for a.e. s ∈ [0, τ ]\T 0 (τ ). (3.19) Given any t ∈]0, τ [, the open set ]x(0), x(t)[\f -1 (0) can be written as a disjoint union of countably many open intervals ]α k , β k [. Setting s k = x -1 (α k ) and t k = x -1 (β k ), we obtain k≥1 ]s k , t k [ = ]0, t[ \T 0 (t).
Thus, (3.19) and (3.18) yield

x(t) -x(0) = k≥1 (x(t k ) -x(s k )) = k≥1 t k s k ẋ(s)ds = k≥1 ]s k ,t k [ f (x(s))ds = ]0,t[\T 0 (t) f (x(s))ds = t 0 f (x(s))ds
showing that x(•) is a Carathéodory solution. This completes the proof.

We are now ready to state the main result of this section. (ii) There exist a positive atomless measure µ supported on the set f -1 (0), a countable set of points S ⊆ f -1 (0), and a map Φ : Ω * → {-1, 1} as in (Q1)-(Q3) such that S coincides with the corresponding semigroup constructed at (3.13)- (3.14).

Proof of the implication (ii)=⇒(i). Given the measure µ, the set S and the map Φ, we will show that the map S : R × R + → R constructed in (3.13)-(3.14) is indeed a semigroup compatible with the ODE (1.1).

1. Let x 0 ∈ R be given. We first show that the map t → x(t) = S t (x 0 ) provides a solution to the Cauchy problem (1.1)-(1.2). Various cases must be considered.

CASE 1. If x 0 / ∈ i I + i ∪ i I - i then S t (x 0 ) = x 0 .
In this case we need to show that f (x 0 ) = 0. If, on the contrary, f (x 0 ) = 0, then by (A2) we would have either

0 < δ ≤ f (x) ≤ M (3.20) for all x ∈ N ε . = ]x 0 , x 0 + ε], or else -M ≤ f (x) ≤ -δ < 0 (3.21)
for all x ∈ N ε . = [x 0 -ε, x 0 [, for a suitably small ε > 0.

We now recall that the measure µ and the countable set S in (Q1)-(Q2) satisfy

Supp(µ) ∪ S ⊆ f -1 (0).
Since the set f -1 (0) is closed and does not contain x 0 , by possibly choosing a smaller ε > 0 we can assume that

S ∩ N ε = ∅, µ(N ε ) = 0. (3.22)
Together, (3.20)-(3.22) imply that either a strictly increasing trajectory or a strictly decreasing trajectory starts from x 0 . Hence

x 0 ∈ i I + i ∪ i I - i , against the assumption. CASE 2.
Next, assume that x 0 ∈ I + i \ j I - j , for some i ∈ I + and

I + i = [α i , β i [. Then the trajectory t → x(t) = S + t (x 0
) is implicitly defined by (3.15). By Lemma 3.1, we already know that x(•) is a Carathéodory solution to the ODE (1.1) for t ∈ [0, τ (x 0 )].

It remains to show that, in the case τ (x 0 ) < +∞, the function x(t) = β i is still a solution of (1.1) for all t ∈ [τ (x 0 ), +∞[ . Of course, this will be the case iff f (β i ) = 0.

Assume that, on the contrary, f (β i ) = 0. Since f -1 (0) is closed, there exists a neighborhood N of β i such that (3.22) holds. Moreover, since f (β i -) ≥ 0, by (A2) it follows f (β i +) > 0. This implies that, for some ε > 0 small enough, the inequalities (3.20) hold for all x ∈ N ε . = ]β i , β i + ε]. Moreover, (3.22) holds as well. As a consequence, there exists a strictly increasing trajectory starting at β i . This yields a contradiction with the maximality of the interval

I + i . CASE 3. If x 0 ∈ I - i \ j I + j ,
for some i ∈ I -, then the same arguments used in Case 2 show that t → x(t) = S - t (x 0 ) is a Carathéodory solution. (3.14) we are back to Case 2 or Case 3.

CASE 4. If x 0 ∈ i I - i ∩ i I + i , then by

2.

It remains to prove that the semigroup property S s (S t (x 0 )) = S s+t (x 0 ) is satisfied.

Referring to the above four cases, in Case 1 this is trivial, because S t (x 0 ) = x 0 for all t ≥ 0.

In Case 2, as long as t + s ≤ τ + (x 0 ), the semigroup property is a straightforward consequence of the identity

t + s = µ([x 0 , x(t + s)]) + x(t+s) x 0 dy f + (y) = µ([x 0 , x(t)]) + µ([x(t), x(t + s)]) + x(t) x 0 dy f + (y) + x(t+s) x(t) dy f + (y)
.

On the other hand, for 0 < t < τ (x 0 ) ≤ t + s, the identity

τ + (S t (x 0 )) = τ + (x 0 ) -t implies S t+s (x 0 ) = β i = S s (S t (x 0 )). (3.23)
Finally, if t ≥ τ + (x 0 ), then again (3.23) trivially holds.

The remaining Cases 3 and 4 are entirely similar. This concludes the proof of the implication (ii)=⇒(i).

Proof of the implication (i)=⇒(ii). Assuming that S : R × R + → R is a deterministic semigroup compatible with the ODE (1.1), in the remaining part of the proof we shall construct a measure µ, a countable set S, and a map Φ so that S coincides with the corresponding semigroup defined at (3.13)-(3.14). ) is a domain of increasing dynamics if, for every x 0 , x ∈ J with x 0 < x there exists t > 0 such that x = S t x 0 .

In analogy with

Similarly, we say that an interval J =]a, b] or J = ]a, b[ (open to the left) is a domain of decreasing dynamics if, for every x 0 , x ∈ J with x < x 0 there exists t > 0 such that x = S t x 0 .

We observe that, if two domains of increasing dynamics J, J have nonempty intersection, then the union J ∪ J is also an interval of increasing dynamics. We can thus partition the real line as

R = Ω + S ∪ Ω - S ∪ Ω 0 S (3.24)
where

• Ω + S = j∈J + J + j is the union of countably many disjoint intervals J + j = [a j , b j [ or J + j = ]a j , b j [ open to the right, where the dynamics is increasing and b j can not be crossed from the left, i.e. S t (b j -ε) ≤ b j for all t ≥ 0, ε ∈]0, b j -a j [.

• Ω - S = j∈J -J - j is the union of countably many disjoint intervals J - j = ]c j , d j ] or J - j = ]c j , d j [ open to the left, where the dynamics is decreasing and c j can not be crossed from the right, i.e. S t (c j + ε) ≥ c j for all t ≥ 0, ε ∈]0, d j -c j [.

• Ω 0 S ⊆ f -1 (0)
is the set of points x 0 such that S t (x 0 ) = x 0 for all t > 0.

4. We shall construct the measure µ separately on each interval J + j , J - j . As in the proof of Lemma 3.1, we define a positive, Borel measure on J + j by setting for every compact subinterval

[x 0 , x] ⊂ J + j µ [x 0 , x] . = meas t ∈ [0, τ ] ; f (S t (x 0 )) = 0 (3.25)
where τ > 0 is such that x = S τ (x 0 ). It is clear that µ is supported on f -1 (0). By the semigroup property of S, the map t → S t (x 0 ) is strictly increasing. Thus, as in the proof of Lemma 3.1, the measure µ is also atomless. Similarly, one can define the measure µ on J - j . Next, we define the countable set

S . = a j , b j : j ∈ J + } ∪ c j , d j : j ∈ J -} ∩ Ω 0 S (3.26)
containing all endpoints of all intervals J + j , J - j whose trajectory remains constant. Finally, the discrete function Φ : Ω * → {-1, 1} is defined as follows. Let x 0 ∈ Ω * . Three cases are considered.

• If x 0 = a j for some half-open interval J + j = [a j , b j [ , then we set Φ(x 0 ) = 1.

• If x 0 = d j for some half-open interval J - j = ]c j , d j ] , then we set Φ(x 0 ) = -1.
• In all other cases, the choice of Φ(x 0 ) is immaterial, because it has no effect on the definition of the semigroup. To fix the ideas, we may thus set Φ(x 0 ) = 1.

Recalling Definition 3.1, let I + i , i ∈ I + , and I - i , i ∈ I -, be respectively the domains of increase and the domains of decrease corresponding to µ, S and Φ. To complete the proof, we first show that

{]α i , β i [: i ∈ I + } = {]a j , b j [: j ∈ J + } and {]γ i , δ i [: i ∈ I -} = {]c j , d j [: j ∈ J -} (3.27)
For any j ∈ J + , by Lemma 3.1 and (3.25)-(3.26), one has that ]a j , b j [ satisfies (3.5) and this implies that ]a j , b j [⊂ I + i for some i ∈ I + . Moreover, if a j ∈ J + j then a j / ∈ Ω 0 S and µ([a j , a j + ε[) + a j +ε

a j 1 f + (y) dy = t ε < ∞ with S tε (a j ) = a j + ε for 0 < ε < b j -a j .
Hence, a j ∈ I + i and this yields J + j ⊆ I + i . Furthermore, we prove that b j = β i , a j = α i and this implies ]α i , β i [ = ]a j , b j [. If b j < β i then b j is reachable from the left and the semigroup property of S implies that b j ∈ Ω 0 S . In particular, b j ∈ S ∩ I + i and this yields a contradiction. Now assume that α i < a j . Two cases are considered:

• If a j / ∈ J + j then a j ∈ Ω 0 S since Ω - S ∩ I + i = ∅. Thus, a j ∈ S ∩ I + i and this yields a contradiction.

• Otherwise, a j ∈ J + j can not be reached from the left. Thus, either µ([a j -ε, a j ]) = +∞ for some ε ∈]0, a j -α i [ or there exists b j ∈ Ω 0 S ∩ I + i . Both cases yield a contradiction.

Vice-versa, for any i ∈ I + , by the definition 3.2 and Lemma 3.1, one has that

Ω - S int(Ω 0 S ) ∩ ]α i , β i [ = ∅.
In particular, ]a j , b j [∩]α i , β i [ = ∅ for some j ∈ J + . Since ]a j , b j [⊆]α i , β i [ for some i ∈ I + and {I k } k∈I + are disjoint, we have that ]a j , b j [=]α i , β i [, and the first equality of (3.27) holds.

Similarly, one can show that the second equality of (3.27). Finally, we need to show that

(i) If α i ∈ I + i \J + j and ]α i , β i [=]a j , b j [ for some j ∈ J + then α i = d k ∈ Ω * ∩ J - k for some k ∈ J -. (ii) If δ i ∈ I - i \J - j and ]γ i , δ i [=]c j , d j [ for some j ∈ J -then δ i = a k ∈ Ω * ∩ J + k for some k ∈ J + .
Since (i) and (ii) are entirely similar, let us prove (i). Observe that α i = a j can not be in Ω 0 S , it holds that α i = d k for some k ∈ J -. On the other hand, one can follow the above argument to show that J - k ⊆ I -for some ∈ I -. Thus, α i = d k ∈ I + i ∩ I -⊆ Ω * and this yields (i).

A Markov process whose sample paths solve the ODE

In this section, we initiate the study of Markov semigroups whose sample paths satisfy the ODE (1.1) with probability one. Our eventual goal is to show that each of these random semigroups can be obtained starting with a deterministic semigroup and performing the two modifications described at (Q4)-(Q5) in the Introduction. In this section, we show that a Markov process can be uniquely determined by the ODE (1.1) and the assignments (Q1)-(Q2) and (Q4)-(Q5), namely:

• A positive, atomless Radon measure supported on f -1 (0).

• A countable set S ⊆ f -1 (0) where the dynamics stops.

• A countable set S * ⊆ f -1 (0) and, for each y j ∈ S * , a number λ j > 0 characterizing the random exponential waiting time, when the trajectories reach the point y j ∈ S * .

• A map Θ : Ω * → [0, 1] determining the probability of moving to the right or to the left, from an initial point z k ∈ Ω * .

We start by selecting an underlying probability space W such that, as ω ∈ W, the countably many random variables Y j (ω) ∈ R + and Z k (ω) ∈ {-1, 1} are independent, with distributions Prob.{Y j > s} = e -λ j s for all s > 0, Prob.

{Z k = 1} = Θ(z k ). (4.1)
Next, we recall that, given the measure µ and the countable set S, as in Section 3 one can uniquely determine the sets

Ω + = i∈I + I + i , Ω -= i∈I - I - i (4.2)
consisting of countable unions of disjoint intervals where the dynamics can increase or decrease, respectively. For x 0 ∈ Ω + , a trajectory t → S + t (x 0 ) was defined at (3.9)-(3.10), while for x 0 ∈ Ω -, a trajectory t → S - t (x 0 ) was defined at (3.11)-(3.12).

To construct a Markov process with sample paths t → X(t, ω) satisfying (1.1), for every t > 0 we need to define the transition probabilities

P t (x 0 , A) = Prob. X(t, ω) ∈ A X(0, ω) = x 0 ,
for any initial point x 0 ∈ R and any Borel set A ⊂ R. Recalling our construction of a deterministic flow at (3.13)- (3.14), this can be done as follows.

(i) If x 0 / ∈ Ω + ∪ Ω -, then X(t, x 0 , ω) = x 0 for every t ≥ 0 and ω ∈ W. Hence

P t (x 0 , {x 0 }) = 1 for all t ≥ 0. (4.3)
In other words, all trajectories starting at x 0 remain constant.

(ii) If x 0 ∈ Ω + \ Ω -, a random trajectory starting at x 0 will have the form

X(t, x 0 , ω) = S + T + (t,x 0 ,ω) (x 0 ) , (4.4)
where the time T + along the trajectory is a random variable with distribution

Prob. T + (t, x 0 , ω) < s = Prob.    s + y j ∈S * ∩[x 0 , S + s (x 0 )] Y j (ω) > t    . (4.5)
Note that (4.5) accounts for the (possibly countably many) waiting times when the trajectory crosses one of the points y j ∈ S * . The transition probabilities are thus given by P t x 0 , ] -∞, x 0 [ = 0,

P t x 0 , [x 0 , S + s (x 0 )] = Prob.    s + y j ∈S * ∩[x 0 , S + s (x 0 )] Y j (ω) ≥ t    . (4.6)
(iii) Similarly, for an initial state x 0 ∈ Ω -\ Ω + , a random trajectory starting at x 0 will have the form

X(t, x 0 , ω) = S - T -(t,x 0 ,ω) (x 0 ) , (4.7)
where the time T -along the trajectory is a random variable with distribution

Prob. T -(t, x 0 , ω) < s = Prob.    s + y j ∈S * ∩[S - s (x 0 ), x 0 ] Y j (ω) > t    . (4.8)
The transition probabilities are thus given by

P t x 0 , ]x 0 , +∞[ = 0, P t x 0 , [S - s (x 0 ), x 0 ] = Prob.    s + y j ∈S * ∩[S - s (x 0 ), x 0 ] Y j (ω) ≥ t    . (4.9)
(iv) To complete the definition, it remains to define the transition probabilities in the case

x 0 ∈ Ω + ∩ Ω -⊆ Ω * .
In this case, by construction we have x 0 = z k for some k. We then define the random variable X(t, x 0 , ω) by setting

X(t, x 0 , ω) =    S + T + (t,x 0 ,ω) (x 0 ) if Z k (ω) = 1 , S - T -(t,x 0 ,ω) (x 0 ) if Z k (ω) = -1 . (4.10)
By (4.1), its distribution satisfies

P t (x 0 , A) = Θ(x 0 )•Prob. S + T + (t,x 0 ,ω) ∈ A +(1-Θ(x 0 ))•Prob. S - T -(t,x 0 ,ω) ∈ A (4.11)
for every Borel set A ⊆ R.

From the above construction it is clear that, in all cases (i)-(iv), all sample paths t → X(t, x 0 , ω) are Carathéodory solutions to the Cauchy problem (1.1)-(1.2). Indeed, we are only adding a countable number of waiting times, when the random trajectories reach one of the points y j ∈ S * ⊆ f -1 (0).

The next result shows that the above transition probabilities define a Markov semigroup.

Proposition 4.1 The transition probability kernels (P t ) t≥0 in (4.3), (4.6), (4.9), (4.11) define a continuous Markov process. Indeed, they satisfy the Chapman-Kolmogorov equation

P t (z, A)P s (x 0 , dz) = P s+t (x 0 , A) (4.12)
for all s, t > 0, x 0 ∈ R and every Borel set A ⊆ R.

Proof. 1. In Case (i) the conclusion is trivially true. We thus focus on Case (ii). Suppose that x 0 ∈ I + i for some i ∈ I + . Observe that X(s, x 0 , ω) = z . = S + η (x 0 ) if and only if

η + y j ∈S * ∩[x 0 , S + η (x 0 )[ Y j (ω) ≤ s ≤ η + y j ∈S * ∩[x 0 , S + η (x 0 )] Y j (ω) (4.13)
This leads to two different expressions, depending on whether z ∈ S * or z / ∈ S * . We claim that, for any Borel set A ⊂ R,

P t+s (x 0 , A) = y j ∈S * ∩[x 0 ,S + s (x 0 )] P s x 0 , {y j } • P t (y j , A) + z∈[x 0 ,S + s (x 0 )]\S * P s (x 0 , dz)P t (z, A).
(4.14) It is sufficient to prove (4.14) assuming x 0 ∈ I + i and A = [x 0 , b] ⊆ I + i , where I + i is one of the intervals in (4.2) where the dynamics is increasing. Consider the times η j , η z ≥ 0 such that y j = S + η j (x 0 ) and z = S + ηz (x 0 ).

• The time when the random trajectory t → X(t, x 0 , ω) crosses z is given by

T + z (ω) = η z + y j ∈S * ∩[x 0 ,z]
Y j (ω).

• The times when the random trajectory t → X(t, x 0 , ω) reaches y j , and then leaves y j , are given by

T - j (ω) = η j + y k ∈S * ∩[x 0 ,y j [ Y k (ω), T + j (ω) = η j + y k ∈S * ∩[x 0 ,y j ] Y k (ω).
In view of the above definition, the left hand side of (4.14) can be written as

P t+s x 0 , [x 0 , b] = Prob. T + b (ω) ≥ t + s = Prob. T + b (ω) ≥ t+s and X(s, x 0 , ω) ∈ S * +Prob. T + b (ω) ≥ t+s and X(s, x 0 , ω) / ∈ S * = y j ∈S * ∩[x 0 ,S + s (x 0 )] Prob. T + b (ω) ≥ t + s and X(s, x 0 , ω) = y j + Prob. T + b (ω) ≥ t + s and X(s, x 0 , ω) / ∈ S * = I + II. (4.15)
2. For any y j ∈ S * ∩ [x 0 , S + s (x 0 )], we have

Prob. T + b (ω) ≥ t + s and X(s, x 0 , ω) = y j = Prob. T + b (ω) ≥ t + s and T - j (ω) ≤ s ≤ T + j (ω) = s 0 d dr 1 Prob. T - j (ω) ∈ [0, r 1 ] ∞ s-r 1 d dr 2 Prob. Y j (ω) ∈ [0, r 2 ] •Prob. t + s -r 1 -r 2 ≤ T + b (ω) -T + j (ω) dr 2 dr 1 = s 0 d dr 1 Prob. T - j (ω) ∈ [0, r 1 ] • ∞ s-r 1 λ j e -λ j r 2 • Prob. t + s -r 1 -r 2 ≤ T + b (ω) -T + j (ω) dr 2 dr 1 .
Performing the change of variable τ = r 2 -(s -r 1 ), one obtains

Prob. T + b (ω) ≥ t + s and X(s, x 0 , ω) = y j = s 0 d dr 1 Prob. T - j (ω) ∈ [0, r 1 ] ∞ 0 λ j e -λ j (τ +s-r 1 } • Prob. t -τ ≤ T + b -T + j dτ dr 1 = s 0 d dr 1 Prob. T - j (ω) ∈ [0, r 1 ] • e -λ j (s-r 1 ) dr 1 • ∞ 0 λ j e -λ j τ • Prob. t -τ ≤ T + b (ω) -T + j (ω) dτ = s 0 d dr 1 Prob. T - j (ω) ∈ [0, r 1 ] • Prob. Y j (ω) ≥ s -r 1 dr 1 • ∞ 0 d dτ Prob. Y j (ω) ∈ [0, τ ] • Prob. t -τ ≤ T + b (ω) -T + j (ω) dτ = Prob. s ∈ T - j (ω), T + j (ω) • Prob. t ≤ T + b (ω) -T - j (ω) = P s x 0 , {y j } • P t y j , [x 0 , b] .
Summing over all y j ∈ S * we thus obtain

I = y j ∈S * ∩[x 0 ,S + s (x 0 )] P s (x 0 , y j ) • P t y j , [x 0 , b] . (4.16)
3. Next, for a fixed integer N ≥ 1, we consider the following partition of [x 0 , b]

z 0 . = x 0 , z i . = sup z ∈ [x 0 , b] : P t z, [x 0 , b] ≥ 1 - i N , (4.17)
and define the open intervals

J i . = z i-1 , z i , i ∈ {1, . . . , N }.
Notice that some of these intervals J i may be empty. For each i ∈ {1, . . . , N }, we estimate

Prob. t + s ≤ T + b (ω) X(s, x 0 , ω) ∈ J i \ S * ≤ sup z∈J i S * Prob. t + s ≤ T + b (ω) X(s, x 0 , ω) = z = sup z∈J i \S * Prob. t + s ≤ T + b (ω) s = T + z (ω) = sup z∈J i \S * Prob. T + b (ω) -T + z (ω) ≥ t = sup z∈J i \S * P t z, [x 0 , b] ≤ inf z∈J i \S * P t z, [x 0 , b] + 1 N .
An entirely similar argument yields

Prob. t + s ≤ T + b (ω) X(s, x 0 , ω) ∈ J i \ S * ≥ sup z∈J i \S * P t (z, [x 0 , b]) - 1 N .
Using the above identities we obtain

P t z, [x 0 , b] P s (x 0 , dz) = P t x 0 , [x 0 , b] • P s x 0 , {x 0 } + ]x 0 ,b] P t z, [x 0 , b] P s (x 0 , dz) = (1 -Θ(x 0 )) • Prob.{Y j ≥ t} + Θ(x 0 ) • Prob. S + T + (t,x 0 ,ω) ∈ [x 0 , b] • Prob. {Y j ≥ s} +Θ(x 0 ) • ]x 0 ,b] Prob. S + T + (t,z,ω) ∈ [x 0 , b] • d dz Prob. S + T + (s,x 0 ,ω) ∈ [x 0 , z] dz = (1 -Θ(x 0 )) • Prob.{Y j ≥ t + s} +Θ(x 0 ) • Prob. S + T + (t,x 0 ,ω) ∈ [x 0 , b] • Prob. S + T + (s,x 0 ,ω) = x 0 +Θ(x 0 ) • ]x 0 ,b] Prob. S + T + (t,z,ω) ∈ [x 0 , b] • d dz Prob. S + T + (s,x 0 ,ω) ∈ [x 0 , z] dz = (1 -Θ(x 0 )) • Prob. S - T -(t+s,x 0 ,ω) = x 0 + Θ(x 0 ) • Prob. S + T + (t+s,x 0 ,ω) ∈ [x 0 , b] = P t+s x 0 , [x 0 , b] .

Characterization of Markov semigroups compatible with the ODE

The goal of the present section is to describe the most general Markov semigroup whose sample paths are all solutions to the ODE (1.1). Our main result shows that all of these Markov semigroups are of the form considered in Proposition 4.1. Namely, they are all obtained starting with a deterministic semigroup and performing two modifications: (i) adding a countable number of random waiting times at points y j ∈ f -1 (0), each with a Poisson distribution, and (ii) assigning the probabilities of moving upwards or downwards, at isolated points from where both an increasing and a decreasing solution can initiate. (II) There exist: (i) a positive, atomless Borel measure µ supported on f -1 (0), (ii) a countable set S ⊆ f -1 (0) of stationary points, (iii) a countable set S * = {y j : j ≥ 1} ⊆ f -1 (0) and corresponding numbers λ j > 0 determining the Poisson waiting times, and (iv) a map Θ : Ω * → [0, 1], such that the transition kernels P t (x 0 , A) = Prob.{X(t, x 0 , ω) ∈ A} coincide with the corresponding ones constructed at (4.3), (4.6), (4.9), (4.11).

Proof. The implication (II)=⇒(I) was proved in Proposition 4.1. Here we need to prove (I)=⇒(II).

1. We begin by defining two subsets of f -1 (0)

Ω 0 X . = x 0 ; Prob.{X(1, x 0 , ω) = x 0 } = 1 , (5.1)
S * . = x 0 ; 0 < Prob.{X(1, x 0 , ω) = x 0 } < 1 . (5.2)
Here Ω 0 X is the set of points where the motion stops forever, while S * contains points where the motion stops for a random time, then starts again. By the Markov property and the fact that all solutions of (1.1) are monotone, x 0 ∈ Ω 0 X implies X(t, x 0 , ω) = x 0 for all t ≥ 0 and a.e. ω. We claim that for each x 0 ∈ S * , there holds Prob.{X(t, x 0 , ω) = x 0 } = e -λt for all t ≥ 0 (5.3) with λ . = -log Prob.{X(1, x 0 , ω) = x 0 } < ∞. Indeed, for t ≥ 0, the map

t → g(t) = log Prob.{X(t, x 0 , ω) = x 0 } ∈ ] -∞, 0]
is nonincreasing. By the Markov property, it satisfies

g(0) = 0, g(t + s) = g(t) + g(s)
for all t, s > 0.

Therefore, g(q) = -λ q for some λ > 0 and all positive rational numbers q ∈ Q + . Since g is monotone, we conclude that g is continuous on [0, +∞[ and hence

Prob.{X(t, x 0 , ω) = x 0 } = e g(t) = e -λt for all t ∈ [0, +∞[.

2.

Next, we need to identify the maximal intervals where the random dynamics is increasing or decreasing. We observe that, if two intervals of increasing random dynamics have nonempty intersection, then their union is still a domain of increasing random dynamics. We can thus define a countable number of maximal open intervals

J + k =]a k , b k [, k ∈ J +
where the random dynamics is increasing, and a countable number of maximal open intervals

J - k =]c k , d k [, k ∈ J -
where the random dynamics is decreasing. Recalling (5.1), we shall consider the countable set

S = a k , b k : k ∈ J + } ∪ c k , d k : k ∈ J -} ∩ Ω 0 X . (5.6)
Next, we consider the set Ω * of isolated points from which both a decreasing and an increasing trajectory can initiate. For z k ∈ Ω * \ S, we define the probability of moving upwards as Θ(z k ) . = Prob. X(t, z k , ω) > z k for some t > 0 .

(5.7)

Of course, starting from z k , the probability of moving downwards is thus 1 -Θ(z k ). for some τ > 0. This implies Prob.{X(kτ, x, ω) < y} ≤ δ k for all k ≥ 1.

(5.9)

Call T = T xy > 0 the random time needed for a solution starting at x to reach y. By (5.9) it follows Prob.{T > kτ } ≤ δ k .

(5.10) By (5.10), the probability distribution T = T xy has moments of all orders. In particular, its mean and its variance are finite.

As a consequence for every x ≤ z < z ≤ y the random variable T zz has moments of all orders. Its expected value and its variance satisfy From (5.11), it follows that for every finite subset S * 1 of S * ∩ [x, y]

E[T zz ] ≤ E[T xy ], Var.(T zz ) ≤ Var.(T xy ). ( 5
y j ∈S * 1 1 λ j = y j ∈S * 1 E Y j ≤ E[T xy ] < + ∞.
In particular,

#{y j ∈ S * ∩ [x, y] : λ j ≤ n} ≤ n • E[T xy ] for all n ≥ 1,
and this shows that the set S * of points where a random waiting time occurs is at most countable. Thus, we can write S * ∩ J = {y 1 , y 2 , . . .} and

z≤y j <z 1 λ j = z≤y j <z E Y j ≤ E[T zz ].
(5.12)

4.

To help the reader, we provide here an outline the remaining steps of the proof. Let J =]a, b[ or J = [a, b[ be a maximal domain of increasing random dynamics and {y 1 , y 2 , . . .} = J ∩ S * be the set of points where the trajectories stop for a random time Y j , then start again. We can then define a new Markov semigroup by removing these waiting times. More precisely, for each n ≥ 1, we define a Markov semigroup S (n) whose trajectories t → X (n) (t, x 0 , ω) satisfy

X (n) (τ n (t, x 0 , ω), x 0 , ω) = X(t, x 0 , ω),
Otherwise, if x 0 ≤ y 1 , then we consider the sets

A 1 = A∩]a, y 1 [ , A 2 = A ∩ [y 1 , b[ , and compute P (1)
t (z, A)P (1) s (x 0 , dz)

= P t (z, A 1 )P s (x 0 , dz) + P t (z, A 2 ) • ∞ 0 P s+τ (x 0 , dz) • λ 1 e -λ 1 τ dτ = P t+s (x 0 , A 1 ) + ∞ 0 P t (z, A 2 ) • P s+τ (x 0 , dz) • λ 1 e -λ 1 τ dτ = P t+s (x 0 , A 1 ) + ∞ 0 P t+s+τ (x 0 , A 2 ) • λ 1 e -λ 1 τ dτ = P (1)
t+s (x 0 , A).

Hence, the process S (1) with sample paths t → X (1) (t, x 0 , ω) is a Markov semigroup.

6. By induction, for each n ≥ 1, we consider the process S (n) obtained from S (n-1) by removing the Poisson waiting time at the point y n ∈ J ∩ S * . By the previous argument, every S (n) is a Markov semigroup. Conversely, one can recover the original Markov semigroup S starting with S (n) and adding the Poisson waiting times Y 1 , . . . , Y n at the points y 1 , . . . , y n . If the set J ∩ S * contains N points, the induction argument is concluded N steps. Otherwise, since the sequence of trajectories t → X (n) (t, x 0 , ω) is monotone increasing and bounded for t in bounded sets, for every ω there exists the limit X (n) (t, x 0 , ω) → X(t, x 0 , ω), uniformly for t in bounded sets. By part (iii) of Theorem 2.1, each limit trajectory t → X(t, x 0 , ω) is still a solution of the ODE (1.1).

In the next step we will prove that this limit process is deterministic. Namely Var. X(t, x 0 , ω) = 0, (5.13)

for every x 0 ∈ J and t > 0.

7. Given x 0 < x ∈ J, let us define

   T x 0 x n (ω) . = inf t > 0 ; X (n) (t, x 0 , ω) ≥ x T x 0 x (ω) . = inf t > 0 ; X(t, x 0 , ω) ≥ x
the random times needed to reach x, for a trajectory starting at x 0 , having removed respectively the first n waiting times at y 1 , . . . , y n or all waiting times y j ∈ J ∩ S * .

Let ε 0 > 0 be such that E[ T x 0 x ] > ε 0 . By (5.12) we can choose n large enough so that j>n, x 0 ≤y j < x 1 λ j < ε 0 .

(5.14)

We now consider the expected values of these random times. By construction the map y → E T x 0 y n is nondecreasing, and has upward jumps in the amount 1 λ j at each point y j , with j > n. By (5.14), we can introduce a partition

x = x 0 < x 1 < • • • < x ν = x
Since ε 0 > 0 can be chosen arbitrarily small, we conclude that the variance of T x 0 x is zero. Hence, the limit process is deterministic.

8. We now define S t x 0 . = lim n→∞ E X (n) (t, x 0 , ω) .

(5.19)

The existence of the limit follows trivially by monotonicity. Since the variance of the random variables X (n) goes to zero, again by (iii) in Theorem 2.1 it follows that each trajectory t → S t x 0 is a Carathéodory solution to (1.1).

We claim that S is a deterministic semigroup. Toward this goal, we first observe that the maps t → S t x 0 , x 0 → S t x 0 are both Lipschitz, and strictly increasing (as long as S t x 0 < b). To prove the semigroup identity S s ( S t x 0 ) = S t+s x 0 , (5.20) set x 1 = S t x 0 and let ε > 0 be given. Choose δ > 0 such that

S s (x 1 -δ) > S s x 1 -ε , S s (x 1 + δ) < S s x 1 + ε. (5.21) We now have lim n→∞ Prob. X (n) (t, x 0 , ω) ∈ [x 1 -δ, x 1 + δ] = 1 .
By (5.21) and a comparison argument, this implies

lim n→∞ Prob. X (n) (t + s, x 0 , ω) ∈ [ S s x 1 -ε, S s x 1 + ε] = 1 .
Since ε > 0 was arbitrary, this proves the semigroup property (5.20).

As a consequence, by Theorem 3.1, there exists a positive atomless measure µ supported on J ∩ f -1 (0) such that the trajectories of the semigroup are characterized by the formula (3.10).

Of course, the above construction of a measure µ can be repeated on every maximal interval J of increasing or decreasing dynamics.

9.

As in Proposition 4.1, given the sets S, S * ⊆ f -1 (0), the positive, atomless measure µ on f -1 (0), and the maps Λ : S * → R + , Θ : Ω * → [0, 1], we construct a unique Markov semigroup S, with transition probabilities given at (4.3), (4.6), (4.9), (4.11). Recalling Definition 3.1, let I + i , i ∈ I + , and I - i , i ∈ I -, be respectively the domains of increase and the domains of decrease corresponding to µ and S. For any k ∈ J + and x 0 ∈ J + k with

J + k =]a k , b k [ or J + k = [a k , b k [, the map [0, T b k [ t → S t
x 0 is strictly increasing and lim t→T b k S t x 0 = b k for some T b k > 0. Thus, J + k is an strictly increasing domain associated to S and this implies that

J + k ⊆ I + i
for some i ∈ I + .

Similarly, for every h ∈ J -it holds that J - h ⊆ I - j for some i ∈ I -. Thus,

k∈J + J + k ⊆ i∈I + I + i and h∈J - J - h ⊆ i∈I - I - i .
In the remainder of the proof, we will show that the given Markov semigroup S coincides with the semigroup S constructed in Proposition 4.1. In other words, for every x 0 ∈ R, t > 0 and any Borel set A ⊂ R, the transition probabilities coincide: P t (x 0 , A) = P t (x 0 , A) . = Prob. S t x 0 ∈ A .

(5.22) Four cases must be considered:

(i) x 0 / ∈ i∈I + I + i ∪ i∈I -I - i ; (ii) x 0 ∈ i∈I + I + i \ i∈I -I - i ; (iii) x 0 ∈ i∈I -I - i \ i∈I + I + i ; (iv) x 0 ∈ i∈I -I - i ∩ i∈I + I + i ⊆ Ω * .
Case (i) is trivial. We thus focus on Case (ii). Assume that x 0 ∈ I + i \ j I - j for some i ∈ I + . In this case, we only need to prove (5.22) for A = [x 0 , S s (x 0 )] with s > 0. From the previous construction in Proposition 4.1, it holds that P t x 0 , [x 0 , S s (x 0 )] = Prob. • Otherwise, if x 0 / ∈ k∈J + J + k then lim t→∞ Prob.{X(t, x 0 , ω) ≤ x} = 1 for all x > x 0 .

(5.24) and this implies that Prob. S t x 0 = x 0 = 1 and x 0 ∈ Ω 0 X .

(5.25) Indeed, assume by a contradiction that there exists x > x 0 such that Prob.{X( t, x 0 , ω) ≤ x} = δ < 1 for some t > 0. By the Markov property of X, we have Prob.{X(k t, x 0 , ω) ≤ x} ≤ δ k for all k ∈ Z + .

In particular, the monotone increasing property of the maps t → X(t, x 0 , ω) implies that lim t→∞ Prob.{X( t, x 0 , ω) ≤ x} = 0. Hence, x 0 is in a domain of increasing random dynamics and this yields a contradiction.

On the other hand, since x 0 / ∈ k∈J + J + k j I - j and h∈J -J - h ⊆ i∈I -I - i , one has that x 0 ∈ a k , b k : k ∈ J + } ∪ c k , d k : k ∈ J -} . Thus, (5.25) and (4.3) implies that x 0 ∈ S and P t x 0 , {x 0 } = 1 = P t x 0 , {x 0 } .

Similarly, one can prove (5.22) for x 0 in an interval of decreasing dynamics. This establishes the identity (5.22) for all initial points x 0 ∈ R, completing the proof of the theorem.

1 1 -

 1 α . In addition, there is a one-parameter family of Markovian flows. Indeed, for each 0 < λ < ∞, one can consider the random time T with Poisson distribution Prob.{T > s} = e -λs .

  If ]a, b[ and ]a , b [ are two intervals of increase having non-empty intersection, then their union ]a, b[ ∪ ]a , b [ is also an interval of increase. We can thus identify countably many, disjoint maximal intervals ]α i , β i [, i ∈ I + of increase. Similarly, we can identify countably many disjoint maximal intervals ]γ i , δ i [, i ∈ I -of decrease. It remains to analyze what happens at the endpoints of these intervals.

Lemma 3 . 1

 31 Let x : [0, τ ] → R be a strictly increasing map defined on some interval [0, τ ]. Then x(•) is a Carathéodory solution to the Cauchy problem (1.1)-(1.

Theorem 3 . 1

 31 Let f : R → R satisfy the assumptions (A1)-(A2). The following statements are equivalent. (i) The map S : R × R + → R is a deterministic semigroup compatible with the ODE (1.1).

Definition 3 . 2

 32 Definition 3.1, we introduce: Given the semigroup S : R × R + → R, we say that an interval J = [a, b[ or J = ]a, b[ (open to the right

Theorem 5 . 1

 51 Let f be a function satisfying (A1)-(A2). The following statements are equivalent.(I) The random variables X(t, x 0 , ω) yield a Markov process whose sample paths are solutions to the ODE (1.1)-(1.2).

Definition 5 . 1

 51 We say that an interval J = [a, b[ or J = ]a, b[ (open to the right) is a domain of increasing random dynamics if for every x 0 , x ∈ J with x 0 < x, one has lim t→∞ Prob. X(t, x 0 , ω) > x = 1. (5.4) Similarly, we say that an interval J =]a, b] or J = ]a, b[ (open to the left) is a domain of decreasing random dynamics if, for every x 0 , x ∈ J with x < x 0 , one has lim t→∞ Prob. X(t, x 0 , ω) < x = 1. (5.5)

3 .

 3 Consider a maximal domain of increasing random dynamics, say J = ]a, b[ or J = [a, b[. By definition, for any a < x < y < b we have that Prob.{X(τ, x, ω) < y} .

. 11 )

 11 Now consider the points y j ∈ [x, y] where a random waiting time Y j occurs. The Markov property implies that Y j has a Poisson distribution as in (4.1), with expected value E Y j = 1 λ j .

•

  j ∈S * ∩[x 0 , Ss(x 0 )] Y j (ω) ≥ t If x 0 ∈ J + k for some k ∈ J + then one hasP t x 0 , [x 0 , S s (x 0 )] = Prob. X(t, x 0 , ω) ∈ [x 0 , S s (x 0 )] = Prob. X(τ (t, x 0 , ω), x 0 , ω) ∈ [x 0 , X(s, x 0 , ω)] = Prob. (τ (t, x 0 , ω) ≤ s) = Prob. j ∈S * ∩[x 0 , Ss(x 0 )] Y j (ω) ≥ t    , where τ (t, x 0 , ω) . = t -meas r ∈ [0, t] ; X(r, x 0 , ω) ∈ S * .This yields (5.22) for A = [x 0 , S s (x 0 )].

Finally, consider x 0

 0 ∈ I + i ∩ I - i \S, for some i ∈ I + and i ∈ I -. It is sufficient to verify(5.22) for A = [x 0 , b], with b ∈ I + i . The case A = [c, x 0 ], c ∈ I - i is entirely similar. If x 0 / ∈ S * then Prob. {X(1, x 0 , ω) = x 0 } = 0 and Prob.{X(1, x 0 , ω) > x 0 } = Θ(x 0 )and this impliesProb. {X(t, x 0 , ω) ∈ [x 0 , b]} = Prob. {X(t, x 0 , ω) ∈ [x 0 , b] and X(1, x 0 , ω) > x 0 } = Prob.{X(1, x 0 , ω) > x 0 } • Prob. X(t, x 0 , ω) ∈ [x 0 , b] X(1, x 0 , ω) > x 0 = Θ(x 0 ) • Prob. S + T + (t,x 0 ,ω) ∈ [x 0 , b] = P t (x 0 , [x 0 , b]).Otherwise, if x 0 = y j ∈ S * then Prob. X(t, x 0 , ω) ∈ [x 0 , b] = Prob. X(t, x 0 , ω) ∈ [x 0 , b] and X(s, x 0 , ω) > x 0 for some s > 0 +Prob. X(t, x 0 , ω) ∈ [x 0 , b] and X(s, x 0 , ω) < x 0 for some s > 0= Θ(x 0 ) • Prob. S + T + (t,x 0 ,ω) ∈ [x 0 , b] +(1 -Θ(x 0 )) • Prob. X(t, x 0 , ω) = x 0 X(s, x 0 , ω) < x 0 for some s > 0 = Θ(x 0 ) • Prob. S + T + (t,x 0 ,ω) ∈ [x 0 , b] + (1 -Θ(x 0 )) • Prob. Y j (ω) ≥ t = P t x 0 , [x 0 , b] .

 1-α . Notice that, by taking the limits λ → 0 or λ → +∞, we recover the deterministic semigroups S and S, respectively.

d c

Case (iii) is proved in an analogous way.

4.

In Case (iv), we show that the result follows from the same analysis as in Cases (ii) and (iii). Indeed, it will be sufficient to prove (4.12) for A = [x 0 , b], while the case A = [c, x 0 ] is entirely similar.

If x 0 / ∈ S * then there is no random waiting time at x 0 , and all trajectories immediately start moving (either to the left or to the right of x 0 ). The same argument used in Case (ii) now yields

From (4.11) it thus follows

The remaining case is when x 0 = y j ∈ S * . We then observe that, for every τ ≥ 0, one has

where

In turn, given S (n) , we can recover the original semigroup S by inserting back the waiting times at the points y 1 , . . . , y n . Now consider the limit semigroup S = lim n→∞ S (n) . Since we removed all the random waiting times, restricted to the interval J the trajectories of S are strictly increasing with probability one. This will imply that S is a deterministic semigroup, hence it admits the representation proved in Theorem 3.1. Namely, there exists a positive atomless measure µ on J ∩ f -1 (0) such that trajectories of S are determined by the formula (3.10). In turn, the original Markov semigroup S can be recovered from S by adding back the random waiting times Y j at the points y j . This will provide the desired characterization of S.

5.

We now work out details. Consider the first point y 1 . We claim that, starting with the Markov semigroup S and removing the random waiting time Y 1 (ω) at y 1 , we obtain another Markov semigroup S (1) .

Indeed, given an initial point x 0 ∈ J, let t → X(t, x 0 , ω) be a sample path of the original process, and define the new path X (1) (•, x 0 , ω) by setting

We claim that the transition probability kernels P (1) τ (x 0 , A) . = Prob. X (1) (τ, x 0 , ω) ∈ A satisfy the Chapman-Kolmogorov equation. Indeed, for any Borel set B ⊂]a, b[ , the following holds.

If x 0 > y 1 , then P

(1)

Therefore, for any s, t > 0 and any Borel set A ⊆]a, b[, if x 0 > y 1 then we trivially have

t (z, A)P (1) s (x 0 , dz) = P t (z, A)P s (x 0 , dz) = P t+s (x 0 , A) = P

t+s (x 0 , A).

such that

] ≤ 2ε 0 for all i = 1, 2, . . . , ν.

(

Notice that, setting

(5.16)

From (5.15) it follows

and (5.16) implies

Prob.

In turn, for every j ≥ 1, it holds Prob. T

Let us now estimate the variance of the random time

Observing that Φ is a non-increasing function which satisfies

we estimate the variance 1

Var.(

(5.17)

We observe that, for i = 1, . . . , ν, the random variables T x i-1 x i are mutually independent. Hence, by (5.16),

Var.( T x 0 x ) =


Stéphane Demri
email: demri@imag.fr

Ewa Or Lowska
email: orlowska@itl.waw.pl

Complementarity relations: reduction of decision rules and informational representability

Introduction

The main objectives of this paper are:

(a) To show how reduction of decision rules and sets of decision rules can be based on an analysis of complementarity of objects defined by means of these rules, (b) To prove the informational representability of relational systems with complementarity relations.

In the paper we consider decision rules determined by a decision table. Each of the rules might be interpreted as a statement defining a decision that depends on properties of an object. We show that the complementarity relations derived from a decision table provide criteria for reduction of both individual rules and sets of rules. It follows that reasoning about complementarity might play an important role in development of decision support systems. Intuitively, two objects are complementary whenever the properties that they possess are negations of each other. For example, if x is green and y is not green, then x and y are complementary. We propose two kinds of structures to model complementarity phenomenon: abstract relational systems, referred to as complementarity frames, where the respective complementarity relations are determined by means of their properties; and 'concrete' structures, where the relations are derived directly from a decision table and are defined in terms of properties of objects. We prove that any abstract complementarity frame is informationally representable. The notion of informational representability of relational systems has been introduced and investigated in [START_REF] Demri | Informational representability of models for information logics[END_REF]. Let a similarity relation 1 in a class C of relational systems be given, for example a relation of 'being isomorphic'. Intuitively, a system K from the class C is informationally 1-representable if there is a decision table and a system K derived from the table such that K is in the class C and K is 1-related to K . The informational representability might be treated as a criterion of adequacy of a formal model in that it shows that the model captures the relevant features of an application domain (see for instance in [7,8] representability results involving similarity structures).

Decision rules and their reduction

By an information system (see e.g. [6]) we mean a pair (OB, AT ) where OB is a non-empty set of objects and AT is a non-empty set of attributes. Each attribute a is a mapping a : OB → P(V al a ) \ {∅}. For each a ∈ AT , the nonempty set V al a is the set of values of the attribute a. In that setting, two objects o 1 , o 2 are said to be indiscernible with respect to a set of attributes A ⊆ AT (in short o 1 ind(A) o 2 ) iff for all a ∈ A, a(o 1 ) = a(o 2 ). Various generalizations of the notion of information system and some other relations between the objects (similarity, weak indiscernibility, . . .) can be found for instance in [4, 9].

An

Fig. 1. A decision table

In Figure 1, 'not green' stands for V al colour \ {green}. This table generates the following set D(S) of rules: r o1 : (colour, green) & (size, small) → pick it up r o2 : (colour, not green) & (size, small) → pick it up r o3 : (colour, blue) & (size, medium) → do not pick it up Any decision rule can be treated in a natural way as a formula of the classical propositional calculus. For example the rule r o1 from Example 1 corresponds to: if an object is green and small then pick it up. Clearly if S is consistent (respectively inconsistent) then D(S) is consistent (respectively inconsistent) in the propositional calculus.

(comp) Two objects o 1 and o 2 are said to be in relation of complementarity

with respect to A ⊆ AT (o 1 comp(A) o 2 ) iff for all a ∈ A, a(o 1 ) = V al a \ a(o 2 ).
We say that a condition attribute a ∈ AT is redundant in rule r o if there is o ∈ OB such that the following conditions hold:

(red)    (o, o ) ∈ comp({a}), (o, o ) ∈ ind(AT \ {a}), and ∀z, if d(z) = d(o) then ∃b ∈ AT \ {a} such that b(z) = b(o)
In other words, a is redundant in r o whenever decision d(o) does not depend on the condition attribute a. As a consequence, if a is redundant in r o we may delete a part of the rule that refers to the attribute a. Moreover, we may delete from D(S) all the rules r o such that o and o satisfy (red). It is easy to see that this reduction process preserves consistency/inconsistency of the set of decision rules. Traditionally, there are two groups of methods for reduction of decision rules and sets of decision rules: methods that reduce the number of condition attributes in the decision table (based on calculation of reducts) and methods of elimination of redundant conditions in a rule. As shown previously, an analysis of complementarity relations contributes to both kinds of methods. 1 then the rule r o1 would not be reducible. For otherwise, the reduced set of rules would be inconsistent, namely r o1 and r o4 would be contradictory.

Example 2. Consider the decision table from

We conclude that reasoning about indiscernibility and complementarity of objects in a decision table S provides criteria for reduction of both individual decision rules and the set D(S) of rules.

Complementarity frames

By a complementarity frame derived form an information system S = (OB, AT ) (or from a decision table S = (OB, AT, d)) we mean the system (OB, comp(AT )), where comp(AT ) is defined according to condition (comp) from Section 2. It can be observed that comp(AT ) is symmetric, irreflexive and intransitive. This is an example of a concrete structure (derived from user data). Moreover, when o comp(AT ) o holds, then for all a ∈ AT the set V al a is uniquely determined by a(o) and a(o ). Hence, a more subtle characterization of complementarity is needed. This problem has been open until now. The following definition provides hints to solve this problem.

A binary relation R over a set U is said to be a complementarity relation iff -R is symmetric, -R does not contain cycles of odd length and, for all u, v, w, z ∈ U , if (u, v) ∈ R, (v, w) ∈ R and (w, z) ∈ R then (u, z) ∈ R (3-transitivity).

By an abstract complementarity frame we mean a system (U, R) such that U is a nonempty set and R is a complementarity relation over U . We write F to denote the class of complementarity frames. Observe that the class F is not closed under p-morphisms. It follows that F is not modally definable (see [3]). Moreover, F is elementary since the condition of being a complementarity relation can be expressed by a set Γ of formulas from the classical first-order logic. Hence modal logics characterized by complementarity frames might play a special role in modal logic theory. It is easy to see that comp(AT ) is a complementarity relation. In the following section we prove the informational representability of abstract complementarity frames.

Informational representability: a construction

For any binary relation R over the set U , for all u ∈ U we write C u,R to denote the largest subset of U such that u ∈ C u,R and, for all v ∈ C u,R \ {u}, there is a R -path between u and v where R is the symmetric closure of R.

Observe that {C u,R : u ∈ U } is a partition of U . For all u ∈ U , we write C 0 u,R (resp. C 1 u,R ) to denote the largest subset of C u,R such that for all v ∈ C 0 u,R , there is a R -path of even (resp. odd) length between u and v. Moreover for all U ⊆ U , we write

C U u,R to denote C 0 u,R if u ∈ U , C 1 u,R otherwise.
Observe that for all u, v, w ∈ U , and for a complementarity relation R,

if {v, w} ⊆ C u,R then {C 1 v,R , C 0 v,R } = {C 1 w,R , C 0 w,R }.
In particular, if there is a R-path of odd length between v and w then

C 1 v,R = C 0 w,R and C 0 v,R = C 1 w,R otherwise C 0 v,R = C 0 w,R and C 1 v,R = C 1 w,R . Lemma 1. Let R be a complementarity relation over a set U . The set {C i u,R : u ∈ U, i ∈ {0, 1}} is a partition of U .
The proof of Lemma 1 is by an easy verification. It is worth mentioning that although {C u,R : u ∈ U } is a partition of U whatever is the binary relation R, the fact that R is a complementarity relation is a crucial hypothesis in Lemma 1.

Indeed if (u, v) ∈ R 2k (resp. (u, v) ∈ R 2k+1 ) for some k ≥ 0 then for all k ≥ 0, (u, v) ∈ R 2k +1 (resp. (u, v) ∈ R 2k
), otherwise it would exist a cycle of odd length passing through u.

In order to show the informational representability, for all (U, R) ∈ F we construct an information system S g(K) = (U, {at g(K) }) such that g(K) ⊆ P(U ), at g(K) is a mapping from U into P(g(K)) and, -R = comp({at g(K) }).

Let g be the mapping such that for all K = (U, R) ∈ F,

g(K) = { u∈Y C U u,R : ∃U ⊆ U, ∃Y ∈ W } with W = {Y ⊆ U : ∀u, v ∈ Y, C u,R = C v,R , u∈Y C u,R = U }
The set W contains subsets of U with exactly one element for each set in {C u,R : u ∈ U }. Moreover g(K) can be roughly defined as the set of maximal subsets U of U (with respect to inclusion) such that R ∩ U × U = ∅. Figure 2 illustrates the construction with a finite frame (the closure by 3-transitivity and symmetry is omitted in the picture for the sake of readability).

§ ¦ ¤ ¥ J J J J J J J J J J J J J J J J J J K = (U, R) an element of W An element of g(K) Fig. 2. Example It is easy to show that for all Y 0 ∈ W , g(K) = { u∈Y0 C U u,R : ∃U ⊆ U } and Y ∈g(K) Y = U . For all u ∈ U , C u,R is not empty (u ∈ C u,R ). Let x u be the representative element of C u,R . Hence W is not empty since {x u : u ∈ U } ∈ W . Lemma 3. comp({at g(K) }) = R.
So for any complementarity frame K = (U, R), there exists an information system (U, AT ) such that comp(AT ) = R. Moreover, for any information system (OB, AT ), the structure (OB, comp(AT )) is a complementarity frame. Hence, This informational representability result relates two classes of structures, namely information systems and abstract complementarity frames. This abstract characterization of the relations comp(AT ) might also be useful in mechanizing the reduction process of sets of decision rules that has been intuitively described in Section 2. Namely, the result assures that any inference method designed for a modal logic determined by the class of complementarity frames ([5]) guarantees a logically adequate transformations of sets of decision rules.

Besides, as observed in [START_REF] Duentsch | [END_REF], in the definition for the complementarity relations, the condition on cycles of odd length can be equivalently replaced by the condition that the relation is irreflexive. However it is an open problem whether the representability construction can be carried on without referring to the cycles property.

Concluding remarks

We discussed a formal framework for the development of a method of reduction of decision rules derived from a decision table. We have shown that an analysis of complementarity is useful for that purpose. We formulated and proved the informational representability of relational systems with complementarity relations. Our construction can also be used to characterize the incomplementarity relations between objects. Let S = (OB, AT ) be an information system. Two objects o 1 and o 2 are said to be in relation of incomplementarity with respect to A ⊆ AT (in short o 1 incomp(A) o 2 ) iff for all a ∈ A, (V al a \ a(o 1 )) = a(o 2 ). Let F be the class of frames (U, R) such that the complement of R is a complementarity relation. For any frame K = (U, R) in F we define g (K) = g((U, -R)) where '-' is the complement with respect to U × U . We can easily show that incomp({at g(K) }) = R. Hence {(OB, incomp(AT )) : (OB, AT ) is an information system} provides an informational representation of the class F . This article was processed using the L A T E X macro package with LMAMULT style

Figure 1 .

 1 The object o 1 satisfies the condition (red). Hence we can reduce the rule r o1 to: r o1 : (size, small) → pick it up Moreover we remove the rule r o2 from the set D(S). Observe that if a row "| o 4 | blue | small | no |" is added to Table

Corollary 4 .

 4 {(OB, comp(AT )) : (OB, AT, d) is an information system} provides an informational representation of the class F.

  information system S = (OB, AT, d), d ∈ AT , with an additional attribute d, referred to as a decision attribute (or with a finite family of decision attributes) is called a decision table. In the rest of this section, we assume that d(o) is a singleton set for each o ∈ OB. The values d(o) of d for objects o ∈ OB are called decisions. The attributes from AT are called condition attributes. Any decision table S with a finite set AT generates a set D(S) of decision rules. By a rule determined by an object o ∈ OB we mean the following statement. Let AT = {a 1 , ..., a n }. (r o ) If the value of a 1 for o is a 1 (o) and ... and the value of a n for o is a n (o), then decide d(o). We abbreviate such a rule as: (a 1 , a 1 (o)) & ... & (a n , a n (o)) → d(o) We say that a decision table is inconsistent if there are two objects o and o such that (o, o ) ∈ ind(AT ) and d(o) = d(o ). Otherwise, the table is consistent. Example 1. Consider the decision table in Figure 1.

		colour	size d (pick-up)
	o1 green	small	yes
	o2 not green small	yes
	o3	blue medium	no

  3. Robert Goldblatt and Steven Thomason. Axiomatic classes in propositional modal logic. In J. Crossley, editor, Algebra and Logic, pages 163-173. Springer-Verlag, Lecture Notes in Mathematics 450, 1975. 4. Ewa Or lowska. Kripke semantics for knowledge representation logics. Studia Logica, 49(2):255-272, 1990. 5. Ewa Or lowska. Studying incompleteness of information: a class of information logics. Technical Report ICS-27-96, Warsaw University of Technology, Institute of Computer Science, April 1996. 6. Zdzislaw Pawlak. Information systems theoretical foundations. Information Systems, 6(3):205-218, 1981. 7. Dimiter Vakarelov. Abstract characterization of some knowledge representation systems and the logic NIL of nondeterministic information. In Philippe Jorrand and Vassil Sgurev, editors, Artificial Intelligence: Methodology, Systems, Applications, pages 255-260. Elsevier Science Publishers B.V. (North-Holland), 1987. 8. Dimiter Vakarelov. Logical analysis of positive and negative similarity relations in property systems. In Michel de Glas and Dov Gabbay, editors, First World Conference on the Fundamentals of Artificial Intelligence, 1991. 9. Dimiter Vakarelov. A modal logic for similarity relations in Pawlak knowledge representation systems. Fundamenta Informaticae, 15:61-79, 1991.

Lemma 2. Let K = (U, R) be a frame in F. For all u, v ∈ U , (u, v) ∈ R iff for all Y ∈ g(K), either (u ∈ Y and v ∈ Y ) or (u ∈ Y and v ∈ Y ).

So there is X 0 ∈ g(K) such that {u, v} ⊆ X 0 , which leads to a contradiction. Now assume C u,R = C v,R . Suppose there is a R-path of even length between u and v, say (u 0 , . . . , u n , . . . , u 2×n ) with

So there is X 0 ∈ g(K) such that {u, v} ⊆ X 0 , which leads to a contradiction. So there is a R-path of odd length between u and v, say (u 0 , . . . , u (2×n)+1 ) with u 0 = u and v = u (2×n)+1 .

-If n = 0, then (u, v) ∈ R.

-If n = 1, then by the 3-transitivity condition (u, v) ∈ R.

-Now assume n > 1. By the 3-transitivity condition, (u (2×(n-1)) , u (2×n)+1 ) ∈ R. So there is a path of length (2×(n-1))+1 between u and v. By induction on n one can therefore prove that (u, v) ∈ R.

We write at g(K) to denote the mapping U → P(P(U )) such that for all x ∈ U , at g(K) (x) = {Z : x ∈ Z ∈ g(K)}. Let S g(K) be the structure (U, {at g(K) }). For all x ∈ U , at g(K) (x) = ∅ since Z∈g(K) Z = U . It follows that S g(K) is an information system. It is worth mentioning that for all u, v ∈ U , (∀Y ∈ g(K),

(by definition of comp) iff {Z : u ∈ Z ∈ g(K)} = g(K) \ {Z : v ∈ Z ∈ g(K)} (by definition of at g(K) ) iff {Z :