Simon Perdrix

Partial Observation of Quantum Turing Machine and Weaker Well-Formedness Condition

The quantum Turing machine (QTM) has been introduced by Deutsch as an abstract model of quantum computation. The transition function of a QTM is linear, and has to be unitary to be a well-formed QTM. This well-formedness condition ensures that the evolution of the machine does not violate the postulates of quantum mechanics. However, we claim in this paper that the well-formedness condition is too strong and we introduce a weaker condition, leading to a larger class of Turing machines called Observable Quantum Turing Machines (OQTMs). We prove that the evolution of such OQTM does not violate the postulates of quantum mechanics while offering a more general abstract model for quantum computing. This novel abstract model unifies classical and quantum computations, since every well-formed QTM and every deterministic TM are OQTMs, whereas a deterministic TM has to be reversible to be a well-formed QTM. In this paper we introduce the fundamentals of OQTM like a well-observed lemma and a completion lemma. The introduction of such an abstract machine allowing classical and quantum computations is motivated by the emergence of models of quantum computation like the one-way model. More generally, the OQTM aims to be an abstract framework for the pragmatic paradigm of quantum computing: 'quantum data, classical control'. Furthermore, this model allows a formal and rigorous treatment of problems requiring classical interactions, like the halting of QTM. Finally, it opens new perspectives for the construction of a universal QTM.

Introduction

How to make a quantum version of the deterministic Turing machine (DTM)? While a probabilistic Turing machine (PTM) is obtained from a DTM by allowing probability distributions over machine configurations, a pre-quantum Turing machine (pQTM) is defined from a DTM by allowing superpositions of machine configurations. In addition, a PTM has to satisfy a well formedness condition ensuring that the probabilities are positive numbers and sum to one. In the same way, a reversible Turing machine (RTM) is an instance of DTM which satisfies a well formedness condition ensuring its reversibility. In a similar vein, Deutsch had introduced the Quantum Turing machines (QTM) as a class of pQTMs which satisfy a well formedness condition. This well formedness condition ensures that QTMs do not violate the postulate of quantum mechanics and implies reversibility as well. As a consequence, a QTM is a quantum version of a RTM. However, recent developments of models of quantum computation like the one-way quantum computer, point out that a quantum computation may be irreversible. Thus, the well-formedness condition is too restrictive.

The main contribution of this paper consists in introducing a weaker well formedness condition to capture the postulates of quantum mechanics, independently of the question of reversability. This weaker condition leads to a class of quantum versions of DTMs, called Observable Quantum Turing machines (OQTM).

After a brief introduction to quantum basics (see [START_REF] Nielsen | Quantum computation and quantum information[END_REF] for a complete introduction), we introduce in section 4, such a less restrictive class of quantum Turing machines, the observable quantum Turing machines (OQTM), where partial observations can be performed at each transition. Fondamentals of OQTM are given: evolution operator (which is not a unitary transformation any more, but a trace-preserving completely-positive map, like in the linear quantum Turing machines [START_REF] Iriyama | Generalized quantum Turing machine and its application to the sat chaos algorithm[END_REF]) a well-observation condition (which is the generalisation of the well-formedness condition.) Essential tools for programming OQTMs are introduced: a well-observation lemma (i.e. the conditions the transition function has to satisfy to make the machine a well-observed pQTM); and a completion lemma (if a partial transition function satisfies the conditions of the well-obseravtion lemma, it can be extended to a total function of a well-observed pQTM.) In section 5.1, we prove that any QTM can be simulated by an OQTM in which a partial measurement is performed at each transition in order to know whether the computation is halted or not.

In section 5.2, we prove that any QTM and any deterministic Turing machine are wellobserved. Thus, OQTM expands the classical model of deterministic Turing machine, including non-reversible machines. Moreover, well-observation can be seen as a weaker wellformedness condition allowing non-reversible computations.

In section 6, we prove that the computational power of OQTM is equivalent to the one of QTM, since any OQTM can be simulated by a QTM within a quadratic slowdown.

Quantum Computing Basics

The basic carrier of information in quantum computing is a 2-level quantum system (qubit), or more generally a d-level quantum system (qudit). The state of a single qudit is a normalized vector of a Hilbert space C A , where A is a finite alphabet of symbols. An orthonormal basis (o.n.b.) of this Hilbert space is described as: {|τ , τ ∈ A}. So the general state |ϕ ∈ C A of a single qudit can be written as: τ β τ (where α * stands for the complex conjugate). The left hand side ϕ| of the inner product is a bra-vector, and the right hand side |ψ is a ket-vector. A bra-vector is defined as the adjoint of the corresponding ket-vector:

if |ϕ = τ ∈A α τ |τ , then ϕ| = |ϕ † = τ ∈A α * τ τ |.
The bra-ket notation can also be used to describe outer products: |ϕ ψ| is a linear operator, (|ϕ ψ|)|ǫ = ψ|ǫ |ϕ . The state of a system composed of 2 qudits in state |ϕ ∈ C A and |ψ ∈ C B respectively, is the normalized

vector |ϕ ⊗ |ψ ∈ C A ⊗ C B ∼ = C A×B , where ⊗ is the tensor product. For any τ ∈ A, γ ∈ B, |τ, γ denotes |τ ⊗ |γ .
Probability distribution of quantum states of C A can be represented by a density matrix ρ ∈ D(C A ) ⊆ C A×A , i.e. a self adjoint1 positive-semidefinite2 complex matrix of trace3 one.

According to the second postulate of quantum mechanics, an isolated system evolves according to a unitary transformation 4 U ∈ C A×A , transforming a state ρ ∈ D(C A ) into U ρU † . More generally, whether the system is isolated or not, the state evolves according to a trace-preserving completely-positive (tpcp) map F , transforming ρ into F (ρ). According to the Kraus representation theorem [START_REF] Choi | Completely positive linear maps on complex matrices[END_REF], for any tpcp map F , there exists a collection of matrices M i ∈ C A×A , that satisfies a completeness condition i M † i M i = I, such that

F (ρ) = i M i ρM † i .
A special instance of tpcp-map is a projective measurement described by a collection of projectors P i . A projective measurement transforms ρ into i P i ρP i . A projective measurement produces a classical outcome i 0 with probability p i0 (ρ) = T r(P i0 ρP i0 ) = T r(P i0 ρ). 5 For instance, a projection onto a given state |ϕ is P 0 = |ϕ ϕ|, thus the probability to obtain the classical outcome associated with this projector is |ϕ is T r(|ϕ ϕ|ρ) = T r( ϕ|ρ|ϕ ).

Quantum Turing Machine

For completeness, the definition of deterministic Turing machines is given. See [START_REF] Papadimitriou | Computational complexity[END_REF] for fondamentals on (classical) Turing machines.

Definition 1 (Deterministic Turing Machine (DTM)).

A deterministic Turing machine is defined by a triplet (Σ, Q, δ) where: Σ is a finite alphabet with an identified blank symbol #, Q is a finite set of states with an identified initial state q 0 and final state q f = q 0 , and δ, the deterministic transition function 6 , is a function

δ : Q × Σ → Σ × Q × {-1, 0, 1}
Deutsch in [START_REF] Deutsch | Quantum theory, the Church-Turing principle and the universal quantum computer[END_REF] introduced a quantum version of the Turing machine, extensively studied by Bernstein and Vazirani [START_REF] Bernstein | Quantum complexity theory[END_REF]: Definition 2 (Pre-Quantum Turing Machine (pQTM)). A pre-quantum Turing machine (pQTM ) is defined by a triplet (Σ, Q, δ) where: Σ is a finite alphabet with an identified blank symbol #, Q is a finite set of states with an identified initial state q 0 and final state q f = q 0 , and δ, the quantum transition function, is a function

δ : Q × Σ → C Σ×Q×{-1,0,1}
(p, τ ) → q∈Q,σ∈Σ,d∈{-1,0,1} α p,τ,q,σ,d |σ, q, d For convenience, the expression δ(p, τ, q, σ, d) is used to denote α p,τ,q,σ,d ∈ C, i.e. the amplitude in δ(p, τ ) of |σ, q, d . The evolution of a pQTM M is given by the linear operator U M defined on C Q×Σ * ×Z (called the state space of configurations):

U M = p,q∈Q,σ∈Σ,d∈{-1,0,1},T ∈Σ * ,x∈Z δ(p, T x , q, σ, d)|q, T σ x , x + d p, T, x|
where T σ x ∈ Σ * is T where the symbol in position x is replaced by σ. A quantum Turing machine (QTM ) is a well-formed pre-quantum Turing machine:

Definition 3 (Well-formedness condition). A pQTM M is well-formed if and only if

U M is an isometry, i.e. U † M U M = I.

Lemma 1 (Well-formedness lemma [11]). For a given pQTM

M = (Σ, Q, δ), M is well- formed if and only if: (a) ∀(τ, p) ∈ Σ × Q, δ(p, τ ) † δ(p, τ ) = 1 (b) ∀(τ, p), (τ ′ , p ′ ) ∈ Σ × Q with (p, τ ) = (p ′ , τ ′ ), δ(p, τ ) † δ(p ′ , τ ′ ) = 0 (c) ∀(τ, p, σ), (τ ′ , p ′ , σ ′ ) ∈ Q × Σ × Σ, d∈{0,1},q∈Q δ(p, τ, q, σ, d -1) * δ(p ′ , τ ′ , q, σ ′ , d) = 0 (d) ∀(τ, p, σ), (τ ′ , p ′ , σ ′ ) ∈ Q × Σ × Σ, q∈Q δ(p, τ, q, σ, -1) * δ(p ′ , τ ′ , q, σ ′ , 1) = 0 A triple M = (Σ, Q, δ) is called a partial pQTM if δ is a partial quantum transition func- tion.
If such a δ satisfies the four conditions of the well-formedness lemma 1, then M is called a partially well-formed pQTM. [START_REF] Ozawa | Local transition functions of quantum turing machines[END_REF]). For every partially well-formed pQTM M with a partial quantum transition δ, there exists a QTM M ′ with the same alphabet, the same set of states, and a transition function δ ′ which is equal to δ on the domain of δ.

Lemma 2 (Completion lemma

A QTM M evolves according to U M : if the initial configuration of M is |c ∈ C Q×Σ * ×Z , then after n transitions, the configuration of the machine is (U M ) n |c . Configurations may also be represented by density matrices ρ ∈ D(C Q×Σ * ×Z ) (see [START_REF] Iriyama | Generalized quantum Turing machine and its application to the sat chaos algorithm[END_REF]). Density matrices allows representation of probabilistic distributions over quantum states. The evolution operator is then the tpcp map:

F M : D(C Q×Σ * ×Z ) → D(C Q×Σ * ×Z ) ρ → U M ρU † M

Observable Quantum Turing Machine

Since a QTM has a unitary evolution, no measurement can be applied until the machine halts. It turns out that it may be useful to observe the machine during the evolution, for instance to know whether the machine is already halted or not. This problem has been solved [START_REF] Ozawa | Halting of quantum Turing machines[END_REF] by proving that one can add a halt qubit that can be measured after each transition, and which switches from 0 to 1 when the machine halts. We introduce a formal and more general framework to describe a partial observation of the machine before and after each transition:

Definition 4 (Observed pre-quantum Turing machine). For a given pQTM M = (Σ, Q, δ), and a partition

K = {K λ , λ ∈ Λ} of Σ × Q, [M ] K is an observed pre-quantum Turing machine. The evolution of [M ] K is given by F [M]K : F [M]K : D(C Q×Σ * ×Z ) → D(C Q×Σ * ×Z ) ρ → λ,µ∈Λ χ λ,µ ρχ † λ,µ
where χ λ,µ is a linear operator defined as follows: As a consequence, the evolution of [M ] K can be decomposed into a projective measurement of the internal states and the cell pointed out by the head according to the observable O Λ = λ∈Λ λP λ , then a linear transition U M -which is the same as the evolution of M -and finally a second projective measurement according to O Λ . Thus, before and after each transition, a property of the machine is measured. The measured property is described by a partition {K λ , λ ∈ Λ}, composed of |Λ| regions, of the internal states and the symbols of the cell pointed out by the head. The measurement consists in projecting the internal state of the machine and the state pointed out by the head into one of these regions. This measurement, which produces a classical outcome λ ∈ Λ, is a partial observation, since after the measurement the configuration can be in a superposition of the elements of the region K λ .

χ λ,µ = (τ,p)∈K λ ,(σ,q)∈Kµ,
From a physical point of view, Well-formedness lemma and completion lemma are essential tools for programming QTMs. We introduce analogues for OQTM, i.e., a well-observation lemma and a completion lemma: Lemma 3 (Well-observation lemma). For a given pQTM M = (Σ, Q, δ) and a given

[M ] K is realizable if F [M]K is a trace-preserving completely- positive (tpcp) map.

Definition 5 (Well-observation condition). An observed pQTM

[M ] K is well-observed if and only if F [M]K is a tpcp map, i.
K = {K λ , λ ∈ Λ} ⊆ Σ × Q, [M ] K is well-observed if and only if: (a) ∀(τ, p) ∈ Σ × Q, δ(p, τ ) † δ(p, τ ) = 1 (b) ∀λ ∈ Λ, ∀(τ, p), (τ ′ , p ′ ) ∈ K λ with (p, τ ) = (p ′ , τ ′ ), δ(p, τ ) † δ(p ′ , τ ′ ) = 0 (c) ∀λ ∈ Λ, ∀(τ, p, σ), (τ ′ , p ′ , σ ′ ) ∈ K λ × Σ, d∈{0,1},q∈Q δ(p, τ, q, σ, d -1) * δ(p ′ , τ ′ , q, σ ′ , d) = 0 (d) ∀λ ∈ Λ, ∀(τ, p, σ), (τ ′ , p ′ , σ ′ ) ∈ K λ × Σ, q∈Q δ(p, τ, q, σ, -1) * δ(p ′ , τ ′ , q, σ ′ , 1) = 0
Proof. According to remark 1, χ λ,µ = P µ U M P λ so λ,µ∈Λ χ † λ,µ χ λ,µ = λ∈Λ P λ U † M U M P λ since µ∈Λ P µ = I. Thus, [M ] K is well-observed if and only if for any basis configura-

tions |p, T, x , |p ′ , T ′ , x ′ , λ∈Λ p, T, x|P λ U † M U M P λ |p ′ , T ′ , x ′ = p, T, x|p ′ , T ′ , x ′ . Since P λ |p, T, x = |p, T, x if (T x , p) ∈ K λ
and 0 otherwise, the well-observation equation is obviously satisfied if (T x , p) and (T ′

x ′ , p ′ ) are not in a same block K λ . If they are in the same block then the well-observation condition is p, T, x|U

† M U M |p ′ , T ′ , x ′ = p, T, x|p ′ , T ′ , x ′ .
Thus, [M ] K is well-observed iff for each λ ∈ Λ, the restriction of U M to C {(p,T,x), s.t. (Tx,p)∈K λ } is an isometry. For each of these restrictions of U M , one can apply the well-formedness conditions (see lemma 1) leading to equations (a) to (d).

Comparing with the well-formedness lemma for QTM (see [START_REF] Ozawa | Local transition functions of quantum turing machines[END_REF]), the well-observation lemma points out that the well-observation is a weaker condition than the well-formedness condition: equation (a) has to be satisfied by both well-formed and well-observed machines, whereas equations (b) to (d) are weaker for well-observation, since only the pairs of elements in a same block have to satisfy the equations.

For a given a partial pQTM M = (Q, Σ, δ) and a given partition K of Σ × Q, if δ satisfies the four conditions of the well-observation lemma 3, then [M ] K is called a partially well-observed pQTM.

Lemma 4 (Completion lemma). For every partially well-observed pQTM [M ]

K with a partial quantum transition δ, there exists an OQTM [M ′ ] K with the same alphabet, the same set of states, and a transition function δ ′ which is equal to δ on the domain of δ.

Proof. The proof consists in applying the QTM completion lemma on each block of the partition K. If K = {K λ , λ ∈ Λ}, then let M λ = (Σ, Q, δ λ ), where δ λ is the restriction of δ to K λ . According to lemmas 1 and 3, M λ is a well-formed partial QTM , thus M λ can be expanded to a well-formed QTM M ′ λ . Let δ (k) be the transition function of M ′ k . Finally, let δ ′ be such that for any (p, τ ), δ ′ (p, τ ) = δ (λ) (p, τ ) if (τ, p) ∈ K λ . Since each δ (k) satisfies the conditions of lemma 1, δ ′ satisfies the conditions of lemma 3. Moreover, δ ′ extends δ.

Examples of Observable Quantum Turing Machines

Quantum Turing machine

The formalism of observable quantum Turing machines expands the formalism of quantum Turing machines: any QTM is an OQTM where a non-informative partial measurement is performed. Indeed:

Proposition 1. For any pQTM M = (Σ, Q, δ), M is well-formed if and only if [M ] {Σ×Q} is well-observed. Moreover, M and [M ] {Σ×Q} have the same evolution: F [M] {Σ×Q} = F M .
More generally, for any QTM M and any partition K of its internal states, [M ] K is wellobserved. However, the evolution of the machine depends on the partition K, so the language recognized by the machine and the execution time depend on the partition K. Proposition 1 states that if K is composed of a unique block, then the evolution of a QTM M and the OQTM [M ] K are the same. Another example where K is a bipartition is given in lemma 5. In that example, for a given QTM M , M and [M ] K do not have the same evolution, however in this particular example the computational power of M and [M ] K are the same.

Halting of quantum Turing machines is symptomatic of the lack of a coherent integration of the notion of observation. The unitary evolution of a QTM implies that the machine, seen as the physical system, does not interact with its environment. As a consequence, it is impossible to know whether the machine halts without measuring it. Moreover, if this measurement reveals that the computation was actually not finished, the machine has to be re-initialised. In order to solve this problem, an ad hoc mechanism, consists in adding a halting qubit to the machine. This qubit can be measured at any time in order to know whether the computation is halted. Such a machine is no more a QTM since its evolution is not unitary, however if some halting condition are satisfied then the computational power of the ad hoc machine is equivalent to the one of the corresponding QTM. One of the aims of the model of observable quantum Turing machines is to describe such a mechanism in a coherent formalism (since observation can be represented in this formalism) and then gives a deeper understanding of the halting of quantum process in general. Thus, following the work of Ozawa [START_REF] Ozawa | Halting of quantum Turing machines[END_REF] on halting of QTM, we show that any QTM M satisfying the halting condition have the same computational power as [M ] K where at each transition the internal state of the machine is measured in order to know when the machine halts.

Lemma 5. Let M = (Q, Σ, δ) be a QTM , then [M ] H is well-observed, where H = {Σ × (Q \ {q f }), Σ × {q f }}. Moreover, if M satisfies the halting condition (i.e., ∀T ∈ Σ * , ∀c ∈ Q × Σ * × Z, ∀t ≥ 0, U M P U t M |c = P U M P U t M |c , where P = x∈Z |q f , T, x q f , T, x|), the computational powers of M and [M ] H are equivalent: ∀n ∈ N, ∀ρ ∈ D(C Q×Σ * ×Z ), ∀T ∈ Σ * , p halt,T (F n M (ρ)) = p halt,T F n [M]H (ρ)
where p halt,T (ρ) denotes the probability that the machine halts (i.e. the internal state is q f ) and that the outcome of the tape measurement is T if the configuration of the machine is ρ.

Proof. The proof is based on the result presented in [START_REF] Ozawa | Halting of quantum Turing machines[END_REF].

Classical Turing machines

In this section, we prove that [M ] K may be well-observed for some K, even if the pQTM M is not well-formed. As a consequence, the well-observation condition is weaker than the well-formedness condition. In lemma 2 a separation between well-formed and well-observed machines is pointed out, by considering deterministic Turing machines. One can describe a deterministic Turing machines M = (Q, Σ, δ) by means of the prequantum Turing machine M = (Q, Σ, δ), where δ(p, τ ) = |δ(p, τ ) . It is well-known that M is well-formed if and only if M is a reversible deterministic Turing machine. However, we prove for any deterministic Turing machine M , that the OQTM [ M ] {{c},c∈Σ×Q} , where a total measurement of the internal states and the cell pointed out by the head is performed, is well-observed:

Proposition 2. For any DTM M = (Q, Σ, δ), [ M ] {{c},c∈Σ×Q} is well-observed, where M = (Q, Σ, δ) is a pQTM such that ∀(p, τ ) ∈ Q × Σ, δ(p, τ ) = |δ(p, τ ) . Moreover, M and [ M ] {{c},c∈Σ×Q} have the same evolution: for any c ∈ Q × Σ * × Z, F [ M ] {{c},c∈Σ×Q} (|c c|) = |M (c) M (c)|.
Probabilistic Turing machines are also special instances of OQTMs. A probabilistic Turing machine is a triple M = (Q, Σ, δ), with δ :

Q × Σ × Q × Σ × {-1, 0, 1} → R + , such that for any (p, τ ) ∈ Q × Σ, q∈Q,σ∈Σ,d∈{-1,0,1} δ(p, τ, q, σ, d) = 1. A configuration is a probabilistic distribution described by a valuation function ν : Q × Σ * × Z → R + . The evolution operator F M of a PTM M is such that for any configuration ν, F M (ν) = (q, T, y) → (p,τ )∈Q×Σ,d∈{-1,0,1} δ(p, τ, q, T y-d , d)ν(p, T τ y-d , y -d).
Proposition 3. For any probabilistic Turing machine

M = (Σ, Q, δ), [M ′ ] {{c},c∈Σ×Q×{-1,0,1}}
is well observed, and has the same evolution 7 as M , where

M ′ = (Σ, Q × {-1, 0, 1}, δ ′ ) is a pQTM with δ ′ = (p, τ, q, (σ, e), d) → δ(p, τ, q, σ, d) if e = d 0 otherwise .
Proof. In order to satisfy conditions (c) and (d) of the well-observation lemma, a copy of the head move is added to the internal states of the machine, such that the total measurements of the internal states of M ′ avoid any superposition of the positions of the head, making the observable quantum Turing machine a probabilistic machine without superposition.

As a consequence, the model of observed quantum Turing machines is not only a formalisation of partial observation of properties during the evolution, but also a unifying model since quantum Turing machines and deterministic Turing machines are observable quantum Turing machines. In the next section, the computational power of observable quantum Turing machines is studied.

Computational Power of Observable Quantum Turing Machine

In this section, we mainly show that any observable quantum Turing machine can be simulated within a polynomial slowdown by a quantum Turing machine. In other words, even if the model of observable quantum Turing machines is more expressive than the model of quantum Turing machines, they have the same computational power. Theorem 1. For any OQTM [M ] K , there exists a QTM M ′ which simulates [M ] K within a quadratic slowdown.

The rest of this section is dedicated to the proof of this theorem. In order to simulate the OQTM [M ] K a two-tape QTM M is used. Multi-tape quantum Turing machines have been introduced in [START_REF] Yamakami | A foundation of programming a multi-tape quantum Turing machine[END_REF]. One of the tapes of M is used to simulate the tape of M , whereas the second tape is an history, where the superposition of the possible outcomes of an hypothetical observation according to K of the current internal state is stored. At the end of the computation, this auxillary tape is measured, simulating the observable quantum Turing machine. First, a such two-tape quantum Turing machine is defined and we prove the well-fornedness of this machine, then we prove the simulation of the original observable quantum Turing machine with a linear slowdown. Finally, this two-tape quantum Turing machine can be simulated by a one-tape quantum Turing machine within a quadratic slowdown.

For a given pQTM M = (Q, Σ, δ) and a partition where

K = {K λ , λ ∈ Λ} of Σ × Q, let M = (Q, Σ × Λ 2 ∪ {#},
[τ, p] ∈ Λ is such that (τ, p) ∈ K [τ,p] .
Notice that the second head always moves right, revealing necessary a blank symbol. That is why the transition function is partially defined. One can prove that δ verifies the well formedness conditions of unity, orthogonality, and separability -see theorem 5.2.2 in [START_REF] Bernstein | Quantum complexity theory[END_REF] for the wellformedness lemma for 1-tape QTM and lemma 1 in [START_REF] Yamakami | A foundation of programming a multi-tape quantum Turing machine[END_REF] for multi-tape QTM. Thus according to the completion lemma -lemma 2 in [START_REF] Yamakami | A foundation of programming a multi-tape quantum Turing machine[END_REF] δ can be extended such that the corresponding pQTM is well-formed.

The evolution

U M of M is such that for any p ∈ Q, x ∈ Z, n ∈ N * , T ∈ Σ * , w ∈ (Λ 2 ) n-1 , U M |p, T, x, w, n = q∈Q,σ∈Σ,λ,µ∈Λ,d∈{-1,0,1} δ(p, T x , #, q, σ, d, (λ, µ), 1)|q, T σ x , x + d, w(λ, µ), n + 1
Thus,

U M |p, T, x, w, n = µ∈Λ,(σ,q)∈Kµ,d∈{-1,0,1} δ(p, T x , q, σ, d)|q, T σ x , x + d, w([τ, p], µ), n + 1
The simulation of M by the 2-tape quantum Turing machine M works as follows: for any initial configuration ρ ∈ D(C Q×Σ×Z ) of M , the initial configuration of M is ρ ⊗ |# #| ⊗ |0 0|. It means that the internal state and the state of the first tape are the same as M , whereas the second tape is empty and the head of the second tape points out the cell indexed by 0. After n transitions, the configuration of

M is U n M (ρ ⊗ |# #| ⊗ |0 0|)U †n M .
At that time, the second head points out the cell indexed by n, and all the cells of the second tape have a blank symbol except the cells between 0 and n -1. These non-blank cells of the second tape are then measured, leading to the configuration w∈(

Λ 2 ) n w|U n M (ρ ⊗ |# #| ⊗ |0 0|)U †n M |w .
We prove, by induction on n, that this resulting configuration is equal to

F n [M]K (ρ) ⊗ |# #| ⊗ |n n|.
In order to initialize the induction, notice that the property is true after n = 0 transition. For any n > 0, the configuration of M , after n + 1 transitions and the measurement of the second tape is

ρ ′ = w∈(Λ 2 ) n+1 w|U n+1 M (ρ ⊗ |# #| ⊗ |0 0|)U †n+1 M |w = λ,µ∈Λ,w∈(Λ 2 ) n w| (λ, µ)| n+1 U n+1 M (ρ ⊗ |# #| ⊗ |0 0|)U †n+1 M |w |(λ, µ) n+1
where (λ, µ)| n means that (λ, µ)| is applied on the cell indexed by n on the second tape.

Since the second head always moves right, the transition number n + 1 does not act on the cells indexed between 0 and n -1 of the second tape, and thus commutes with any operation acting on these cells:

ρ ′ = λ,µ∈Λ,w∈(Λ 2 ) n (λ, µ)| n U M w|U n M (ρ ⊗ |# #| ⊗ |0 0|)U †n+1 M |w U † M |(λ, µ) n By induction, ρ ′ = λ,µ∈Λ (λ, µ)| n U M (F n [M]K (ρ) ⊗ |# #| ⊗ |n n|)U † M |(λ, µ) n
For any p, p ′ ∈ Q, any T, T ′ ∈ Σ * , and any x, x ′ ∈ Z,

P (λ, µ)|nU M |p, T, x, #, n p ′ , T ′ , x, #, n|U † M |(λ, µ) n λ, µ ∈ Λ = P (λ, µ)|n P δ(p, Tx, q, σ, d)δ † (p ′ , T ′ x ′ , q ′ , σ ′ , d ′ )|q, T σ x , x + d, ([Tx, p], µ0), n + 1 λ,µ∈Λ µ 0 ,µ ′ 0 ∈Λ,(σ,q)∈Kµ 0 ,(σ ′ ,q ′ )∈K µ ′ 0 ,d,d ′ ∈{-1,0,1} q ′ , T ′σ ′ x ′ , x ′ + d ′ , ([T ′ x ′ , p ′ ], µ ′ 0 ), n + 1||(λ, µ) n = P λ|[Tx, p] [T ′ x ′ , p ′ ]|λ P δ(p, Tx, q, σ, d)δ † (p ′ , T ′ x ′ , q ′ , σ ′ , d ′ )|q, T σ x , x + d, #, n + 1 λ,µ∈Λ (σ,q)∈Kµ,d,d ′ ∈{-1,0,1} q ′ , T ′σ ′ x ′ , x ′ + d ′ , #, n + 1| = P χ λ,µ |p, T, x p ′ , T ′ , x ′ |χ † λ,µ ⊗ |# #| ⊗ |n + 1 n + 1| λ,µ∈Λ = F [M ] K (|p, T, x p ′ , T ′ , x ′ |) ⊗ |# #| ⊗ |n + 1 n + 1| Thus, ρ ′ = F n+1 [M]K (ρ) ⊗ |# #| ⊗ |n + 1 n + 1|
Thus M simulates M within a linear slowdown. Since any two-tape quantum Turing machine can be simulated by a one-tape QTM within a quadratic slowdown [START_REF] Yamakami | A foundation of programming a multi-tape quantum Turing machine[END_REF], M is simulated by a one-tape QTM within a quadratic slowdown.

Conclusion and perspectives

This paper has introduced observable quantum Turing machines (OQTM) as a generalisation of quantum Turing machines (QTM) allowing partial observation of the machine during the computation. OQTM provides a formal model to deal with applications where partial observations of the machine are necessary, like the halting problem where observations are used to know whether the computation is halted or not. OQTM turns out to be a unifying model of Turing machines, since any QTM but also any deterministic TM are special instances of OQTM, whereas it is well-known that non reversible deterministic TM cannot be expressed into the formalism of QTM. However, the computational power of OQTM is equivalent to the power of QTM. Thus, the well-observation condition (condition verified by OQTM) is weaker than the well-formedness condition (condition verified by QTM) and is a good candidate to meet the necessary and sufficient conditions for a Turing machine to be a valid quantum device. Since observations are formalized in OQTM, a perspective is to investigate the connections between OQTM and recent models of quantum computation based on measurements (Teleportation-based model [START_REF] Nielsen | Universal quantum computation using only projective measurement, quantum memory, and preparation of the 0 state[END_REF][START_REF] Perdrix | State transfer instead of teleportation in measurement-based quantum computation[END_REF], One-way model [START_REF] Raussendorf | The one-way quantum computer -a non-network model of quantum computation[END_REF][START_REF] Danos | The measurement calculus[END_REF]) and the formal framework of classically-controlled quantum Turing machines [START_REF] Perdrix | Classically-controlled quantum computation[END_REF].

Indeed, the structure of the OQTM is inspired from the paradigm quantum data, classical control: quantum data are stored on the tape of the machine, while the control, thanks to the partial observation of the internal states and the cell pointed out by the cell, is hybrid. A perspective is to characterize the amount of quantum control needed to have an efficient quantum device: what is the minimal k for which any OQTM [M ] K can be efficiently simulated with an OQTM [M ′ ] K ′ where all the blocks of K ′ have a size less than k ?

Another open question is the existence of a universal OQTM. Recent developments in the quest of a universal QTM [START_REF] Fouché | Universality and programmability of quantum computers[END_REF][START_REF] Müller | Strongly universal quantum turing machines and invariance of kolmogorov complexity[END_REF] point out that existence of a classical control could be helpful for the design of a universal machine.

  τ ∈A α τ |τ , with τ ∈A |α τ | 2 = 1. Vectors, inner and outer products are expressed in the notation introduced by Dirac. Vectors are denoted |ϕ ; the inner product of two vectors |ϕ , |ψ is denoted by ϕ|ψ . If |ϕ = τ ∈A α τ |τ and |ψ = τ ∈A β τ |τ , then ϕ|ψ = τ ∈A α *

Definition 6 (

 6 e.: λ,µ∈Λ χ † λ,µ χ λ,µ = I Such a well-observed pre-quantum Turing machine is an observable quantum Turing machine: Observable quantum Turing machine). An observable quantum Turing machine (OQTM ) is a well-observed pQTM [M ] K .

  δ) be a 2-tape quantum Turing machine. The alphabet of the first tape is Σ, the alphabet of the second tape is Λ 2 ∪ {#}. The transition function δ of M is defined as follows: ∀p ∈ Q, ∀τ ∈ Σ, δ(p, τ, #) = µ∈Λ,(σ,q)∈Kµ,d∈{-1,0,1} δ(p, τ, q, σ, d)|q, σ, d, ([τ, p], µ), 1

  d∈{-1,0,1},x∈Z,T ∈Σ * , s.t. Tx=τ δ(p, T x , q, σ, d)|q, T σx , x + d p, T, x| Remark 1. Notice that χ λ,µ = P µ U M P λ , where P ν is a projector defined for any ν ∈ Λ as follows:P ν =

p∈Q,x∈Z,T ∈Σ * s.t. (Tx,p)∈Kν |p, T, x p, T, x|

M is self adjoint (or Hermitian) if and only if M † = M

M is positive-semidefinite if all the eignenvalues of M are non-negative.

The trace of M (tr(M )) is the sum of the diagonal elements of M

U is unitary if and only if U† U = U U † = I.

since T r(M N ) = T r(N M ) and for any projector P , P 2 = P .

The transition function of deterministic Turing machine is supposed to be total in this paper.

Notice that the configuration of an OQTM [M ]K is a density matrix where as a configuration of a probabilistic Turing machine M ′ is a probabilistic distribution that can be represented as a valuation function ν : Q × Σ * × Z → R + . As a consequence, we say that the evolutions of[M ]K and M ′ are the same if Φ • F [M ] K • Ψ = F M ′ ,where Ψ (ν) = P c∈Q×Σ * ×Z ν(c) |c c| and Φ(ρ) = c → c|ρ|c .


Jie Sun
email: jie.sun@irstea.fr

Gil De Sousa
email: gil.de-sousa@irstea.fr

Catherine Roussey
email: catherine.roussey@irstea.fr

Franc ¸ois Jean-Pierre Chanet
email: jean-pierre.chanet@irstea.fr

Pinet Irstea

Kun-Mean Hou
email: kun-mean.hou@isima.fr

A New Formalisation for Wireless Sensor Network Adaptive Context-aware System: application to an environmental use case

Keywords: Context-aware system, formalisation, architectur, Wireless Sensor Network, Internet of Things, environment, phenomenon

Henceforth, new generations of Wireless Sensor Networks (WSN), as part of the Internet Of Things (IoT), have to be able to adapt their behaviour to collect, from the study phenomenon (or feature of interest), quality data for long period of time. In this article, we propose a new formalisation for the design and the implementation of context-aware systems. To illustrate this whole proposition, an environmental use case, the study of flood events in a watershed, relying on a WSN for the data collection, is presented.

I. INTRODUCTION

The acquisition of heterogeneous data is essential in the era of IoT and the Big Data that is just starting. These two research topics have application in numerous fields: industry, "smart home smart care", agriculture, environment, etc. WSN technology is now viewed as part of the IoT [START_REF] Atzori | The internet of things: A survey[END_REF]. The increasingly use of WSN envisioned at the beginning of the 2000's [START_REF] Akyildiz | Wireless sensor networks: a survey[END_REF], is now a reality as shown, for example, in environment [START_REF] Othman | Wireless sensor network applications: A study in environment monitoring system[END_REF] and agriculture [START_REF] Ur Rehman | A review of wireless sensors and networks' applications in agriculture[END_REF]. In these applications, a WSN collects natural phenomenon observations (temperature, humidity, etc.) and send them to a context-aware system, which may propose adaptation actions based on context. To build a full context adaptation service, information about wireless sensors themselves such as their energy level are also required. Indeed, despite steady progress in hardware (the development of low energy communication modules for example), a wireless sensor still has scarse resources. It is the case for "scalar" WSN and it is even more for Wireless Multimedia Sensor Networks (WMSN) [START_REF] Akyildiz | A survey on wireless multimedia sensor networks[END_REF]. Thus, to better use these limited resources, all the system components involved in data acquisition process have to work together in a cooperative way, from the component that collects raw data to the one that provides indicators to end users. Generally, these components are the wireless sensors, the gateway(s) and the remote Decision Support System (DSS). The acquisition and transmission frequencies required by the DSS, through the gateway, have to be consistent with the energy available at the level of the wireless sensors. For some alert applications such as fire prevention, data transmission is sometimes more important than the "survival" of a node of the network. Thus, all the components implied in the data acquisition process have to adapt their behaviours to the context in order to achieve the best performances. A WSN is also subject to unpredictable events that, without fast interventions, can threaten the stability of the whole system. The combination of the common decisions and actions is the issue addressed in this paper. More precisely, we propose a formalisation to define high level context which, integrated into an adaptive contextaware system, will be used to reduce the number of exchanged communication packets. Section II presents the main existing concepts related to context-aware systems. Section III of the article explains our proposition of formalisation of context in order to build any context system based on WSN. Section IV shows its application with the design of a context-aware system dedicated to a complex environmental use case. Section V presents our implementation of this formalisation in order to develop a context-aware system and an adaptive contextaware one focused on the previous environmental use case.

The second system adapts its behaviour to the context in order to limit packet exchanges. Section VI presents different context systems developed for the same purpose. The last section concludes this article.

II. CONTEXT-AWARE SYSTEM MAIN CONCEPTS

One of the most known and accepted definition of context is given by [START_REF] Dey | Towards a better understanding of context and context-awareness[END_REF] as Context is any information that can be used to characterize the situation of an entity. An entity is a person, place, or object that is considered relevant to the interaction between a user and an application, including the user and applications themselves. As indicated in this definition, context is focused on one entity. Several contexts can be defined, for example, the context of the user, the context of the device running the application, and so on. As explained in [START_REF] Perera | Context aware computing for the internet of things: A survey[END_REF], different categories of context exist. Low level context corresponds to the raw data acquired by sensors or static data provided by users. High level context is computed from the low level one, with more informative data associated to the application and the user. The Figure 1 presents the processes associated to an adaptive context-aware system when data are collected by a WSN. It could also be applied to sensor networks or other systems that generate raw data.

In an adaptive context-aware system, different processes are required:

• Context acquisition: collecting raw data and metadata that are useful to build the context. • Context modeling: organisation of the collected data through a specific context data model. The process gives an interpretation to each raw data. For example, the value 24 becomes the measurement of the outdoor temperature in degree Celsius. This process builds the low level context. This process is also called annotation or tagging [START_REF] Perera | Context aware computing for the internet of things: A survey[END_REF]. • Context reasoning: the high level context is computed or inferred from the low level one. This process can imply different approaches based on machine learning [START_REF] Goumopoulos | Automated zonespecific irrigation with wireless sensor/actuator network and adaptable decision support[END_REF] or rule engine [START_REF] Jajaga | An expert system for water quality monitoring based on ontology[END_REF]. • Context distribution: diffusion of the high level context to the different consumers, for example, the end user or any system components are able to adapt their actions according to the current context. • Context adaptation: actions to adapt any system components according to context changes.

Note that a context-aware system stops at the context distribution process and sends alert to the end users.

III. PROPOSED CONTEXT FORMALISATION

The work in [START_REF] Bendadouche | Extension of the semantic sensor network ontology for wireless sensor networks: The stimulus-wsnnode-communication pattern[END_REF] define the concept of entity "state" as a qualitative data which changes over times (summarizing a set of information). Based on this definition, we propose a new definition of "context" as a set of entities characterized by their state, plus all information that can help to derive any state changes of these entities In our context-aware system formalisation, we add the definition of two classes of entities: If we take the example of a wireless sensor management application, we consider a wireless sensor as an entity of interest where one of its associated observable entities is its power supply (a battery). From this observable entity, a sensor measures a charge/an energy level as a raw data observation or low-level context. Based on capacity and charge values, we deduce the percentage of energy remaining in the battery. This percentage is represented by the variable Energy. Figure 3 presents an example of finite-state machine used to deduce the energy state (high, middle or low) of the battery which is its high level context. The number of states and entities depends on the application requirements. Any hardware component, such as memories, of a wireless sensor can be added in our context formalisation. It can also be applied to software such as the operating systems. The number of system failures or watchdog calls constitutes raw observation data to derive states of the associated observable entities. The state of a wireless sensor will then be deduced from all the considered (hardware and software) entity states. These different entities and their state enrich the context. Thus, there are different contexts according to different entities and their state. However, The complexity of the deduction process increases with the number of relevant entities analysed. Providing entities and states in limited number is essential to have a highly dynamic contextaware system but this should not be at the expense of the quality of the final application decision. In the WSN topic, another possible use of this formalisation is for link quality evaluation application. This problem is well-known in routing protocols. Different metrics can be considered such as the available bandwidth, the latency, the available energy in the neighbourhood nodes and others [START_REF] Draves | Comparison of routing metrics for static multi-hop wireless networks[END_REF]. The Quality of Service (QoS) of a link can be deduced from different observable entities: the connected nodes, the bandwidth. Our context formalisation can be improved depending on the complexity of the application requirements. For example, a wireless sensor management application wants to evaluate if a wireless sensor can communicate. The states of the wireless sensor entity (the entity of interest) are able to communicate or not able to communicate. Its state will be deduced from the link entity and the battery entity (enough energy to communicate). For a WSN management application, its entity of interest is the WSN. The state of the WSN could be computed from the states of all its wireless sensors (or nodes). Its connectivity state could be calculated from the QoS of all the links between its wireless sensors. At the end, the application can just need the states of the WSN, established from the states of all its nodes and of the gateway(s). Thus, we divide the context and the reasoning in several parts. Each part can be supported by different components of the context-aware system. If the two steps of the reasoning process is supported by two different components, the first component that deduces the high level context of an observable entity (its state) can communicate it to the second component. For performance reason, it would be better to communicate only the changing state events (with the associated value). In the following section, a context-aware system is built for an environmental use case. We experiment our formalisation on it.

IV. ENVIRONMENTAL APPLICATION USE CASE

The considered environmental application is a watershed monitoring system which is able to send alert about flood risk. As shown in Figure 4, the application uses a WSN for data acquisition. This network is composed of wireless sensors, called "Water flow node", equipped with stream gauge measuring the water flow rate. One of these wireless sensors is located on the outlet of the watershed. The network contains also "Precipitation nodes" measuring the precipitation quantity. All the measurements are sent to a DSS. This DSS deduces the risk or the occurrence of a flood and send it to users. One of our assumptions is that the WSN has a star topology: each node communicates directly with the DSS, we do not introduce routing protocol constraints at this step.

In the application, we define four entities:

1) the Precipitation entity which is an observable one. Its state is calculated from the data collected by the "Precipitation nodes" located at different points of the watershed. The Precipitation entity (P ) has two states: high and low. 2) the WaterCourse entity which is an observable one.

Its state is calculated from the data collected by the "water flow nodes" located at different points of the tributary stream (WaterCourses). The WaterCourse (W ) entity has two states: high and low. 3) the Outlet entity which is also an observable one.

Its state is calculated from the data collected by the "water flow node" located on the outlet of the watershed. The Outlet entity (O) has two states: high and low. 4) the Flood entity is the entity of interest of the application. The flood entity is not an observable entity but its state depends on the states of all the observable entities. The Flood entity has four states "Normal", "Rain", "Risk", "Flood". Normal state means there is no risk. Rain state means that the watershed has received lot of precipitations, but there is no flood. Risk state means that flood is coming. Flood state means that the flood is there, the main river is overflowing. Application users want to know as soon as possible when a risk state is reached.

All the measurements are stored in the context data model in order to build the low level context. Several reasoning steps will be proposed in order to build the high level context of the Flood entity:

1) The precipitation measurements from the various "Precipitation nodes" are aggregated. One threshold should be set on the aggregation value in order to determine when the Precipitation entity moves from the low to the high state and vice versa.

2) The water flow measurements from the various stream gauges, which equip "Water flow nodes" located in the WaterCourses, are aggregated. One threshold should be set on the aggregation value in order to determine when the WaterCourse entity moves from the low to the high state and vice versa. 3) Based on the measurements of the stream gauge that equips the "Water flow node" located at the Outlet, one threshold should be set in order to determine when the Outlet entity moves from the low to the high state and vice versa. 4) The Figure 5 presents the finite-state machine that deduces the state of the Flood entity from the states of the three other observable entities. This diagram follows every step of the emergence of a flood. Usually, when a flood event occurs, the Flood entity will move from the "Normal (F1)" state to the "Rain (F2)" one, proceed to the "Risk (F3)" one and finish with the "Flood (F4)" one.

Based on the use case mentioned above, we can see

V. FORMALISATION USE IN SIMULATION

To implement our formalisation, we extend the simulation system based on the multi-agent system JADE (Java Agent DEvelopment Framework) as introduced in [START_REF] Bendadouche | Extension of the semantic sensor network ontology for wireless sensor networks: The stimulus-wsnnode-communication pattern[END_REF]. There are 3 main features that JADE has: 1) Agent communication : Exchange messages among the agents.

2) Content of message modelization by Ontology :

JADE uses ontology to model the exchanged message contents between agents. 3) Integration with other tools : JADE can use tools like Jess [START_REF] Friedman-Hill | Jess in Action: Java Rule-Based Systems[END_REF] in a Java language framework as a decision component of an agent, so the agents in multi-agent systems are more intelligent.

However, current implementations based on JADE are very basic. The work in [START_REF] Subercaze | APPLICATION AUX COMMUNAUTS VIRTUELLES DE CONNAISSANCES[END_REF] only realizes basic agent communication. It does not care about the content of message modelization and other tools integration. In our simulation, we implement all the 3 features as shown in Figure 6. We use Ontology to model the content of exchange messages among the agents, meanwhile we can get low level context of observable entities e.g. rainfall amount last 24 hour. Then we can use Jess to infer and acquire the high level context of observable entities e.g. Precipitation state; thus, high level context of entity of interest e.g. Flood state is inferred from those the high level context of observable entities by Jess. As mentioned in [START_REF] Perera | Context aware computing for the internet of things: A survey[END_REF], the context modeling is often based on ontologies. Ontologies are defined by [START_REF] Studer | Knowledge engineering: Principles and methods[END_REF] as an formal explicit specification of a shared conceptualization. According to W3C, ontologies are vocabularies that define the concepts and relationships used to describe and represent an area of concern. Thus, ontologies provide meaning to data (as data model do). Our ontology is based on Semantic Sensor Network ontology (SSN) proposed by the W3C [START_REF]The ssn ontology of the w3c semantic sensor network incubator group[END_REF]. This ontology is a nucleus on which other ontologies can be connected, in order to develop a full context data model. The main concepts of SSN that we reused are "Sensor", "FeatureOfInterest", "Property", "Observation". Our observable entities or entity of interest are defined in SSN as "FeatureOfInterest". Possible entities can also come from some dedicated ontologies such as the Climate and Forecast ontology [START_REF] Group | Climate and Forecast (CF) features[END_REF] or the SWEET ontology [START_REF]Semantic Web for Earth and Environmental Terminology (SWEET)[END_REF]. To describe time stamp, we reuse the Time ontology proposed by the W3C [START_REF] Hobbs | Time Ontology in OWL, W3c Working Draft 27[END_REF]. We use the QU ontology to define the unit [START_REF] De Koning | Library for Quantity Kinds and Units: schema, based on QUDV model OMG SysML(TM), Version 1.2[END_REF]. To describe the state of our entities, we reuse the ontology proposed in [START_REF] Bendadouche | Extension of the semantic sensor network ontology for wireless sensor networks: The stimulus-wsnnode-communication pattern[END_REF]. Concerning the reasoning process, we use the rule-based engine called Jess as indicated above. We define several rules sets. Some are dedicated to infer the observable entity state based on predefined thresholds and aggregation values. Others are dedicated to infer the state of the Flood entity. For example, Figure 8. Flood context-aware system the following rule deduces the state "Normal (F1)" of the Flood entity from states of observable entities.

We implement two systems where the DSS receives all the measurements and perform all the reasoning processes. These systems use the same WSN composed of heterogeneous wireless sensors to collect precipitation quantities, the WaterCourses and the outlet flow rates. Figure 8 is a UML sequence diagram that presents the operating mode of "system 1", a context-aware one that send the Flood entity state to end user. The three different types of wireless sensors, previously mentioned, are represented by: "PrecipitationNode", "WaterCourseNode" (for the "water flow nodes" located in the tributary stream), "OutletNode" (for the "water flow node" located in the outlet).

Based on the previous system, we develop an adaptive context-aware one, "system 2", presented in Figure 9. The adaptation decision is implemented by the DSS. It deduces a new communication frequency for each wireless sensor based on the Flood entity state. Using our simulation architecture, we have compared these two systems at the level of the total amount of exchanged communication packets, using onemonth data collected on a watershed. We use the data provided by [START_REF] Tallec | Observatoire oracle[END_REF]. Three "PrecipitationNodes", two "WaterCourseNodes" and one "OutletNode" are considered in our simulation. In JADE, we define as many agents as nodes. We also add a DSS agent. Each node agent acquires raw observation data and sends them to DSS. The acquisition frequency is of one measurement every minute. In the "system 1", the acquisition and the transmission frequencies are equals. In the "system 2", the transmission frequency is modulated (calculated by the DSS) as shown in Figure 9. The DSS agent processes the context modeling in order to build the low level context. It infers the high level context from the low level one using Jess rule engine. Figure 10 shows the obtained results. The nodes of the "system 1" has transmitted near 250000 packets. With the "system 2", the number of transmitted message is reduced to less than 100000 packets. In terms of the phenomenon monitoring quality, the two systems detect the same number of state changes.

VI. RELATED WORK

No system of this type dedicated to flood monitoring was found. However, a context-aware system for water quality management exits. The InWaterSense project proposes a contextaware system to deduce the water quality of any water bodies (lake, river) [START_REF] Jajaga | An expert system for water quality monitoring based on ontology[END_REF] [21]. Their system is totally built using semantic web technologies. SSN ontology is used as a nucleus in order to build the context model. They also use the Jess rule based engine. Their rule format is based on SQWRL language. It is able to build aggregation value using rules. Thus, their rules merge the characteristics of observable entities and those of the entity of interest. Their rules infer the state of the water body without intermediate steps. Compare to our approach, their rules are much more difficult to manage due to their complexity. Our formalisation eases the reasoning process by splitting it into several steps: deduction of the high level context of observable entities; then, deduction of the high level context of the entity of interest.

The work of [START_REF] Kasi | SEPSen: semantic event processing at the sensor nodes for energy efficient wireless sensor networks[END_REF] proposes a WSN architecture called "Sepsen" in order to integrate, in nodes, several components: semantic annotator based on fragments of ontology, rule-based engine and a knowledge base that stores events. The goal is to decrease the number of event messages between sensors by classifying them as share, forward or discard event. The share events are sent to other sensor nodes to update their knowledge base. The forward events are sent to the gateway. The discarded events are removed. However, the semantic annotation is done manually. The rule indicates that a sensed value should be above a threshold in order to become a share or forward event. Using the PowerTOSSIM environment, the "Sepsen" architecture is applied on a simulation scenario showing the energy saving which this kind of approach can bring.

None of these systems uses the same formalisation based on observable entities, entity of interest and states. Thus, even if all these systems use a rule-based engine and ontologies, their rules are very complex and hard to maintain. The Semsorgrid4Env project [START_REF]A Semantically Enabled Service Architecture for Mashups over Streaming and Stored Data[END_REF] wants to help coastal flood planning managers to make decisions during coastal flooding events. It proposes a mash-up application that integrates heterogeneous datasets: sensor data stream, historical database. The integration is made possibly by a set of ontologies: SSN, SWEET, etc. In this project, the context is not modeled explicitly.

When dealing with complex phenomenon like natural disaster, context-aware systems based on WSN become situation awareness system based on WSN. In this type of system, the data management model is composed of different layers (sensor data, aggregation data, situation representation knowledge) [START_REF] Stocker | Abstractions from Sensor Data with Complex Event Processing and Machine Learning[END_REF]. Our formalisation can be integrated in the situation layer. In [START_REF] Stocker | Abstractions from Sensor Data with Complex Event Processing and Machine Learning[END_REF], a situation is defined as the representation of a "structured part of the reality". It contains all the description of entities involved in the situation. Context is a point of view of one entity about the situation.

VII. CONCLUSION AND PERSPECTIVES

In this article, we have proposed a new formalisation for the design and the implementation of context-aware systems. One of its advantages is that our approach can be used for multiple purposes. It can integrate both the monitoring of the studied phenomenon (feature of interest) and the management of the hardware and the software system used to observe it. More generally, it provides a unified way to deal with all the components/entities of an observation process. This formalisation can be used in different application topics related to agriculture, environment, "smart care smart home", industry. To illustrate its use, we have provided an environmental use case application: the study of flood events in a watershed. In the Irstea institute, we have different data related to this topic and we will continue the implementation and the experiment of our approach in this application field. A simulation architecture is provided to evaluate systems developed using our formalisation. This architecture is based on the ontology concept with the use of the multi-agent system JADE and the rule-based engine Jess (those are both Java language tools). Different scenarios for this environmental application will be proposed in our future work taking into account different states and extended wireless sensors reasoning capabilities. Our application will also be implemented with tools suitable for the limited resources of wireless sensors.

Figure 1 .

 1 Figure 1. Context cycle of an application based on WSN

Figure 3 .

 3 Figure 3. Example of wireless sensor energy finite-state machine

Figure 4 .

 4 Figure 4. Example of watershed monitoring

Figure 5 .

 5 Figure 5. Example of flood finite-state machine

Figure 6 .

 6 Figure 6. Simulation architecture

( d e f

  r u l e f l o o d S t a t e N o r m a l F 1 ( d e c l a r e ( s a l i e n c e 1 0 ) ) ? p <-( p l u v i o { s t a t e == low } ) ?w <-( W a t e r C o u r s e { s t a t e == low } ) ? o <-( o u t l e t { s t a t e == low } ) ? f <-( f l o o d ) => ( m o d i f y ? f ( s t a t e f 1 ) ) )

Figure 7 .

 7 Figure 7. Rule of Normal state of Flood entity

Figure 9 .Figure 10 .

 910 Figure 9. Flood adaptive context-aware system

Tenth International Conference on Sensor Technologies and Applications SENSORCOMM 2016, July 24-28th, Nice, France

ACKNOWLEDGMENT

This research is partly funded by the grant of the French Auvergne region, and now in the new Auvergne-Rhône-Alpes region (temporary name) and, the grant of the European Regional Development Fund (ERDF). The authors would like to thank the team of the Orgeval observatory for their help.