Arnaud Carayol

Zoltán Ésik

A context-free linear ordering with an undecidable first-order theory

The words of a context-free language, ordered by the lexicographic ordering, form a context-free linear ordering. It is well-known that the linear orderings associated with deterministic context-free languages have a decidable monadic second-order theory. In stark contrast, we give an example of a context-free language whose lexicographic ordering has an undecidable first-order theory.

Introduction

When the alphabet of a language L is linearly ordered, we may equip L with the lexicographic ordering. It is known that every countable linear ordering is isomorphic to the lexicographic ordering of a (prefix) language.

The lexicographic orderings of regular languages (i.e., the regular linear orderings) were studied in [1-4, 12, 15, 20, 24, 28]. These linear orderings agree with the leaf orderings of the regular trees, and are all automatic linear orderings as defined in [START_REF] Khoussainov | Automatic linear orders and trees[END_REF]. It follows from results in [START_REF] Heilbrunner | An algorithm for the solution of fixed-point equations for infinite words[END_REF] that all scattered regular linear orderings have finite Hausdorff rank, or finite condensation rank (FC-rank), as defined in [START_REF] Rosenstein | Linear Orderings[END_REF]. In fact all automatic linear orderings have finite FC-rank [START_REF] Khoussainov | Automatic linear orders and trees[END_REF]. Moreover, an ordinal is the order type of a regular well-ordering if and only if it is strictly less than ω ω .

The study of the lexicographic orderings of context-free languages (contextfree linear orderings) was initiated in [START_REF] Bloom | Regular and algebraic words and ordinals[END_REF] and further developed in [START_REF] Bloom | Algebraic ordinals[END_REF][START_REF] Bloom | Algebraic linear orderings[END_REF][START_REF] Carayol | The FC-rank of a context-free language[END_REF][START_REF] Ésik | An undecidable property of context-free linear orders[END_REF][START_REF] Ésik | Scattered context-free linear orders[END_REF][START_REF] Ésik | Hausdorff rank of scattered context-free linear orders[END_REF] and was extended to languages generated by deterministic higher order grammars in [START_REF] Braud | Linear orders in the pushdown hierarchy[END_REF].

It follows from early results in [START_REF] Courcelle | Fundamental properties of infinite trees[END_REF] that the lexicographic orderings of deterministic context-free languages are (up to isomorphism) identical to the leaf orderings of the algebraic trees, cf. [START_REF] Bloom | Algebraic ordinals[END_REF]. In [START_REF] Bloom | Regular and algebraic words and ordinals[END_REF], it was shown that every ordinal less than ω ω ω is the order type of a deterministic context-free linear ordering and it was conjectured that a well-ordering is isomorphic to a context-free linear ordering if and only if its order type is less than ω ω ω . This conjecture was confirmed in [START_REF] Bloom | Algebraic ordinals[END_REF] for deterministic context-free linear orderings, and in [START_REF] Ésik | Hausdorff rank of scattered context-free linear orders[END_REF] for context-free linear orderings. Moreover, it was shown in [START_REF] Bloom | Algebraic linear orderings[END_REF] and [START_REF] Ésik | Hausdorff rank of scattered context-free linear orders[END_REF] that the FC-rank of every scattered deterministic context-free linear ordering and in fact every scattered context-free linear ordering is less than ω ω . Since the FC-rank of a well-ordering is less than ω ω exactly when its order type is less than ω ω ω , it follows in conjunction with results proved in [START_REF] Bloom | Regular and algebraic words and ordinals[END_REF] that a well-ordering is isomorphic to the lexicographic ordering of a context-free language or deterministic context-free language if and only if its order type is less than ω ω ω . Exactly the same ordinals are the order types of the tree automatic well-orderings, see [START_REF] Delhommé | Automaticité des ordinaux et des graphes homogènes[END_REF]. Eventually, it was proved in [START_REF] Carayol | The FC-rank of a context-free language[END_REF] that the FC-rank of every context-free linear ordering is less than ω ω . However, the question whether there exists a context-free linear ordering that is not a deterministic context-free linear ordering remained open.

Since deterministic context-free linear orderings belong to the pushdown hierarchy [START_REF] Carayol | The Caucal hierarchy of infinite graphs in terms of logic and higher-order pushdown automata[END_REF][START_REF]On infinite terms having a decidable monadic theory[END_REF][START_REF]On infinite transition graphs having a decidable monadic theory[END_REF][START_REF] Ong | On model-checking trees generated by higher-order recursion schemes[END_REF], they all have decidable monadic second-order theories. In fact, there exists an algorithm that takes two inputs, an LR(1) grammar (or equivalently a deterministic pushdown automaton) and a sentence of the monadic second-order logic of linear orders and tells whether the sentence holds in the lexicographic ordering of the language generated by the grammar. Such a decision procedure does not exist for all context-free grammars and monadic second-order or even first-order sentences, since as shown in [START_REF] Ésik | An undecidable property of context-free linear orders[END_REF], it is undecidable to tell whether a context-free linear ordering (given by a context-free grammar) is dense. In contrast, it is decidable whether a context-free linear ordering is a well-ordering or a scattered ordering.

In this paper we prove that there is a context-free linear ordering whose first-order theory is undecidable. Thus there exists a context-free linear ordering which is not the lexicographic ordering of a deterministic context-free language. The context-free language defining this linear ordering is a finite disjoint union of deterministic context-free languages. Hence our undecidability result holds for the class of unambiguous context-free linear orderings.

As a corollary, we also obtain the existence of a (unambiguous) context-free language whose associated tree has an undecidable monadic second-order theory. The tree of a language is composed of the set of all prefixes of the words of the language as set of vertices, and its ancestor relation is simply the prefix relation. This result in turn proves the existence a context-free language that cannot be accepted by any deterministic collapsible pushdown automaton (an extension of the classical notion of pushdown automaton with nested stacks and links [START_REF] Hague | Collapsible Pushdown Automata and Recursion Schemes[END_REF]), as shown previously by Pawe l Parys using a pumping argument [START_REF] Parys | Higher-order stacks can not replace nondeterminism[END_REF].

The paper is organised as follows. In Section 2, we recall basic definitions on linear orderings. Definitions concerning first-order logic and the structures associated with languages are given in Section 3. Section 1 presents our main result and its corollaries are given in Section 5. Section 6 concludes the paper.

A piece of notation: for a nonnegative integer n, we will denote the set {1, . . . , n} by [n].

When A is an alphabet, we let A * denote the set of all finite words over A, including the empty word . The set A + is A * -{ }. We let u R denote the mirror image of a word u ∈ A * .

A linear ordering [START_REF] Rosenstein | Linear Orderings[END_REF] (I, <) is a set I equipped with a strict linear order relation <. As usual, we will write x ≤ y for x, y ∈ I if x < y or x = y. A linear ordering (I, <) is finite or countable if I is. A morphism of linear orderings is an order preserving map. Note that every morphism is necessarily injective. When (I, <) and (J, < ) are linear orderings such that I ⊆ J and the embedding I → J is a morphism, we call (I, <) a subordering of (J, < ). In this case the relation < is the restriction of the relation < onto I and we usually write just I for (I, <).

An isomorphism is a bijective morphism. Isomorphic linear orderings are said to have the same order type. The order types of the positive integers N, negative integers N -, all integers Z, and the rationals Q, ordered as usual, are denoted ω, ω * , ζ and η, respectively. As usual, the finite order types may be identified with the nonnegative integers.

Recall that a linear ordering (I, <) is dense if it has at least two elements and for every x, y ∈ I with x < y there is some z ∈ I with x < z < y. A quasi-dense linear ordering is a linear ordering that has a dense subordering, and a scattered linear ordering is a linear ordering that is not quasi-dense. For example, N and Z are scattered, Q is dense, and the ordering obtained by replacing each or some point in Q with a 2-element linear ordering is quasi-dense but not dense. Clearly, every subordering of a scattered linear ordering is scattered. It is well-known that a linear ordering is quasi-dense if and only if it has a subordering of order type η. Moreover, up to isomorphism, there are 4 countable dense linear orderings, the ordering Q of the rationals possibly equipped with a least or greatest element, or both.

When (I, <) is a linear ordering and for each i ∈ I, (J i , < i ) is a linear ordering, the ordered sum i∈I

(J i , < i )
is the disjoint union i∈I (J i × {i}) equipped with the order relation (x, i) < (y, j) if and only if either i < j, or i = j and x < i y. When each (J i , < i ) is the linear ordering (J, < ), we call the ordered sum the product of (I, <) and (J, < ), denoted (I, < ) × (J, < ). Finite ordered sums are also denoted as (

I 1 , < 1 ) + • • • + (I n , < n ).
Since the operation of ordered sum preserves isomorphism, we may also define ordered sums of order types. For example, 1 + η + 1 is the order type of the rationals equipped with both a least and a greatest element. It is known that every scattered sum of scattered linear orderings is scattered. This means that if (I, <) is scattered as is each (J i , < i ), then i∈I (J i , < i ) is also scattered. A sum over a dense linear ordering (I, <) is referred to as a dense sum.

A signature is a ranked set σ of symbols. We let |R| denote the arity (≥ 1) of the symbol R. A relational structure S over σ is given by a tuple (D, (R S ) R∈σ ), where D is the domain of S, and where for all R ∈ σ, the interpretation of R in S denoted R S is a subset of D |R| . When S is clear from the context, we just write R for its interpretation R S .

Let S = (D, (R S ) R∈σ ) and S = (D , (R S ) R∈σ ) be two structures over σ. An isomorphism h from D to D is a bijection from D to D such that for all R ∈ σ and for all u 1 , . . . , u |R| ∈ D, (u 1 , . . . , u |R| ) ∈ R S if and only if (h(u 1 ), . . . , h(u |R| )) ∈ R S . We let S ∼ = S denote the existence of an isomorphism between S and S .

A linear ordering (I, < I ) is naturally represented as a structure over the signature σ ord with one symbol < of arity 2. Its domain is the set I and the symbol < is interpreted as < I .

First-order formulas use first-order variables, which are interpreted by elements of the structure and are denoted by lower case letters x, y . . .. Atomic first-order formulas are of the form R(x 1 , . . . , x |R| ), where R is a relation symbol from the signature and x 1 , . . . , x |R| are first-order variables, or x = y for firstorder variables x, y with the obvious semantics. Complex formulas are built as usual from atomic ones by the use of Boolean connectives and quantifiers. Free and bound occurrences of variables in a formula are defined as usual. We write ϕ(x 1 , . . . , x n ) to denote that the formula ϕ has free variables in {x 1 , . . . , x n }. A closed formula has no free variables.

For a formula ϕ(x 1 , . . . , x n ) and elements of the domain u 1 , . . . , u n , we write S |= ϕ[u 1 , . . . , u n ] to denote that the structure S satisfies the formula ϕ when the free variable x i , i ∈ [n], is interpreted as u i . For a closed formula ϕ, we simply write S |= ϕ.

For example, the following formula over the signature σ ord expresses that the structure is a linear ordering:

∀x ∀y x < y → ¬(y < x) ∧ ∀x ∀y x < y ∨ y < x ∨ x = y ∧ ∀x ∀y ∀z (x < y ∧ y < z) → x < z

First-order interpretations

First-order interpretation is a transformation defining a structure in another structure using first-order logic. Definition 1. A first-order interpretation from a signature σ to a signature σ is given by a tuple (δ, (ϕ R ) R∈σ ), where δ is a formula over σ with one free variable x 1 , and for each symbol R ∈ σ , ϕ R is a formula over σ with free variables x 1 , . . . , x |R| .

Applying a first-order interpretation I to a structure S over the signature σ gives rise to a structure over the signature σ , denoted I(S). Its domain is the

set D = {u ∈ D | S |= δ[u]}. A symbol R ∈ σ is interpreted in I(S)
as the set of all tuples satisfying ϕ R :

{(u 1 , . . . , u |R| ) ∈ (D ) |R| | S |= ϕ R [u 1 , . . . , u |R| ]}.
An example of first-order interpretation is given in Section 3.2.

Structures associated with words and languages

Let A be a finite alphabet. A word w over A can be represented by a structure over the signature σ A = {P a | a ∈ A} ∪ σ ord with |P a | = 1 for all a ∈ A. This structure, denoted S w , has the set [|w|] of positions in the word as its domain. The symbol < is interpreted (in S w ) as the natural order and for all a ∈ A, P a is interpreted as the predicate marking all occurrences of the letter a.

For A = 2 = {0, 1}, the formula ϕ over the signature σ A given below expresses that a word starts with the letter 0 (i.e., for all w ∈ A * , S w |= ϕ if and only if w stars with 0) : ∃x (∀y ¬(y < x) ∧ P 0 (x)) .

Similarly, when L ⊆ A * , we define the structure S L over the signature σ A associated with a language L. This structure is obtained by taking the disjoint union of all the structures S w for w ∈ L. Note that as soon as L contains two nonempty words, the relation < is no longer a linear ordering.

The following formula is satisfied by the languages in which all nonempty words start with the letter 0. ∀x (∀y ¬(y < x) → P 0 (x))

0 1 0 1 1 0 1 1 1 0 < < < < < < < < < < Fig. 1.
The structure SL associated with the language L = 1 * 0.

Lexicographic ordering and countable words associated with a language

We will consider countable linear orderings that arise as lexicographic orderings of languages. Suppose that A is an alphabet which is linearly ordered by the relation <. Then we define a strict partial order < s on A * by u < s v if and only if u = xay and v = xbz for some x, y, z ∈ A * and a, b ∈ A with a < b. We also define u < p v if and only if u is a proper prefix of v, and u < v if and only if u < s v or u < p v. The lexicographic order relation < turns A * into a linear ordering. In particular, any language L ⊆ A * gives rise to a structure over the signature σ ord denoted O L and called the lexicographic ordering of L. The domain of O L is the language L and the symbol < is interpreted as the lexicographic ordering < . We say that a language L ⊆ A * is scattered, dense, etc. if its lexicographic ordering has the corresponding property. Moreover, we say that a lexicographic ordering is a regular or a context-free linear ordering if it is isomorphic to the lexicographic ordering of a regular or context-free language. Deterministic context-free linear orderings are defined in the same way.

Example 1. Consider the alphabet 2 = {0, 1} ordered by 0 < 1. The lexicographic ordering of the regular language 1 * 0 is of order type ω and is depicted below.

0 10 110 1110 < < < < < <
Similarly the lexicographic orderings of the regular languages 0 * 1, 0 + 1 + 1 + 0 are of order type ω * and ζ, respectively. The lexicographic ordering of (00+11) * 01 is η. The context-free linear ordering ( n≥0

1 n 0(1 * 0) n , < ) is of order type 1 + ω + ω 2 + • • • = ω ω .
The context-free linear orderings ( n≥1 1 n 0(0(0 + 1 + 1 + 0) + 10 <n ), < ) and ( n≥1 1 n 0(0(00 + 11

) * 01 + 1(1 * 0) n ), < ) have respective order types ζ + 1 + ζ + 2 + • • • and η + ω + η + ω 2 + • • •.
A countable word (called arrangement in [START_REF] Courcelle | Frontiers of infinite trees[END_REF]) over an alphabet B is a countable linear ordering whose elements are labelled by letters of B. Each language over an ordered alphabet A not containing the empty word gives rise to a countable word W L over A, which is represented by a structure over the signature σ A . Its domain is the language L. The symbol < is interpreted as the lexicographic order < , and for all a ∈ A, P a is interpreted as the set of words of L ending with the letter a. We say that a countable word is context-free if it is isomorphic to the countable word of some context-free language.

Lemma 1. Every context-free linear ordering (resp. word) can be represented by a prefix context-free language not containing the empty word.

Proof. We establish the result for context-free words. Let A = {a 1 , . . . , a n } with a 1 < • • • < a n , and let L ⊆ A + be a context-free language which does not contain the empty word.

Let A = {a 1 , . . . , a n } be an alphabet disjoint from A and let π : A * → (A ) * be the morphism mapping a i to a i for all i ∈ [n].

Consider the context-free language L over A ∪ A ordered by

a 1 < • • • < a n < a 1 < • • • < a n defined by L = {π(wa)a | wa ∈ L and a ∈ A}.
The language L is prefix (as L is included in (A ) + A and A and A are assumed to be disjoint). To conclude the proof, we observe that the mapping θ : L → L mapping wa ∈ L to π(wa)a ∈ L is an isomorphism from W L to W L .

Context-free words are clearly closed under substitution. Thus we have: Lemma 2. Let L be context-free language over an ordered alphabet A which does not contain the empty word, and suppose that for each a ∈ A, P a is a context-free linear ordering. Then the ordered sum

u∈L P λ(u)
where λ(u) designates the last letter of u, obtained by replacing each u ∈ L ending with a ∈ A by a copy of P a , is a context-free linear ordering.

Proof. By Lemma 1, we can assume w.l.o.g. that L is prefix. For all a ∈ A, let L a be a context-free language (which does not contain the empty word) defining the context-free linear ordering P a . The ordered sum u∈L P u(|u|) is isomorphic to the context-free linear ordering defined by

{waL a | wa ∈ L and a ∈ A}.
This property in turn implies that context-free words can be defined in context-free linear orderings. Lemma 3. Let A be an ordered alphabet and let L be a context-free language not containing the empty word. There exists a context-free language L and a first-order interpretation I such that W L is isomorphic to I(O L ).

Proof. Let L be a context-free language not containing the empty word over the alphabet A = {a 1 , . . . , a n }. Consider the linear ordering O obtained by replacing in W L each vertex labelled a i by a copy of a linear ordering of order type ζ + i + ζ. As for all i ≥ 0, ζ + i + ζ is a context-free linear ordering, we obtain by Lemma 2 that O is a context-free linear ordering. Let L be a context-free language such that O L is isomorphic to O.

We now define a first-order interpretation transforming O L into W L . The first-order interpretation I only keeps vertices that have no predecessor. These vertices correspond to the first vertex in between two consecutive copies of ζ. Therefore these vertices are in a one to one correspondence with the elements of L. The order relation < is inherited by I. The predicate P a1 is defined for those vertices with no successors, hence guaranteeing that the vertex (which must have no predecessor) lies in a copy of ζ + 1 + ζ. Similarly P a2 is defined for vertices having a successor with no successor, etc. Formally the interpretation is defined by

δ(x) = ∀y ¬Succ(y, x) ϕ < (x, y) = x < y ϕ Pa i (x 1 ) = ∃x 2 . . . ∃x i j∈[i-1] Succ(x j , x j+1
) ∧ ∀y ¬Succ(x i , y) where Succ(x, y) is the formula expressing that y is the successor of x.

Tree of language

The tree of a language L over A is a structure, denoted T L , over the signature σ anc = σ A ∪ {≺}, where ≺ is of arity 2. The domain is the the set of prefixes of the language L. For all a ∈ A, P a is interpreted as the set of words of L ending with the letter a, and ≺ is interpreted as the prefix relation < p .

It is possible to define the tree of a language over a more restricted signature σ suc = σ A ∪ {Succ}, where Succ is interpreted as the direct successor relation.

(ε) (0) (1) (10) (11)
Fig. 2. The tree TL of the language L = 1 * 0 where full edges represent the Succ relation and dashed edges represent the relation ≺. The root is not labelled, all leaves are labelled by 0, and all other nodes by 1.

Lemma 4. For any language L over an ordered alphabet A, the linear ordering O L can be first-order interpreted in T L over the signature σ anc .

Main undecidability result

This section is devoted to establishing the following theorem.

Theorem 1. There exists a context-free word with an undecidable first-order theory. Furthermore, such a context-free word can be defined by a finite disjoint union of deterministic context-free languages.

We now proceed with the proof of Theorem 1. The key ingredient of the proof are the languages obtained by a special form of product, denoted ⊗, of deterministic context-free languages. Definition 2. Let L 1 , . . . , L n be languages over the alphabet A. We let L 1 ⊗ • • • ⊗ L n denote the language over the alphabet A × 2 n containing all nonempty words (a 1 , b1 )

• • • (a m , bm )
such that for all i ∈ [m], a i belongs to A and bi belongs to 2 n and furthermore for all ∈ [n], the -th component of the "flag" bi is equal to 1 if and only if the word a 1 • • • a i belongs to L .

Intuitively the th bit of the ith letter of the attached flag signals if the prefix of length i projected on A belongs to the language L . Example 2. Let A be the alphabet {a, b, c, d}. Consider the two deterministic context-free languages

L 1 = {w ∈ A * | |w| a = |w| b } and L 2 = {w ∈ A * | |w| c = |w| d }. The language L 1 ⊗ L 2 contains the word   a 0 1     c 0 0     b 1 0     d 1 1     a 0 1     d 0 0   Note that the language L 1 ⊗ L 2 is not a context-free language 3 .
The key observation is that the structure associated with the product L 1 ⊗ L 2 of two deterministic context-free languages L 1 and L 2 can be defined in first-order logic in some context-free word.

Proposition 1. Let L 1 and L 2 be two deterministic context-free languages. There exists a language L over an ordered alphabet which is the disjoint union of deterministic context-free languages not containing the empty word such that the structure S L1⊗L2 can be first-order interpreted in W L .

Proof. Let L 1 and L 2 be two deterministic context-free languages. Using a standard binary encoding, we can assume that L 1 and L 2 are on the binary alphabet A = {a, b} ordered by a < b.

Consider the alphabet

B = { , ā, b, 0 1 , 1 1 , 0 2 , 1 2 , , #, a, b} with < ā < b < 0 1 < 1 1 < 0 2 < 1 2 < < # < a < b
and the language L which is the (disjoint) union of the following languages:

{u# | u ∈ A * } {u#u R | u ∈ A * } {u#vxx | u ∈ A * , v ∈ A * , x ∈ A and vx ≤ p u R } {u#v0 i | u ∈ A * , v ∈ A + and v ∈ L i }, i = 1, 2 {u#v1 i | u ∈ A * , v ∈ A + and v ∈ L i }, i = 1, 2.
We now define a first-order interpretation transforming W L into S L1⊗L2 . The interpretation only keeps the vertices labelled by the predicate ā or b:

δ(x) = P ā(x) ∨ Pb(x).
The order relation < coincides with the order relation of W L but restricted to vertices lying between a vertex labelled by and a vertex labelled by with no vertex labelled by in between:

ϕ < (x, y) = ∃z 1 ∃z 2 (z 1 < x < y < z 2 ∧ P (z 1 ) ∧ P (z 2 ) ∧ ∀z (z 1 < z < z 2 → ¬P (z ))).
3 Indeed, by taking the intersection of L1 ⊗ L2 with the regular language (A ×

. The white nodes correspond to words that are kept by the interpretation.

For (a, b, c) ∈ A × 2 × 2, the predicate P (a,b,c) is defined by

ϕ P (a,b,c) (x) = P ā(x) ∧ ∃y∃z (Succ(x, y) ∧ Succ(y, z) ∧ P b1 (y) ∧ P c2 (z))
where b 1 is 0 1 if b = 0 and 1 1 otherwise, and similarly, c 2 is 0 2 if c = 0 and 1 2 otherwise.

To conclude the proof, it remains to show that there exists a product of two deterministic context-free languages whose structure has an undecidable first-order theory. Proposition 2. There exist two deterministic context-free languages L 1 and L 2 such that S L1⊗L2 has an undecidable first-order theory.

Proof. Let A be the alphabet containing the symbols + 1 , + 2 , -1 , -2 , = and $. Consider the following deterministic context-free languages:

L 1 = {w ∈ A * | |w| +1 = |w| -1 } L 2 = {w ∈ A * | |w| +2 = |w| -2 }.
In our argument, we will use reduction from the halting problem of 2-counter machines. A program for a 2-counter machine is a nonempty sequence I 1 ; . . . ; I n of instructions, where I n is a halt instruction and all other instructions I i are of the form Inc j , Dec j or Test j (k), j = 1, 2, k ∈ [n]. Here, Inc j increments the value of the jth counter by 1, Dec j decrements it by 1 -provided that the current value is not 0. If the current value is 0, then Dec j corresponds to a skip instruction. A conditional branch instruction Test j (k), where k ∈ [n], tests the current value of the jth counter and transfers the control to the kth instruction if this value is 0. Initially, the values of the counters are 0. The instructions are executed sequentially, except for the effect of the conditional branch instructions. The machine halts when I n is executed. Without loss of generality we will consider machines that do not try to decrease the value of a counter whose value is 0. This condition can be syntactically enforced by prefacing each decrease operation with a test.

Formally, a computation sequence for the program is a sequence i 1 , . . . , i m of instruction numbers in [n] such that one can define a valuation mapping v : [m] → N × N associating to every index ∈ [m], the value of the two counters before executing the th instruction. The computation sequence and the valuation must satisfy the following properties:

-i 1 = 1 and v(1) = (0, 0) -for all ∈ [m -1], if I i = Inc 1 (resp. I i = Inc 2 ), then i +1 = i + 1 and v( + 1) = v( ) + (1, 0) (resp. v( + 1) = v( ) + (0, 1)), -for all ∈ [m -1], if I i = Dec 1 (resp. I i = Dec 2 ), then i +1 = i + 1 and v( + 1) = v( ) + (-1, 0) (resp. v( + 1) = v( ) + (0, -1)), -for all ∈ [m-1], if I i = Test 1 (k) (resp. I i = Test 2 (k)), then v( +1) = v( ),
and i +1 = k if the first (resp. second) component of v( ) is equal to zero and i +1 = i + 1 otherwise.

Furthermore, a computation sequence is halting if i m = n. A word w over A is said to represent a computation sequence if it satisfies the following conditions:

1. it is of the form $ i1 x 1 • • • x m-1 $ im with x 1 , . . . , x m-1 ∈ {+ 1 , + 2 , -1 , -2 , =} and i ∈ [n] for ∈ [m]; 2. for all ∈ [m -1], x is + 1 if I i = Inc 1 , + 2 if I i = Inc 2 , -1 if I i = Dec 1 ,
-2 if I i = Dec 2 , and = otherwise; 3. i 1 , . . . , i m is a computation sequence.

Claim. The exists a first-order formula ϕ Halt such that for every word w ∈ L 1 ⊗L 2 , S w |= ϕ Halt if and only if w projected on A represents a halting computation sequence.

Proof. It is straightforward to write a first-order formula ensuring that w projected on A satisfies the conditions 1 and 2 above. To be able to express condition 3 in first-order, the only difficulty consists in testing if before the th instruction the value of a given counter is 0, where ∈ [n]. For this it is enough to notice that if the value of the two counters before the th instruction is given by (|w

| +1 -|w | -1 , |w | +2 -|w | -2 ), where w = $ i1 x 1 • • • x -1 $ i -
recall that we do not consider machines that can decrease the value of a counter when its value is zero -, then by the definition of L 1 ⊗ L 2 , the fact that the jth counter has value 0 can be tested by reading the jth bit of the attached flag.

To conclude the proof, we construct a formula φ P such that S L1⊗L2 |= φ P if and only if L 1 ⊗ L 2 contains at least one word satisfying ϕ Halt (and hence if and only if P is halting). The formula φ P is equal to ∃x ϕ Halt (x), where ϕ Halt (x) is the formula obtained from ϕ Halt by relativizing all quantifications to elements that are comparable to x with respect to < or =.

We can now prove Theorem 1.

Proof (Proof of Theorem 1). By Proposition 2, there exist two deterministic context-free languages L 1 and L 2 such that S L1⊗L2 has an undecidable first-order theory. By Proposition 1, there exists a language L over an ordered alphabet which is the disjoint union of deterministic context-free languages (not containing the empty word), such that S L1⊗L2 can be first-order interpreted in W L . Thus W L has an undecidable first-order theory.

Corollaries of Theorem 1

Using Lemma 3, Theorem 2 can be transferred to context-free linear orderings.

Corollary 1. There exists a context-free linear ordering with an undecidable first-order theory. Furthermore such a context-free linear ordering can be defined by a finite disjoint union of deterministic context-free languages.

Proof. By Theorem 1, there exists a finite union L of deterministic context-free languages such that W L has an undecidable first-order theory. By Lemma 3, there exists a context-free language L and a first-order interpretation I of W L in O L . Since the first-order theory of W L is undecidable, it follows that the first-order theory of O L is also undecidable.

Observe that as L is a finite disjoint union of deterministic context-free languages, the language L constructed in Lemma 3 can also be chosen to be a finite disjoint union of deterministic context-free languages.

As all deterministic context-free linear orderings have a decidable monadic second-order theory, this result provides an example of a context-free linear ordering that is not deterministic context-free.

Corollary 2. There exists a context-free linear ordering that is not a deterministic context-free linear ordering.

Moving our focus to trees, we obtain a simple proof of a result first proved in [START_REF] Parys | Higher-order stacks can not replace nondeterminism[END_REF].

Corollary 3. There exists a finite disjoint union of deterministic context-free languages such that 1. the associated tree has an undecidable first-order theory over the signature σ anc (which includes the ancestor relation), 2. it cannot be accepted by any deterministic collapsible automaton.

Proof. The first claim is a direct consequence of Corollary 1 and Lemma 4. The second claim then follows form the fact that any language accepted by a deterministic collapsible automaton has a tree with a decidable MSO-theory [START_REF] Ong | On model-checking trees generated by higher-order recursion schemes[END_REF], and hence a decidable first-order theory over the signature σ anc .

In a draft of this article, we asked if there exists a context-free language whose associated tree has an undecidable first-order theory over the signature σ suc . This question was positively answered by Markus Lohrey [23].

Proposition 3 (M. Lohrey). There exists a context-free language whose associated tree has an undecidable first-order theory over the signature σ suc .

Proof. The proof starts by establishing that there exists a context-free language L 0 over an alphabet A such that the following problem is undecidable : "Given a word w ∈ A + , decide if L 0 contains all words ending with w".

To construct L 0 , we consider a universal Turing machine M with a set Q of states and a set Γ of tape symbols. It is well-known that the set L M of words representing ill-formed or non-terminating computations of a Turing machine is a context-free language [START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF]. More precisely, a configuration is represented by a word in Γ * QΓ * and a computation c 0

• • • c n is represented by the word w = c 0 c R 1 c 2 • • •.
For the language L 0 , we take L R M = {w R | w ∈ L M }. For a word w representing an initial configuration c 0 of M , it is clear that L R M contains all words ending with w R if and only if M does not have a halting computation starting from c 0 . Hence the aforementioned problem is undecidable for L 0 .

Let $ be a fresh symbol. We show that the first-order theory over σ suc of T L0$ is undecidable.

Let w = a 1 • • • a n with n > 0 be a word over A. The formula ϕ w over σ suc , ϕ w = ∀x ∃x 1 • • • ∃x n+1 Succ(x, x 1 ) ∧ i∈[n] Succ(x i , x i+1 ) ∧ i∈[n] P ai (x i ) ∧ P $ (x n+1 ), expresses that for every word u, the word uw$ is in the domain of T L0$ and hence that uw belongs to L 0 . Hence for all w ∈ A + , T L0$ |= ϕ w if and only if L 0 contains all words ending in w. We conclude that the undecidability of the first-order theory of T L0$ follows from the undecidability of the above problem.

As observed by M. Lohrey, the above proposition can be stated for the more restrictive signature {Succ} in which labels are omitted. Indeed, this follows from the following lemma that shows that a context-free tree over σ suc can be first-order interpreted in a context-free trees over {Succ}.

Lemma 5. Let L be a context-free language. There exists a context-free language L such that T L over the signature σ suc can be first-order interpreted in T L over the signature {Succ}.

Proof. Let L be a context-free language over the alphabet A = {a 1 , . . . , a n }.

Without loss of generality we may assume that L contains a nonempty word. Consider the context-free language L = {ua j i | i ≤ j and ∃w ∈ L, ua j ≤ p w} over the alphabet A ∪ [n]. The first-order interpretation of T L over σ suc in T L over {Succ} only keeps non-leaf nodes. The Succ relation is inherited. For i ∈ [n], the predicate P ai holds at those non-leaf nodes which have exactly i sons which are leaves. Formally the interpretation is defined by δ(x) = ¬Leaf(x) ϕ Succ (x, y) = Succ(x, y) ϕ Pa i (x) = ∃ =i y Succ(x, y) ∧ Leaf(y)

where Leaf(x) is a formula expressing that x is a leaf.

It would be interesting to know if Property 3 remains true when only considering context-free languages which are finite unions of deterministic context-free languages.

Discussion

In this article, we have established that the linear orderings and trees associated with context-free languages are more complex than those associated to deterministic context-free languages. This result even holds for finite disjoint unions of deterministic context-free languages and hence for unambiguous context-free languages. It would be interesting to investigate whether such a separation result exists for context-free scattered linear orderings.

2 2 )Fig. 3 .

 23 Fig.3. Assuming that L1 = A * b and L2 = A * ba, we depict the part of the tree TL corresponding to the subset of the language producing after interpretation the word (b, 1, 0)(b, 1, 0)(a, 0, 1). The white nodes correspond to words that are kept by the interpretation.

Acknowledgements

The authors would like to thank Markus Lohrey for his remarks on a previous draft of this article as well as for the proof of Proposition 3. The authors are also grateful for the remarks of the anonymous referees.

Arnaud Carayol has been supported by the project AMIS (ANR 2010 JCJC 0203 01 AMIS). Both authors received partial support from the project T ÁMOP-4.2.1/B-09/1/KONV-2010-0005 "Creating the Center of Excellence at the University of Szeged", supported by the European Union and co-financed by the European Regional Fund. Zoltán Ésik was also partly supported by the National Foundation of Hungary for Scientific Research, grant no. K 75249, and by a chair Labex Bézout as part of the program "Investissements d'Avenir" (ANR-10-LABX-58).


Garvita Bajaj
email: garvitab@iiitd.ac.in

Rachit Agarwal
email: rachit.agarwal@inria.fr

Pushpendra Singh
email: psingh@iiitd.ac.in

Nikolaos Georgantas
email: nikolaos.georgantas@inria.fr

Valerie Issarny
email: valerie.issarny@inria.fr

A study of existing Ontologies in the IoT-domain

Keywords: IoT, Ontologies, interoperability, heterogeneity

Several domains have adopted the increasing use of IoT-based devices to collect sensor data for generating abstractions and perceptions of the real world. This sensor data is multi-modal and heterogeneous in nature. This heterogeneity induces interoperability issues while developing cross-domain applications, thereby restricting the possibility of reusing sensor data to develop new applications. As a solution to this, semantic approaches have been proposed in the literature to tackle problems related to interoperability of sensor data. Several ontologies have been proposed to handle different aspects of IoT-based sensor data collection, ranging from discovering the IoT sensors for data collection to applying reasoning on the collected sensor data for drawing inferences. In this paper, we survey these existing semantic ontologies to provide an overview of the recent developments in this field. We highlight the fundamental ontological concepts (e.g., sensor-capabilities and context-awareness) required for an IoT-based application, and survey the existing ontologies which include these concepts. Based on our study, we also identify the shortcomings of currently available ontologies, which serves as a stepping stone to state the need for a common unified ontology for the IoT domain.

Introduction

With the rapid adoption of the Internet of Things (IoT) technology in various domains including health, transportation, and manufacturing, the number of IoT devices in the world is expected to increase to 50 billion by the end of 2020 1 . These IoT devices collect an enormous amount of data using the sensors embedded in them. According to a Cisco report, the amount of annual global data traffic will reach 10.4 ZB (zettabytes) by 2019 2 . It is interesting to note here that this data will be multi-modal in nature comprising of various formats including video streams, images, and strings.

Handling such large-scale heterogeneous data and processing it in real-time will be a key factor towards building smart applications [START_REF] Aggarwal | The Internet of Things: A Survey from the Data-Centric Perspective[END_REF]. Semantic approaches -ontologies -have been used to solve these issues related to largescale heterogeneity. Ontologies are defined as a "well-founded mechanism for the representation and exchange of structured information" [START_REF] Ye | Ontology-based Models in Pervasive Computing Systems[END_REF]. Existing works have proposed the use of unified ontologies to tackle issues of interoperability and automation associated with heterogeneity of sensor data [START_REF] Atzori | The Internet of Things: A survey[END_REF][START_REF] Gyrard | Enrich Machine-to-Machine Data with Semantic Web Technologies for Cross-Domain Applications[END_REF][START_REF] Nambi | A Unified Semantic Knowledge Base for IoT[END_REF]. However, multiple possible unifications developed by domain experts [START_REF] Gyrard | Domain knowledge Interoperability to Build the Semantic Web of Things[END_REF] pose several challenges as every unified ontology proposes its self-defined taxonomy. Figure 1 illustrates an example scenario where the use of several possible unifications of ontologies causes issues. Let us consider two IoT platforms deployed at different geographic locations for building two different applications for smart-health and smart-building domains respectively. Accessing data from both the platforms at another location (e.g., a remote server using data from both the platforms for developing another application) will lead to the challenges described below.

Firstly, the integration of multi-modal sensor data from different sources (i.e., sensors belonging to the two platforms in this scenario) results in complexity and variability in information exchange as multiple sources (i.e., IoT sensors) corresponding to the same sensor data follow the nomenclature [START_REF] Ye | Ontology-based Models in Pervasive Computing Systems[END_REF] defined by different ontologies. For example, Cloud 1 may store a sensor's location using a tag loc (defined by ontology A); while Cloud 2 may use the tag location for referencing sensor location (defined by ontology B). This difference in nomenclatures may lead to usability issues in developing cross-domain applications as developers would require prior knowledge of every data source and its associated ontology before selecting one for use. Secondly, the heterogeneous data representation also poses challenges in the development of cross-domain applications that rely on the same set of sensors [START_REF] Gyrard | Enrich Machine-to-Machine Data with Semantic Web Technologies for Cross-Domain Applications[END_REF] available with different IoT platforms. For example, the temperature sensor used in the smart-health application and the smart-building application would yield two temperature values -body temperature and room temperature respectively -that cannot be used interchangeably even if the same nomenclature (e.g., temperature or Temp) is used to describe the sensor data.

Thirdly, heterogeneity also causes problems in the design, interaction, and integration of automated solutions based on sensor data [START_REF] Dibowski | Ontology-based Device Descriptions and Device Repository for Building Automation Devices[END_REF]. For example, with the growing complexity of building automation systems and available devices, there is a need to develop automated design approaches for building systems. Developing such automated approaches would require a comprehensive specification of the hardware and software components to avoid heterogeneity issues, which can be solved using a common unified ontology.

Defining one comprehensive unified ontology for the domain of IoT may be challenging as there are more than 200 domain ontologies available [START_REF] Gyrard | LOV4IoT: A second life for ontology-based domain knowledge to build Semantic Web of Things applications[END_REF]. For most of the ontologies, there are certain concepts peculiar to the IoT applica-tion domains while some concepts used are common to all the IoT platforms. Consider, for example, the two platforms shown in Figure 1. Platform 1 will require concepts from health domain while Platform 2 may need concepts from energy and location domains to cater to application needs. On the other hand, both these platforms will require some concepts to answer the basic queries posed by a developer including the location of a sensor and capabilities of a sensor among others. Concepts belonging to the former group (applicationspecific) comprise the vertical silos of an IoT ontology, while those belonging to the latter group comprise the horizontal silos as shown in Figure 2. In this work, we limit our discussion to the unification of concepts pertaining to the horizontal silos in the IoT domain.

In 2012, the W3C Semantic Sensor Networks Incubator Group (SSN-XG) 3was formed to address the issues of heterogeneity in sensor networks. Although a standard, SSN4 still fails to address several aspects of the IoT data such as real-time data collection issues, providing a taxonomy for measurement units, context, quantity kinds (the phenomena sensed), and exposing sensors to services, which compels developers to define new concepts in IoT domain while developing novel applications. Several ontologies have been proposed to overcome the shortcomings of SSN, and most of them are limited to certain concepts owing to the vastness of the domain.

In this work, we identify these standard concepts by identifying the competency questions -"what are the queries that experts will submit to a knowledge base to find answers? " [START_REF] Yan | An Ontology For Specifying Spatiotemporal Scopes in Life Cycle Assessment[END_REF]. We identify these questions using the 4W1H methodology [START_REF] Niitsuma | Describing Human-Object Interaction in Intelligent Space[END_REF][START_REF] Zhang | 4W1H in Mobile Crowd Sensing[END_REF]. The answers to the competency questions will help us identify the core concepts for a unified IoT ontology. In this paper, we survey the existing IoT and IoT-related ontologies proposed since 2012 5to identify the concepts that could be used towards building the unified IoT ontology. We aim to identify these concepts to solve the heterogeneity issue arising because of several domain ontologies available in the literature. From the concepts identified, we also aim to structure the existing literature which can serve as a tool for ontology developers. To summarise, we identify the main concepts in an IoT-based application using the 4W1H methodology and classify the existing ontologies on the basis of these concepts. Our study aims to highlight the research gaps in existing ontologies which will help identify concepts required for a unified standard ontology in this domain.

Roadmap

We begin with identifying the core concepts by defining the competency questions using the 4W1H methodology in Section 2. We identify a structure within the proposed ontologies with a survey in Section 3. In Section 4, we discuss the different approaches used to evaluate the ontologies in order to identify a common ground for comparing existing ontologies with each other. We end this paper with a discussion in Section 5 on the need of a common unified ontology for achieving semantic interoperability among IoT applications.

Identifying Core Concepts

An application based on IoT technology (e.g., a standalone mobile application or a cloud-based application using static sensors) consists of several components. These components are used to interact with several different sensors that are attached to a platform. These sensors may be statically positioned or dynamically moving for collecting data across a geographical area of interest. An ideal IoT ontology should describe the core concepts common to all IoT applications (i.e., horizontal), and concepts that are specific to applications (i.e., vertical) as shown in Figure 2. However, to limit the concepts in a unified ontology for IoT domain, we focus on including all the horizontal core concepts in this study. To identify these fundamental concepts required in an ontology, we must identify the competency questions -queries submitted by experts to a knowledge base to find answers [START_REF] Yan | An Ontology For Specifying Spatiotemporal Scopes in Life Cycle Assessment[END_REF]. Previous works by Haller et al. [START_REF] Haller | A Domain Model for the Internet of Things[END_REF], Wang et al. [START_REF] Wang | Knowledge Representation in the Internet of Things: Semantic Modeling and its Applications[END_REF], and Bermudez-Edo et al. [START_REF] Bermudez-Edo | IoT-Lite: A Lightweight Semantic Model for the Internet of Things[END_REF][START_REF] Bermudez-Edo | IoT-Lite: A Lightweight Semantic Model for the Internet of Things and its use with Dynamic Semantics[END_REF] have identified some of these questions to list the following different core concepts for the IoT domain: Augmented Entity, User, Device, Resource, and Service among others. These studies ( [START_REF] Haller | A Domain Model for the Internet of Things[END_REF][START_REF] Wang | Knowledge Representation in the Internet of Things: Semantic Modeling and its Applications[END_REF][START_REF] Bermudez-Edo | IoT-Lite: A Lightweight Semantic Model for the Internet of Things[END_REF][START_REF] Bermudez-Edo | IoT-Lite: A Lightweight Semantic Model for the Internet of Things and its use with Dynamic Semantics[END_REF]), however, do not consider all the core concepts which can be used by several applications to infer complex information in IoT scenarios.

4W1H [START_REF] Niitsuma | Describing Human-Object Interaction in Intelligent Space[END_REF][START_REF] Zhang | 4W1H in Mobile Crowd Sensing[END_REF] is a popular approach that is being used to describe the basics of an event/situation. To define the comprehensive list of concepts for an IoT ontology, we rely on the use of 4W1H methodology. For this, we must define five variables -four Ws (What, Where, When, Who) and one H (How) to list the competency questions required for identification of the core IoT concepts. These variables and the corresponding competency questions are listed below followed by a detailed explanation of the identified concepts:

• Who: Who will provide the information required to develop the IoT application? The answer to this question requires concepts to identify the sources which provide data for building an IoT-based application. This source is the sensor which is embedded in a platform that can be a part of a testbed. Thus, to answer the 'who' question, an IoT ontology must include concepts for sensor, platform, and testbed. • What: What are the conditions under which the source must collect data? Should the data be collected under certain circumstances only? Answering this question requires the IoT ontology to include concepts to define the context of the data source (e.g., the mobility of the sensor, the activity being performed, whether the measurement was taken by the device automatically or was there some human intervention). • Where: Where should the data come from? This refers to the location of the data source which can be defined using geo-coordinates, building names, landmarks, etc. The IoT ontology must incorporate the different ways to locate the data source for allowing developers to identify the data source. • When: When should the data collection happen? Should the sensor collect data at specified timestamps, should it be at a regular frequency, or over a span of time? An IoT ontology should provide concepts to support different formats for defining the time for data collection. • How: Once the data has been collected by the relevant sensors, how should it be exposed to the developer for building the IoT application? There should be concepts to support services for providing developers with the access to this sensor data.

These competency questions help us identify the requirements of the core concepts in a unified IoT ontology. We list and explain these concepts in detail below (the concepts are highlighted in bold):

(1) An IoT application is based on sensor data collected from various heterogeneous sensors. A sensor is defined as a "source that produces a value representing a quality of a phenomenon" [START_REF] Compton | A survey of the Semantic Specification of Sensors[END_REF]. Note that here sensor data refers to both raw data captured by the sensor and the metadata that describes a sensor.

(2) These sensors need a power supply to operate. They may be batterypowered or may be attached to another power source for energy. This "identifiable entity to which a sensor is attached " is called a platform [START_REF] Compton | A survey of the Semantic Specification of Sensors[END_REF]. (3) For a wide-scale deployment of IoT solutions provided by these platforms, a large-scale realistic testbed is required [START_REF] Gluhak | A Survey on Facilities for Experimental Internet of Things Research[END_REF]. This testbed should provide functionalities to support the different kinds of sensors required (based on the phenomenon they sense), and should provide mechanisms to communicate the sensor data to the applications. The testbeds may also internally store the captured sensor data in their proprietary format for performing local data analysis. (4) Given a testbed infrastructure (e.g., SmartSantander6 , IoT-Lab7 , Ambiciti 8 ), an identifiable service to access this raw or processed data is required. The service should support a combination of sensor data to get better contextual information (assimilation), and removal of redundant sensor data (filtering) from multiple data sources. The service should allow the users to discover information from the environment based on certain search criteria. (5) Further, since most of the sensor data is location and time specific, the location and time information may be used to provide a common context ("information about a location, its environmental phenomena, and the people, devices, objects, and software agents it contains" [START_REF] Chen | An ontology for Context-Aware Pervasive Computing Environments[END_REF]) for modeling the services in IoT frameworks [START_REF] Flury | OWL-based location ontology for context-aware services[END_REF]).

Several domains have proposed ontologies defined by domain experts for these concepts. In this work, we study some ontologies centered around these concepts.

Survey

In this section, we present a survey of ontologies in the IoT-domain based on the concepts identified above. These ontologies are prevalent in several application areas including Building Management Systems (BMS) [START_REF] Balaji | Brick: Towards a Unified Metadata Schema for Buildings[END_REF], indoor navigation [START_REF] Szász | iLOC-Building Indoor Navigation Services using Linked Data[END_REF], and smart-homes [START_REF] Bae | An Ontology-based approach to {ADL} Recognition in Smart Homes[END_REF]. Ye et al. [START_REF] Ye | Ontology-based Models in Pervasive Computing Systems[END_REF] have proposed a classification of ontologies based on (i) expressiveness as light-weight or heavy-weight; or (ii) generality as generic, domain-specific, or application-specific. In this paper, we use the latter classification based on the functionalities provided by the ontology. Since our focus is on the entire IoT domain and not on a specific application, we restrict our discussion to generic and domain specific ontologies only.

Sensor Ontologies

Sensor Discovery [START_REF] Bermudez-Edo | IoT-Lite: A Lightweight Semantic Model for the Internet of Things[END_REF][START_REF] Balaji | Brick: Towards a Unified Metadata Schema for Buildings[END_REF][START_REF] Hirmer | Dynamic Ontology-Based Sensor Binding[END_REF][START_REF] Daniele | Study on Semantic Assets for Smart Appliances Interoperability[END_REF] Sensor Data Description [START_REF] Gyrard | Enrich Machine-to-Machine Data with Semantic Web Technologies for Cross-Domain Applications[END_REF][START_REF] Compton | The SSN Ontology of the W3C Semantic Sensor Network Incubator Group, Web Semantics: Science, Services and Agents on the World Wide Web[END_REF][START_REF] Nachabe | Unified Data Model for Wireless Sensor Network[END_REF] Sensor Capabilities [START_REF] Bermudez-Edo | IoT-Lite: A Lightweight Semantic Model for the Internet of Things[END_REF][START_REF] Bermudez-Edo | IoT-Lite: A Lightweight Semantic Model for the Internet of Things and its use with Dynamic Semantics[END_REF][START_REF] Russomanno | Sensor Ontologies: from Shallow to Deep models[END_REF][START_REF] Xue | An Ontology based Scheme for Sensor Description in Context Awareness System[END_REF] Extensibility [START_REF] Balaji | Brick: Towards a Unified Metadata Schema for Buildings[END_REF][START_REF] Daniele | Study on Semantic Assets for Smart Appliances Interoperability[END_REF] Data Access & Sharing [START_REF] Xue | An Ontology based Scheme for Sensor Description in Context Awareness System[END_REF][START_REF] Shi | Sensor Ontology Building in Semantic Sensor Web[END_REF] Figure 3. The different problem areas tackled by existing sensor ontologies

Sensor ontologies

Existing sensor ontologies proposed in the literature aim to solve heterogeneity problems associated with the hardware, software, and the data management aspect of sensors. These aspects are highlighted in Figure 3 where we classify the different sensor-based ontologies based on the problems they tackle.

Please note that 'sensor data' may refer to the raw sensor data generated by sensing the phenomenon, or the metadata information used to describe the sensor capabilities. Here, we use the term 'sensor data' to refer to the raw data generated by sensors, and 'sensor capabilities' to describe the metadata information (e.g., the accuracy of a sensor and coverage range of a sensor.) associated with these sensors. In the following text, we briefly introduce the different proposed ontologies based on the generic concepts defined by them.

Generic Ontologies

In 2012, W3C (World Wide Web Consortium) proposed a standard ontology -SSN (Semantic Sensor Network) ontology [START_REF] Compton | The SSN Ontology of the W3C Semantic Sensor Network Incubator Group, Web Semantics: Science, Services and Agents on the World Wide Web[END_REF] for describing the sensor resources and the data collected through these sensors as observations. SSN ontology aims to solve the heterogeneity problems associated with sensor discovery and sensor data collection but has limited concepts to support the spatial and temporal association of sensor data with the resources. Also, it is difficult to describe the different sensor capabilities using SSN as there is only one concept for sensor description. To overcome this problem, Xue et al. [START_REF] Xue | An Ontology based Scheme for Sensor Description in Context Awareness System[END_REF] proposed an ontology with concepts for sensor typesnormal or advanced, and also sensor capabilitiesstatic, or dynamic. They also introduce concepts to deal with issues of sensor management and data sharing in sensor networks. However, their ontology supports a small number of sensors in terms of the phenomenon they can sense, and provides semantic support for only a limited number of sensor features. Further, in the ontology, the concept of location is only limited to building rooms and building floors. This limits the usage of this ontology to indoor applications only. Gyrard et al. [START_REF] Gyrard | Enrich Machine-to-Machine Data with Semantic Web Technologies for Cross-Domain Applications[END_REF][START_REF] Gyrard | Standardizing generic cross-domain applications in internet of things[END_REF] overcome this limitation by providing M3 ontology -a comprehensive ontology proposed as an extension to W3C's SSN ontology to support the description of sensors, observations, phenomena, their units, and domains, which also allows for reasoning on sensor data using rules to infer contextual information.

Since the platform to which the sensors are attached can be mobile, issues with dynamicity and sensor discovery must also be dealt with. Concepts for dealing with these issues were introduced in OntoSensor [START_REF] Russomanno | Sensor Ontologies: from Shallow to Deep models[END_REF]. The ontology extends concepts from SensorML9 , ISO-1911510 , and SUMO [START_REF] Niles | Towards a standard upper ontology[END_REF], to allow concepts for the identification of sensor categories, behavior, relationships, functionalities, and meta-data regarding sensor characteristics, performance, and reliability. OntoSensor aims to support interoperability and ontology-based inferences that require aspects of physical sensing to be incorporated in the ontology definition. The ontology is heavy-weight, has high usage complexity, and lacks the ability to describe sensor observations. This limitation was solved by MyOntoSens [START_REF] Nachabe | Unified Data Model for Wireless Sensor Network[END_REF] which provides a generic and exhaustive ontology for describing sensor observations and capabilities to reason over the collected data. MyOntoSens has been proposed for the domain of wireless sensor networks (WSN) and borrows several concepts and relationships from existing ontologies including OntoSensor [START_REF] Russomanno | Sensor Ontologies: from Shallow to Deep models[END_REF], SSN [START_REF] Compton | The SSN Ontology of the W3C Semantic Sensor Network Incubator Group, Web Semantics: Science, Services and Agents on the World Wide Web[END_REF], and QUDT [START_REF] Hodgson | QUDT-Quantities, Units, Dimensions and Data types Ontologies[END_REF] which makes it applicable to the IoT domain also. MyOntoSens provides concepts to support sensor discovery and sensor registration with the platform.

Hirmer et al. [START_REF] Hirmer | Dynamic Ontology-Based Sensor Binding[END_REF] propose an ontology to support dynamic registration and bindings of new sensors to a platform. They borrow the concepts of Sensors, Things and their associated properties from SensorML, and introduce an additional concept of 'Adapter' associated with every sensor. The borrowed concepts support sensor discovery while the newly introduced concepts provide/compute additional information about sensor data. For example, adapters are used to compute the average quality of sensor data values from the quality of the sensor provided by the manufacturer and the staleness of the values generated by the sensor. This additional information is then used to build a repository of the different possible sensor bindings -bindings of different Sensors with different Adapters -which is then used to automate the registration and binding tasks.

Shi et al. [START_REF] Shi | Sensor Ontology Building in Semantic Sensor Web[END_REF] identified the problems associated with inconsistencies in concept definitions among existing ontologies and proposed a framework to overcome them. Their ontology, Sensor Core Ontology (SCO), borrows concepts from existing sensor ontologies with provision to add new concepts, thereby supporting extensibility. The ontology focused mainly on concepts related to sensor data where each sensor observation is associated with time, space (location), and a theme (phenomenon being sensed). However, the description of these concepts themselves is not detailed enough even though the focus is on aspects of sensor data collection.

Domain-specific ontologies

In this section, we present the domain specific ontologies and limit our discussion to domains including smart appliances, energy, and building management systems which also form an integral part of the IoT ecosystem. Note that this is not the comprehensive list of all the domains. There are 17 different domains that have been identified 11 , but we focus only on the above-mentioned domains. SAREF [START_REF] Daniele | Study on Semantic Assets for Smart Appliances Interoperability[END_REF] (Smart Appliance REFerence) ontology exists in the domain of smart appliances and aims to reuse and align concepts and relationships in existing appliance-based ontologies. The concept of functions -one or more commands supported by devices (sensors) defined in SAREF -supports modularity and extensibility of the ontology, and also helps in maintenance of the appliances. An extension of SAREF -SAREF4EE [START_REF] Daniele | Interoperability for Smart Appliances in the IoT World[END_REF] has been proposed to support interoperability with EEBus12 and Energy@Home13 standards.

Along similar lines, Dey et al. [START_REF] Dey | Sensor Knowledge Representation with Spatiotemporal Annotation: An Energy Sensor Ontology use case[END_REF] propose an extension of OntoSensor ontology in the energy domain to include the spatial and temporal concepts of sensor data. Another ontology which focuses on energy efficiency at building level -Brick [START_REF] Balaji | Brick: Towards a Unified Metadata Schema for Buildings[END_REF], has been proposed in the domain of Building Management Systems (BMS). Brick proposes the use of tags and tagsets to specify sensors and building subsystems, thus, enabling sensor discovery. The use of tags, tagsets, and functional block s provides support for extensibility and flexibility for developing cross-building BMS applications. They do not cover the entire range of sensors available in the market and limit their focus to sensors used in smart-building applications. Since the concept of location used by them is limited to 'zones' (HVAC zones, rooms, and floors) inside the buildings, it can't be extended to other application areas.

Context-Aware ontologies

As defined by Chen et al. [START_REF] Chen | An ontology for Context-Aware Pervasive Computing Environments[END_REF], contexts are "used to describe places, agents, and events". Contexts can be classified as external or internal; and physical or logical [START_REF] Baldauf | A Survey on Context-Aware Systems[END_REF]. Several ontologies have been proposed for context-aware systems to effectively label contextual information collected from sensor devices in the form of sensor data. The following section reviews some of the generic and domain specific context ontologies. We emphasize more on domain specific ontologies as the context inferred in context-aware applications (including IoTbased applications) is highly dependent on the domain in consideration. As an example, for labeling a user activity, we need a complete understanding of the possible activities in the domain as activities performed on a university campus will be very different than the activities performed in a smart-home environment. Thus, better concepts for semantic labeling of contexts can be identified with domain-specific ontologies.

Generic Ontologies

In IoT applications, contexts are often important to correctly interpret sensor data [START_REF] Perera | Context Aware Computing for the Internet of Things: A survey[END_REF]. Thus, as the first step towards semantic labeling of contexts in IoT applications, Baldauf et al. [START_REF] Baldauf | A Survey on Context-Aware Systems[END_REF] propose the common architecture principles of context-aware systems based on the classification of contexts: external (physical) or internal (logical). External or physical contexts are those that can be measured using physical sensors, while internal or logical contexts are those that are explicitly specified by users or captured by monitoring user interactions (e.g., a user's goal or emotional state). The authors also derive a layered conceptual design framework to explain the elements common to most context-aware architectures. To further describe the concepts for contexts (places, agents, and events), Chen et al. [START_REF] Chen | An ontology for Context-Aware Pervasive Computing Environments[END_REF] propose COBRA-ONT for smart spaces. They describe places using <lat, lon, string-name> with two kinds of places with different constraints. There are also agents such as human and software, which are located in places and play certain roles to perform some activities. An important contribution is the broker architecture proposed by the authors, which can be used to acquire and reason over contextual information from mobile devices in order to reduce the burden of developers.

Since in IoT applications, the concept of a location may vary from a point to a place of interest, COBRA-ONT is one of the most promising ontologies to represent the location context of "things". It not only can describe a point but also be used to specify a place using a 'string' value for a location. To further correlate contextual information with location, Kim et al. [START_REF] Kim | Ontology based Location Reasoning Method using Smart Phone data[END_REF] propose an ontology based on the information provided by mobile device sensors, both -physical (e.g. WiFi, Bluetooth, etc.) and virtual (e.g., user schedule, web-logs, etc.) to support context-aware services. The proposed ontology defines the relations between different user locations and the contexts identified. The authors further propose a reasoner upon this ontology and evaluate it to identify locations. The result shows that their reasoner has higher location accuracy than the GPS locations.

Domain-specific ontologies

Several domain-specific ontologies have been proposed for defining contextual information as the contexts inferred from sensor data may vary largely based on the domain. For example, in a university domain, the activities may be limited to only a small subset such as reading, playing, sleeping, etc., while in a smart-home, a large set of activities (e.g., cooking, cleaning, reading, sleeping, etc.) may be encompassed. In this section, we will limit our study to contextaware ontologies in the domain of smart-homes and activity recognition.

Smart-home technologies are now being developed to assist disabled and elderly individuals with dignified living. Okeyo et al. [START_REF] Okeyo | Dynamic Sensor Data Segmentation for Real-time Knowledge-driven Activity Recognition[END_REF] propose an ontology to semantically label the Activities of Daily Living (ADL) such as cooking food, brushing teeth, etc. for the smart-homes domain. Their ontology is based on dynamic segmentation of sensor data for variable time windows to identify simple user activities. These simple activities are then used to infer more complex activities. A limitation of their ontology is that it focuses only on individual activities, and does not consider social activities (e.g., tea party, business meetings, etc.) that might occur in a smart-home environment.

To accommodate these concepts, Bae et al. [START_REF] Bae | An Ontology-based approach to {ADL} Recognition in Smart Homes[END_REF] present RADL (Recognizing Activities of Daily Living) system to classify three different kinds of services in smart-home environments. The ontology supports the discovery of devices and their location in smart-home domains using concepts like Person, Sensor, Device, Location, and AmIApplication. Reasoning on this ontology helps the system discover the user activities such as individual and social.

Further, extending our study to activity recognition in the domain of a university, Lee et al. [START_REF] Lee | Location-based Service using Ontology-based Semantic Queries: A study with a focus on Indoor Activities in a University Context[END_REF] propose UAO (University Activity Ontology) which caters to activities specific to a university campus (e.g.: attending a lecture or having lunch in the cafeteria). The authors use concepts defined in CONON (CONtext ONtology) [START_REF] Wang | Ontology based Context modeling and reasoning using OWL[END_REF] and introduce new concepts that are specific to activities on a university campus. They propose a hierarchical division of concepts using sub-ontologies to differentiate existing concepts from the new concepts. The concepts borrowed from existing ontologies are placed in the upper hierarchical structure, while the newly introduced concepts occupy positions in the lower hierarchical structure.

Location-based ontologies

Location is used to describe the spatial context (partly, physical context) of users/devices. Although a subset of context, we consider location ontologies separately as they have been used in several different areas like defining cultural heritage [START_REF] Cacciotti | Monument Damage Information System (MONDIS): An ontological approach to Cultural Heritage Documentation[END_REF], urban planning [START_REF] Liao | Place Name Ambiguities in Urban Planning Domain Ontology[END_REF], etc., beyond IoT technologies. However, we limit our discussion to location ontologies defined in the domain of IoT only.

Generic Ontologies

WGS84 ontology [START_REF] Brickley | Basic geo (WGS84 lat/long) vocabulary[END_REF] describes abstract concepts for defining SpatialThings such as buildings, people, etc., and TemporalThings such as events, or time durations. It also describes the geographical locations of these 'things' by using concepts for defining the geo-coordinates using latitude, longitude, and altitude. Concepts defined in this ontology are inherited from abstract concepts for defining subclasses specific to the system. A more descriptive location ontology is provided by Flury et al. [START_REF] Flury | OWL-based location ontology for context-aware services[END_REF] for context-aware services as they identify the location to be a common denominator for modeling services in context-aware environments. They provide a generic ontology for the location concept for "device-based services encountered in ubiquitous computing environments". They provide abstract mathematical models to categorize the different location solutions (like Cartesian coordinates and numerical estimation techniques) used to define location information. The different models considered are as follows: (i) Geometric models (comprising of Cartesian coordinates); (ii) Set-theoretic models (for defining location as an element of a set, e.g., Cellular location, WiFi AP location, etc.); (iii) Graph-based models (for defining locations in physically grounded networks, social networks, etc.), and (iv) Semantic models (for defining locations defined using human-friendly notations). However, in most IoT-based applications, location data is often collected using sensor data. Kim et al. [START_REF] Kim | Ontology based Location Reasoning method using Smart Phone Data[END_REF] rely on the use of sensor data collected from mobile devices of users to estimate device location. They propose a reasoner built upon sensor data and information from location sensors to estimate the location of users.

Domain-specific Ontologies

In this section, we restrict our discussion to location ontologies for indoor navigation.

iLoc [START_REF] Szász | iLOC-Building Indoor Navigation Services using Linked Data[END_REF] is an ontology specified in the domain of indoor building navigation and follows some of the best practices for defining a new ontology. It uses concepts borrowed from several existing ontologies -QUDT14 , W3C Geo vocabulary, and vCard15 and also supports extensibility. Since the root concept Location is borrowed from W3C Geo vocabulary, iLoc can also be extended to provide navigation for outdoor locations. The authors, however, do not provide an extensive evaluation of the ontology, and only demonstrate the usability through a use-case scenario.

Time-based ontologies

Time is used to describe the temporal context. Most of the IoT-related ontologies reuse existing ontologies that define the temporal context.

Generic Ontologies

Many ontologies that define temporal context have been proposed in the literature, for example, DAML-Time16 (DARPA Agent Markup Language project Time initiative), DAML-S17 (DAML for Web Services), KSL-Time18 (Stanford Knowledge Systems Lab Time ontology [START_REF] Fikes | A Reusable Time Ontology[END_REF]) and OWL-Time ontology 19 to name a few. DAML-Time focused on concepts to provide a common understanding of time. DAML-S however, provides temporal concepts required to define a web service such as profile, process and time. We refrain ourselves from describing them in detail. KSL-Time ontology, on the other hand, provides concepts to distinguish between different types of intervals and granularity.

The most commonly used ontology is the OWL-Time ontology proposed by Hobbs and Pan [START_REF] Hobbs | An ontology of time for the semantic web[END_REF] that focuses on describing date-time information specified in Gregorian calendar format. Several updates to the initial version of OWL-Time ontology have been proposed and implemented. The latest version of OWL-Time ontology 20 provides more concepts while deprecating some.

In general, the OWL-Time ontology provides concepts to describe time using five main core concepts, namely, TemporalEntity, Instant, Interval, ProperInterval, and DateTimeInterval. M. Grüninger in [START_REF] Grüninger | Verification of the OWL-Time Ontology[END_REF] verified the older version of the OWL-Time ontology in an independent study. A lightweight version of the OWL-Time ontology called Time-Entity is developed for applications needing only limited concepts [START_REF] Pan | Documentation for an Entry Sub-Ontology of Time in OWL[END_REF].

Timeline ontology21 is yet another time-based ontology. It extends Time Ontology by providing various concepts such as ContinuousTimeLine, DiscreteTimeLine, OriginMap, etc. Fikes et al. in [START_REF] Fikes | A Reusable Time Ontology[END_REF] considered granularity of time to provide more flexibility to the annotations. They considered both open and closed intervals to include flexibility on top of temporal aspects such as Time-Point.

Domain-specific Ontologies

TimeML, a time Domain-Specific Language (DSL), has been proposed by Pustejovsky et al. [START_REF] Pustejovsky | TimeML: Robust Specification of Event and Temporal Expressions in Text[END_REF] to provide the ability to query specific data based on duration, events, granularity and instant. An instance of TimeML is defined in XML format. However, Pustejovsky et al. used TimeML to annotate events within a Natural Language Processing system. Dey et al. [START_REF] Dey | Sensor Knowledge Representation with Spatio-Temporal Annotation: An Energy sensor ontology use case[END_REF] extended the use of TimeML to IoT systems and as a use-case, demonstrated the usage of TimeML to enrich annotations for the Energy sensors. Zhang et al. in [START_REF] Zhang | A Chinese Time Ontology for the Semantic Web[END_REF] created a time ontology that is capable of representing temporal aspects: (1) characterized by events either cultural or historical; and (2) in Chinese calendar instead of Gregorian calendar.

Ontology Evaluation

The goal of an ontology is to provide a semantic framework which can solve the problem of heterogeneity and interoperability associated with domain applications. This requires available ontologies to be comprehensive, readable, extensible, scalable, and reusable. Several methods have been proposed to evaluate an ontology on these different aspects. As a first step, validation tools like OntoCheck [START_REF] Schober | OntoCheck: Verifying Ontology Naming Conventions and Metadata Completeness in Protégé 4[END_REF] and SAOPY22 have been developed. These validation tools help ontology creators to identify inconsistencies in naming conventions and metadata completeness for (e.g., cardinality checks, class hierarchy, etc.). Another tool called OOPS 23 was developed to identify pitfalls in the ontology [START_REF] Poveda-Villalón | OOPS! (OntOlogy Pitfall Scanner!): An On-line Tool for Ontology Evaluation[END_REF] based on 41 evaluation criteria24 such as missing annotations, missing domain or range, and identifying anomalies in the relationships. Vapour25 is yet another validation tool that focuses on identifying if the ontology is correctly published or not based on the best practices recipes 26 . RDF Triple Checker27 is another tool that validates triples by finding typos and matching namespaces for the used concepts. Bae et al. [START_REF] Bae | An Ontology-based approach to {ADL} Recognition in Smart Homes[END_REF] have also proposed a schema-based approach for evaluating the design of ontologies on their richness, depth, width, and inheritance. Note that there are other validation tools also available 28 , but we restrict ourselves from comparing them with each other.

Once these basic checks have been performed, ontologies must be evaluated on parameters like scalability and extensibility. Bermudez et al. [START_REF] Bermudez-Edo | IoT-Lite: A Lightweight Semantic Model for the Internet of Things[END_REF][START_REF] Bermudez-Edo | IoT-Lite: A Lightweight Semantic Model for the Internet of Things and its use with Dynamic Semantics[END_REF] evaluate IoT-lite on scalability and complexity using Round Trip Time (RTT) as a measure. They annotate sensor data using their ontology and execute SPARQL queries on annotated datasets containing a different number of triples. For evaluating ontologies on extensibility, Shi et al. [START_REF] Shi | Sensor Ontology Building in Semantic Sensor Web[END_REF] propose a metric for objectively assessing the nomenclature of concepts used in the ontology based on translatability, clarity, comprehensiveness, and popularity.

A survey by Brank et al. [START_REF] Brank | A Survey of Ontology Evaluation Techniques[END_REF] highlights the following four major approaches to evaluate an ontology: (1) by comparing it with another ontology in the same domain;

(2) by comparing the concepts identified with a set of documents containing information about the domain in consideration; (3) by proposing an application using the ontology to justify its usage; and (4) by asking domain experts to evaluate it manually. Summarizing our study, we observe that no single metric or approach can be used to evaluate an ontology. This has also been identified by the authors in [START_REF] Vrandečić | Ontology Evaluation[END_REF] where they identify eight different parameters to assess the quality of an ontology. These are accuracy, adaptability, clarity, completeness, computational efficiency, conciseness, consistency, and organizational fitness. They also develop a framework called Semantic MetaWiki (SMW) to evaluate ontologies on these parameters. They identified that no single parameter could be used to compare ontologies; the goodness of an ontology depends on the application in consideration, and it cannot be judged by a single metric.

Most of the works referenced in this survey have demonstrated the feasibility of their ontologies using sample applications which are only a measure of the usability of the ontology. For evaluating ontologies on other parameters, there are independent measures but no single comprehensive metric for concrete assessment.

Discussion

Often systems propose proprietary ontologies for achieving semantic consistency in different modules. However, ontologies proposed by one system can often be used by other systems to improve interoperability. For example, authors in [START_REF] Desai | Semantic Gateway as a Service Architecture for IoT Interoperability[END_REF] Another ontology called Open-MultiNet (ONM) [START_REF] Willner | The Open-Multinet Upper Ontology Towards the Semanticbased Management of Federated Infrastructures[END_REF] is built to define federations of infrastructures. Similar to oneM2M, ONM does not reuse concepts. Further, ONM also lacks the notion of context.

An early attempt by Hachem et al. [START_REF] Hachem | Ontologies for the Internet of Things[END_REF] to solve the challenges of heterogeneity and scalability in IoT, proposed three ontologies for a service-oriented middleware for IoT applications. They are -(i) Device ontology (for describing the physical things and their metadata), (ii) Domain ontology (for defining relations between physical objects and mathematical formulas/functions), and (iii) Estimation ontology (for describing automated estimation processes to relate one mathematical function with another, and to model the errors in estimations). These ontologies lack the concepts required to annotate the collected data for addressing the issues of heterogeneity and interoperability. A detailed model to define concepts for devices, services, context, and information is also provided by IoT-A ontology [START_REF] Bauer | Enabling Things to Talk: Designing IoT solutions with the IoT architectural reference model[END_REF] for the IoT Architecture Reference Model [START_REF] Bassi | IoT Reference Architecture[END_REF]. Note that, as we have described earlier, all these ontologies are designed to satisfy specific requirements for the platform they are applied in and thus, do not completely follow the requirements set in Section 2.

Even with so many ontologies defined for IoT-specific platforms, a single comprehensive ontology comprising of the core concepts is missing. Developers should, therefore, reuse existing ontologies and merge them into new ontologies as per their requirements. Before defining a new ontology, they should identify the competency questions. If the competency questions can be answered by existing ontologies, then developers should emphasize on reusing concepts and relationships from existing ontologies. This allows easy integration of heterogeneous data and facilitates developing reasoning capabilities on top of semantic data. The reasoners can provide useful insights about the systems and their output/reasoning data can also serve as raw data for other systems/applications. However, if a developer has to define new concepts for his/her systems, he/she should follow the best practices. These best practices are: reusing existing concepts as much as possible and aligning the concepts with equivalence relations [START_REF] Suarez-Figueroa | NeOn Methodology for Building Networks Ontology: Specification, Scheduling and Reuse[END_REF], validating the ontology using ontology validators (see Section 4), having recommended ontology metadata 30 , making the ontology accessible, following a modular approach so that the ontology is reusable, and documenting it with samples to demonstrate its usage [START_REF] Gyrard | Semantic Web Methodologies, Best Practices and Ontology Engineering applied to Internet of Things[END_REF].

Conclusion

In this paper, we study existing ontologies in the domain of IoT and identify the major concepts listed by them. We identify that no existing ontology is comprehensive enough to document all the concepts required for semantically annotating an end-to-end IoT application as ontologies are often restricted to a certain domain. Hence, as a step towards developing a comprehensive unified ontology for IoT domain, we identify the core concepts required for developing an IoT application. We study the ontologies proposed for those concepts and analyse the methods used for their evaluation. Our study identifies that there are no concrete methods for evaluating an ontology, and developers must always follow the best practices while publishing a new ontology in order to enhance readability, usability, extensibility, and interoperability.

Figure 1 .

 1 Figure 1. Challenges may arise with the use of semantic approaches in IoT applications. The lack of a common semantics may lead to interoperability and design issues.

Figure 2 .

 2 Figure 2. Distributing the concepts requirement of an IoT-based application into horizontal and vertical elements

  use W3C's SSN ontology and propose a system to provide semantic interoperability between the different protocols used by different classes of IoT applications such as wearable devices, and hardware platforms like Raspberry Pi, Arduino, etc. Another example of such a system is STAR-CITY (Semantic Traffic Analysis and Reasoning for CITY)[START_REF] Lécué | Star-city: Semantic Traffic Analytics and Reasoning for City[END_REF]. This system uses multiple domain ontologies29 to combine heterogeneous data sources -static and dynamic, generating data that has variety, has high sampling rate, and volume. The system provides traffic analysis and reasoning for efficient urban planning which supports re-usability of heterogeneous, real-time data, and expose them to the end users through REST-ful web-APIs by reusing and combining existing domain ontologies instead of proposing a new one.Another approach to reuse existing concepts in ontologies, while adding new concepts specific to the domain, is to provide a hierarchical structure composed of two sub-ontologies as suggested by Lee et al.[START_REF] Lee | Location-based Service using Ontology-based Semantic Queries: A study with a focus on Indoor Activities in a University Context[END_REF]. The authors use existing concepts as part of the 'upper' ontology and define new domain-specific concepts as part of the 'lower' ontology in the hierarchy of sub-ontologies. This hierarchical division enhances the readability, and thus improves the scope of reusability of the proposed ontology.Several works have now started reusing existing ontologies by combining them to propose new ontologies for the IoT domain. These new ontologies are meant for specific platforms aimed at collecting and integrating IoT data. However, they lack one or more concepts identified in Section 2, rendering them incomplete for the IoT domain. IoT-Lite[START_REF] Bermudez-Edo | IoT-Lite: A Lightweight Semantic Model for the Internet of Things[END_REF], for example, provides a lightweight instantiation of the SSN ontology and extends it using SAO. They also include dynamic semantics by introducing mathematical formulas to estimate missing sensor values during the data annotation phase itself. This saves time as the data is no longer required to be sent to a server for extrapolating missing sensor values, rendering IoT-Lite dynamic, fast, and interoperable; thus, making it suitable for constrained IoT environments. The concepts covered by IoT-Lite include sensor information and location. VITAL ontology[START_REF] Kazmi | Overcoming the Heterogeneity in the Internet of Things for Smart Cities[END_REF] also follows a similar approach by combining concepts from SSN, QUDT, OWL-Time, and WGS84 to define sensors, measurements, time, and location concepts respectively. OpenIoT ontology[START_REF] Van Der Schaaf | Mapping the OGC Sensor Things API onto the OpenIoT Middleware[END_REF] also uses SSN as a base to build upon concepts required for IoT applications and testbeds -Observation, Sensor, and Location. It further extends to define utility metrics for Service level agreements between its users and provided OpenIoT services.Authors of IoT-O ontology[START_REF] Seydoux | IoT-O, a Core-Domain IoT Ontology to Represent Connected Devices Networks[END_REF] claimed to built IoT-O ontology such that it is modular and focused on two sets of requirements -Conceptual and Functional. They defined "conceptual" requirements as those requirements that form the core of any IoT-related ontology. These were based on the description of devices, data, services and their lifecycle. Further, "functional" requirements were defined as those requirements that follow best practices defined by the semantic community. IoT-O is one of the first approaches towards unification of the IoT ontologies. IoT-O reuses concepts from SSN, SAN, DUL, QUDT, oneM2M and further, defines new concepts. Nevertheless, the ontology lacks a complete/holistic view of context. FIESTA-IoT ontology[START_REF] Agarwal | Unified IoT Ontology to Enable Interoperability and Federation of Testbeds[END_REF] is yet another attempt to unify existing ontologies for the IoT domain. It covers most of the concepts identified in Section 2. However, it lacks concepts for annotating context information such as place of interest, has no support for context-aware services and has limited notion for activity, actuators, virtual entities, etc. oneM2M ontology[START_REF] Onem2m | oneM2M Base Ontology[END_REF], on the other hand, although supported by standardization bodies in IoT, also lacks contextual information. oneM2M provides minimal concepts needed for representing a device and its functionality. oneM2M does not reuse any existing ontology to define the concepts.

https://www.statista.com/statistics/471264/iot-number-ofconnected-devices-worldwide/

2 http://www.cisco.com/c/dam/en/us/solutions/collateral/serviceprovider/global-cloud-index-gci/white-paper-c11-738085.pdf

https://www.w3.org/2005/Incubator/ssn/ssnx/ssn

A new version of SSN is available, however, it still does not address the issues discussed.

For a detailed study on context-aware ontologies in the domain of IoT before 2012, we refer the readers to[START_REF] Perera | Context Aware Computing for the Internet of Things: A survey[END_REF].

http://www.smartsantander.eu/

https://www.iot-lab.info/

https://io.ambiciti.mobi

https://en.wikipedia.org/wiki/SensorML

http://bit.ly/2nedvM1

http://sensormeasurement.appspot.com/?p=ontologies

https://www.eebus.org/en/about-us/

http://www.energy-home.it/SitePages/Home.aspx

http://www.qudt.org/

https://www.w3.org/TR/vcard-rdf/

http://www.cs.rochester.edu/ ~ferguson/daml/

http://www.daml.org/services/daml-s/0.9/

http://www.ksl.stanford.edu/ontologies/time

http://www.w3.org/2006/time\#

http://w3c.github.io/sdw/time/

http://motools.sourceforge.net/timeline/timeline.html#term_Instant

http://iot.ee.surrey.ac.uk/citypulse/ontologies/sao/saopy.html

http://oops.linkeddata.es

http://oops.linkeddata.es/catalogue.jsp

http://linkeddata.uriburner.com:8000/vapour

https://www.w3.org/TR/swbp-vocab-pub/

http://graphite.ecs.soton.ac.uk/checker/

A comprehensive list of existing semantic validators can be found on https: //www.w3.org/2001/sw/wiki/SWValidators

http://goo.gl/5TbTT2

Acknowledgement

This work is partially funded by the European project "Federated Interoperable Semantic IoT/cloud Testbeds and Applications (FIESTA-IoT)" from the European Union's Horizon 2020 Programme with the Grant Agreement No. CNECT-ICT-643943.