Aleksandre Maskharashvili
email: aleksandre.maskharashvili@inria.fr

Sylvain Pogodalla
email: sylvain.pogodalla@inria.fr

Constituency and Dependency Relationship from a Tree Adjoining Grammar and Abstract Categorial Grammar Perspective *

This paper gives an Abstract Categorial Grammar (ACG) account of (Kallmeyer and Kuhlmann, 2012)'s process of transformation of the derivation trees of Tree Adjoining Grammar (TAG) into dependency trees. We make explicit how the requirement of keeping a direct interpretation of dependency trees into strings results into lexical ambiguity. Since the ACG framework has already been used to provide a logical semantics from TAG derivation trees, we have a unified picture where derivation trees and dependency trees are related but independent equivalent ways to account for the same surface-meaning relation.

Introduction

Tree Adjoining Grammars (TAG) [START_REF] Aravind | Tree adjunct grammars[END_REF][START_REF] Aravin | Treeadjoining grammars[END_REF]) is a tree grammar formalism relying on two operations between trees: substitution and adjunction. In addition to the tree generated by a sequence of such operations, there is a derivation tree which records this sequence. Derivation trees soon appeared as good candidates to encode semantic-like relations between the elementary trees they glue together. However, some mismatch between these trees and the relative scoping of logical connectives and relational symbols, or between these trees and the dependency relations, have been observed. Solving these problems often leads to modifications of derivation tree structures [START_REF] Schabes | An alternative conception of tree-adjoining derivation[END_REF][START_REF] Kallmeyer | Using an enriched tag derivation structure as basis for semantics[END_REF][START_REF] Aravind | Flexible composition in ltag: Quantifier scope and inverse linking[END_REF][START_REF] Rambow | D-Substitution Grammars[END_REF]Chen-Main and Joshi, To appear).

While alternative proposals have succeeded in linking derivation trees to semantic representa- * Work supported by ANR (ANR-12-CORD-0004). tions using unification [START_REF] Kallmeyer | Ltag semantics with semantic unification[END_REF][START_REF] Kallmeyer | Scope and situation binding for ltag[END_REF] or using an encoding [START_REF] Pogodalla | Computing Semantic Representation: Towards ACG Abstract Terms as Derivation Trees[END_REF][START_REF] Pogodalla | Advances in Abstract Categorial Grammars: Language Theory and Linguistic Modeling[END_REF] of TAG into the ACG framework (de [START_REF] De | Towards abstract categorial grammars[END_REF], only recently [START_REF] Kallmeyer | A formal model for plausible dependencies in lexicalized tree adjoining grammar[END_REF] has proposed a transformation from standard derivation trees to dependency trees.

This paper provides an ACG perspective on this transformation. The goal is twofold. First, it exhibits the underlying lexical blow up of the yield functions associated with the elementary trees in [START_REF] Kallmeyer | A formal model for plausible dependencies in lexicalized tree adjoining grammar[END_REF]. Second, using the same framework as [START_REF] Pogodalla | Computing Semantic Representation: Towards ACG Abstract Terms as Derivation Trees[END_REF][START_REF] Pogodalla | Advances in Abstract Categorial Grammars: Language Theory and Linguistic Modeling[END_REF] allows us to have a shared perspective on a phrase-structure architecture and a dependency one and an equivalence on the surface-meaning relation they define.

Abstract Categorial Grammars

ACGs provide a framework in which several grammatical formalisms may be encoded (de Groote and [START_REF] Pogodalla | Computing Semantic Representation: Towards ACG Abstract Terms as Derivation Trees[END_REF]. They generate languages of linear λ-terms, which generalize both string and tree languages. A key feature is to provide the user direct control over the parse structures of the grammar, the abstract language, which allows several grammatical formalisms to be defined in terms of ACG, in particular TAG [START_REF] De | Tree-adjoining grammars as abstract categorial grammars[END_REF]. We refer the reader to [START_REF] De | Towards abstract categorial grammars[END_REF][START_REF] Pogodalla | Advances in Abstract Categorial Grammars: Language Theory and Linguistic Modeling[END_REF] for the details and introduce here only few relevant definitions and notations.

Definition. A higher-order linear signature is defined to be a triple Σ = A, C, τ , where:

• A is a finite set of atomic types (also noted

A Σ ), • C is a finite set of constants (also noted C Σ ),
• and τ is a mapping from C to T A the set of types built on A: T A ::= A|T A T A (also noted T Σ ).

A higher-order linear signature will also be called a vocabulary. Λ(Σ) is the set of λ-terms built on Σ, and for t ∈ Λ(Σ) and α ∈ T Σ such that t has type α, we note t : Σ α (the Σ subscript is omitted when it is obvious from the context).

Definition. An abstract categorial grammar is a quadruple G = Σ, Ξ, L, s where:

1. Σ and Ξ are two higher-order linear signatures, which are called the abstract vocabulary and the object vocabulary, respectively; 2. L : Σ -→ Ξ is a lexicon from the abstract vocabulary to the object vocabulary. It is a homomorphism 1 that maps types and terms built on Σ to types and terms built on Ξ. We note t:= G u if L(t) = u and omit the G subscript if obvious from the context. 3. s ∈ T Σ is a type of the abstract vocabulary, which is called the distinguished type of the grammar.

Definition. The abstract language of an ACG

G = Σ, Ξ, L, s is A(G ) = {t ∈ Λ(Σ) | t : Σ s} The object language of the grammar O(G ) = {t ∈ Λ(Ξ) | ∃u ∈ A(G ). t = L G (u)}
Since there is no structural difference between the abstract and the object vocabulary as they both are higher-order signatures, ACGs can be combined in different ways. Either by having a same abstract vocabulary shared by several ACGs in order to make two object terms (for instance a string and a logical formula) share the same underlying structure as G d-ed trees and G Log in Fig. 1. Or by making the abstract vocabulary of an ACG the object vocabulary of another ACG, allowing the latter to control the admissible structures of the former, as G yield and G d-ed trees in Fig. 1.

TAG as ACG

As Fig. 1 shows, the encoding of TAG into ACG uses two ACGs G d-ed trees = Σ derθ , Σ trees , L d-ed trees , s and

G yield = Σ trees , Σ string , L yield , τ .
We exemplify the encoding 2 of a TAG analyzing (1) 3 1 In addition to defining L on the atomic types and on the constants of Σ, we have:

• If α β ∈ TΣ then L(α β) = L(α) L(β). • If x ∈ Λ(Σ) (resp. λx.t ∈ Λ(Σ) and t u ∈ Λ(Σ)) then L(x) = x (resp. L(λx.t) = λx.L(t) and L(t u) = L(t) L(u)
) with the proviso that for any constant c :Σ α of Σ we have L(c) :Ξ L(α).

2 We refer the reader to [START_REF] Pogodalla | Advances in Abstract Categorial Grammars: Language Theory and Linguistic Modeling[END_REF] for the details. 3 The TAG literature typically uses this example, and [START_REF] Kallmeyer | A formal model for plausible dependencies in lexicalized tree adjoining grammar[END_REF] as well, to show the This sentence is usually analyzed in TAG with a derivation tree where the to love component scopes over all the other arguments, and where claims and seems are unrelated, as Fig. 2(a) shows.

Λ(Σ derθ ) Λ(Σtrees) G d-ed trees Λ(Σ string ) G yield Λ(Σ Log ) G Log
The three higher-order signatures are: Σ derθ : Its atomic types include s, vp, np, s A , vp A . . . where the X types stand for the categories X of the nodes where a substitution can occur while the X A types stand for the categories X of the nodes where an adjunction can occur. For each elementary tree γ lex. entry it contains a constant C lex. entry whose type is based on the adjunction and substitution sites as Table 1 shows. It additionally contains constants I X : X A that are meant to provide a fake auxiliary tree on adjunction sites where no adjunction actually takes place in a TAG derivation. Σ trees : Its unique atomic type is τ the type of trees. Then, for any X of arity n belonging to the ranked alphabet describing the elementary trees of the TAG, we have a constant

X n : n times τ • • • τ τ Σ string :
Its unique atomic type is σ the type of strings. The constants are the terminal symbols of the TAG (with type σ), the concatenation + : σ σ σ and the empty string ε : σ. Table 1 illustrates L d-ed trees . 4 L yield is defined as follows:

•

L yield (τ ) = σ; • for n > 0, L yield (X n ) = λx 1 • • • x n .x 1 + • • • + x n ;
mismatch between the derivation trees and the expected semantics and the relative scopes of the predicates. 4 With L d-ed trees (XA) = τ τ and for any other type X, L d-ed trees (XA) = τ .

• for n = 0, X 0 : τ represents a terminal symbol and L yield (X 0 ) = X. Then, the derivation tree, the derived tree, and the yield of Fig. 2 are represented by: Trees [START_REF] Kallmeyer | A formal model for plausible dependencies in lexicalized tree adjoining grammar[END_REF]'s process to translate derivation trees into dependency trees is a two-step process. The first one does the actual transformation, using macro-tree transduction, while the second one modifies the way to get the yield from the dependency trees rather than from the derivation ones.

t 0 = C to love (C claims I s C Bill ) (C seems I vp ) C Mary C John L d-ed trees (t 0 ) = s 2 (np 1 John) (s 2 (np 1 Bill) (vp 2 claims (s 2 (np 1 Mary) (vp 2 seems (vp 1 to love))) L yield (L d-ed trees (t 0 )) = John + Bill + claims + Mary + seems + to love

Derivation To Dependency Trees

This transformation aims at modeling the differences in scope of the argument between the derivation tree for (1) shown in Fig. 2(a) and the corresponding dependency tree shown in Fig. 2(b). For instance, in the derivation trees, claims and seems are under the scope of to love while in the dependency tree this order is reversed. According to [START_REF] Kallmeyer | A formal model for plausible dependencies in lexicalized tree adjoining grammar[END_REF], such edge reversal is due to the fact that an edge between a complement taking adjunction (CTA) and an initial tree has to be reversed, while the other edges remain unchanged.

Moreover, in case an initial tree accepts several adjunction of CTAs, [START_REF] Kallmeyer | A formal model for plausible dependencies in lexicalized tree adjoining grammar[END_REF] hypothesizes that the farther from the head a CTA is, the higher it is in the dependency tree. In the case of to love, the s node is farther from the head than the vp node. Therefore any adjunction on the s node (e.g. claims) should be higher than the one on the vp node (e.g. seems) in the dependency tree. We represent the dependency tree for (1) as t 0 = d claims d Bill (d seems (d to love d John d Mary )).

In order to do such reversing operations, [START_REF] Kallmeyer | A formal model for plausible dependencies in lexicalized tree adjoining grammar[END_REF] uses Macro Tree Transducers (MTTs) [START_REF] Engelfriet | Macro tree transducers[END_REF]. Note that the MTTs they use are linear, i.e. non-copying. It means that any node of an input tree cannot be translated more than once. [START_REF] Yoshinaka | Extensions and Restrictions of Abstract Categorial Grammars[END_REF] has shown how to encode such MTTs as the composition G • G -1 of two ACGs, and we will use a very similar construct.

4.2

The Yield Functions [START_REF] Kallmeyer | A formal model for plausible dependencies in lexicalized tree adjoining grammar[END_REF] adds to the transformation from derivation trees to dependency trees the additional constraint that the string associated with a dependency structure is computed directly from the latter, without any reference to the derivation tree. To achieve this, they use two distinct yield functions: yield TAG from derivation trees to strings, and yield dep from dependency trees to strings.

Let us imagine an initial tree γ i and an auxiliary tree γ a with no substitution nodes. The yield of the derived tree resulting from the operations of the derivation tree γ of Fig. 3 defined in [START_REF] Kallmeyer | A formal model for plausible dependencies in lexicalized tree adjoining grammar[END_REF]

is such that yield TAG (γ) = a 1 + w 1 + a 2 + w 2 + a 3 = (yield TAG (γ i ))(yield TAG (γ a )) = (λ x 1 , x 2 .a 1 + x 1 + a 2 + x 2 + a 3 ) w 1 , w 2 where x, y denotes a tuple of strings.
Because of the adjunction, the corresponding dependency structure has a reverse order (γ = γ a (γ i )), the requirement on yield dep imposes that

yield dep (γ ) = a 1 + w 1 + a 2 + w 2 + a 3 = (yield dep (γ a ))(yield dep (γ i )) = (λ x 1 , x 2 , x 3 .x 1 + w 1 + x 2 + w 2 + x 3 ) a 1 , a 2 , a 3
In the interpretation of derivation trees as strings, initial trees (with no substitution nodes) Indeed, an initial tree can have several adjunction sites. In this case, to be ready for another adjunction after a first one, the first result itself should be a tuple of strings. So an initial tree (with no substitution nodes) with n adjunction sites is interpreted as a (2n + 1)-tuple of strings. Accordingly, depending on the location where it can adjoin, an auxiliary tree is interpreted as a function from (2k + 1)-tuple of strings to (2k -1)-tuple of strings.

γ i = Y X a 1 a 3 a 2 X γ a = X X * w 1 w 2 γ = γ i γ a
Taking into account that to model trees having the substitution nodes is then just a matter of adding k string parameters where k is the number of substitution nodes in a tree. Then using the interpretation: Remark. The given interpretation of d to love is only valid for structures reflecting adjunctions both on the s node and on the vp node of γ to love . So actually, an initial tree such as γ to love yields four interpretations: one with the two adjunctions (5tuple), two with one adjunction either on the vp node or on the s node (3-tuple), and one with no adjunction (1-tuple). The two first cases correspond to the sentences (2a) and (2b).5 Accordingly, we need multiple interpretations for the auxiliary trees, for instance for the two occurrences of seems in (3) where the yield of the last one yield dep (d seems ) maps a 5-tuple to a 3-tuple, and the yield of the first one maps a 3-tuple to a 3-tuple. And yield dep (d claims ) maps a 3-tuple to a 1-tuple of strings. We will mimic this behavior by introducing as many different non-terminal symbols for the dependency structures in our ACG setting.

yield dep (d to love ) =
(2) a. John Bill claims Mary seems to love b. John Mary seems to love (3) John Bill seems to claim Mary seems to love Remark. Were we not interested in the yields but only in the dependency structures, we wouldn't have to manage this ambiguity. This is true both for (Kallmeyer and Kuhlmann, 2012)'s approach and ours. But as we have here a unified framework for the two-step process they propose, this lexical blow up will result in a multiplicity of types as Section 5 shows.

In order to encode the MTT acting on derivation trees, we introduce a new abstract vocabulary Σ derθ for disambiguated derivation trees as in [START_REF] Yoshinaka | Extensions and Restrictions of Abstract Categorial Grammars[END_REF]. Instead of having only one constant for each initial tree as in Σ derθ , we have as many of them as adjunction combinations. For instance, γ to love gives rise to the several constants [START_REF] Yoshinaka | Extensions and Restrictions of Abstract Categorial Grammars[END_REF]'s encoding of [START_REF] Kallmeyer | A formal model for plausible dependencies in lexicalized tree adjoining grammar[END_REF] MTT rules: q 0 , C to love (x 1 , x 2 , x 3 , x 4 ) → q 2 , x 2 ( q 4 , x 4 (d to love ( q 1 , x 1 , q 3 , x 3 ))) q 0 , C to love (x 1 , x 2 , x 3 ) → q 2 , x 2 (d to love ( q 1 , x 1 , q 3 , x 3 )) q 0 , C to love (x 1 , x 2 , x 3 ) → q 4 , x 4 (d to love ( q 1 , x 1 , q 3 , x 3 )) q 0 , C to love (x 1 , x 2 ) → d to love ( q 1 , x 1 , q 3 , x 3 ) where the states q 0 , q 1 , q 2 , q 3 and q 4 are given the names s, np, s . . . are designed in order to indicate that a given adjunction has n adjunctions above it (i.e. which scope over it). The superscripts (2(n + 1))(2(n -1)) express that an adjunction that has n adjunctions above it is translated as a function that takes a 2(n + 1)-tuple as argument and returns a 2(n -1)tuple.

Σ
To model auxiliary trees which are CTAs we need a different strategy. For each such adjunction tree T we have two sets in Σ derθ : S 1 T the set of constants which can be adjoined into initial trees and S 2 T the set of constants which can be adjoined into auxiliary trees.

For instance, γ seems would generate S A as its argument type (e.g. C 01 to love ).

6 See note 5.

C 11 seems31 is of type s 3-3 A vp 3-3 A vp 31
A . It means it expects two adjunctions at its s and vp nodes respectively and returns back a term of type vp 31

A (as in John claims to appear to seem to love Mary). Here, s 3-3 A and vp 3-3 A are types used for modeling adjunction on adjunctions.

When an auxiliary tree is adjoined into another auxiliary tree as in (3), we do not allow the former to modify the tupleness of the latter. For instance γ seems would generate S 2 seems that includes C 11 seems5-5 etc. C 00 seems3-3 has a subscript (k-k) that correspond to adjunctions into adjunction trees. The type of C 00 seems3-3 is vp 3-3 A , meaning that it can directly adjoin into auxiliary trees which have arguments of type

C 11 seems3-3 , C 10 seems3-3 , C 01 seems3-3 , C 00 seems3-3 ,
vp 3-3 A . C 01 seems3-3 is of type vp 3-3 A vp 3-3
A , which means that it itself expects an adjunction and the result can be adjoined into another adjunction tree. Now it is easy to define L der from Σ derθ to Σ derθ . It maps every type X ∈ Σ derθ to X ∈ Σ derθ and every X N A to X A ; types without numbers are mapped to themselves, i.e. s to s, np to np, etc. Moreover, the different versions of some constant, that were introduced in order to extract the yield, are translated using only one constant and fake adjunctions. The ACG of [START_REF] Pogodalla | Advances in Abstract Categorial Grammars: Language Theory and Linguistic Modeling[END_REF] mapping TAG derivation trees to logical formulas already encoded some reversal of the predicate-argument structure. Here we map the disambiguated derivation trees to dependency structures. The vocabulary that define these dependency trees is Σ dep . It is also designed to allow us to build two lexicons from it to Σ string (to provide a direct yield function) and to Σ Log (to provide a logical semantic representation).

In

L dep (s) = τ 1 L dep (np) = τ 1 np L dep (X (2n+1)(2n-1) A ) = τ 2n+1 τ 2n-1 L dep (X (2n+1)(2n+1) A ) = τ 2n+1 τ 2n+1 for X ∈ s 31 A ,

Conclusion

In this paper, we have given an ACG perspective on the transformation of the derivation trees of TAG to the dependency trees proposed in [START_REF] Kallmeyer | A formal model for plausible dependencies in lexicalized tree adjoining grammar[END_REF]. Figure 4 illustrates the architecture we propose. This transformation is a two-step process using first a macrotree transduction then an interpretation of dependency trees as (tuples of) strings. It was known from [START_REF] Yoshinaka | Extensions and Restrictions of Abstract Categorial Grammars[END_REF] how to encode a macrotree transducer into a G dep •G -1 der ACG composition. Dealing with typed trees to represent derivation trees allows us to provide a meaningful (wrt. the TAG formalism) abstract vocabulary Σ derθ encoding this macro-tree transducer. The encoding of the second step then made explicit the lexical blow up for the interpretation of the functional symbols of the dependency trees in [START_REF] Kallmeyer | A formal model for plausible dependencies in lexicalized tree adjoining grammar[END_REF])'s construct. It also provides a push out (in the categorical sense) of the two morphisms from the disambiguated derivation trees to the derived trees and to the dependency trees. The diagram is completed with the yield function from the derived trees and from the dependency trees to the string vocabulary.

Finally, under the assumption of [START_REF] Kallmeyer | A formal model for plausible dependencies in lexicalized tree adjoining grammar[END_REF] of plausible dependency structures, we get two possible grammatical approaches to the surface-semantics relation that are related but independent: it can be equivalently modeled using either a phrase structure or a dependency model.

Figure 1 :

 1 Figure 1: ACG architecture for TAG

Figure 2 :

 2 Figure 2: John Bill claims Mary seems to love

Figure 3 :

 3 Figure 3: Yield from derivation trees

  For instance: L der (C 11 to love ) = C to love L der (C 10 to love ) = λxso.C to love x I vp s o L der (C 00 to love ) = C to love I s I vp 6 Encoding a Dependency Grammar

Figure 4 :

 4 Figure 4: General architecture

Table 1 :

 1 Abstract constants of Σ derθTheir images by Σ derθ TAG as ACG: the L d-ed trees lexicon are interpreted as functions from tuples of strings into strings, and auxiliary trees as tuples of strings. The interpretation of dependency trees as strings leads us to interpret initial trees as tuples of strings and auxiliary trees as function from tuples of strings to strings.

	The corresponding TAG trees

  λx 11 x 21 . x 11 , x 21 , to love, ε, ε yield dep (d seems ) = λ x 11 , x 12 , x 13 , x 14 , x 15 . x 11 , x 12 + seems + x 13 x 14 , x 15 yield dep (d claims ) = λx 21 x 11 , x 13 , x 14 . x 11 + x 21 + claims + x 14 + x 13 we can check that yield dep (d claims d Bill (d seems (d to love d Mary d

John ))) = John + Bill + claims + Mary + seems + to love

  C 11 to love is used to model sentences where both adjunctions are performed into γ to love . C 10 to love and C 01 to love are used for sentences where only one adjunction at the s or at the vp node occurs respectively. C 00 to love : np np s is used when no adjunction occurs. 6 This really mimics

	derθ : C 11 to love C 10 to love C 01 to love C 00 to love	: s 31 A : s 31 A : vp 31 A : np	vp 53 A np np np	np np np s	s	np s	s
	Here,

  Σ dep constants are typed as follows: d 5 indicates that they are modeled as 2tuples in Σ string . Now we can define L dep , the lexicon from Σ derθ to Σ dep translating disambiguated derivation trees into dependency trees:

	have constants like: d 3 s to love : τ 1 np	τ 1 np	τ 3 and
	d 3 v to love : τ 1 np	τ 1 np	τ 3 .
	Moreover, we have constants for adjunction
	trees, like d 5 seems : τ 5 the translation of C 01 seems53 , and d 5-5 τ 3 that will be used in τ 5 seems : τ for C 00 seems5-5 . Furthermore, additional constants
	are needed to have things correctly typed. For this
	reason, the constants d 1 3 , d 3 5 etc. are introduced. Each d 2n-1 τ 2n-1 . 2n+1 has type τ 2n+1 Finally, non-CTAs like n A , n d A , vp A and s A are translated as τ 2 n A , τ 2 n d , τ 2 vp , and τ 2 s respectively. A A superscript 2
				to love :
				τ 1 np	τ 1 np	τ 5 . Here, τ 1 np is the type
				into which the np type is translated from disam-
				biguated derivation tree. The superscript 1 indi-
				cates that τ 1 np will be translated into 1-tuple into
				Σ string . Now, it is easy to see that in order to
				translate C 10 to love : s 31 a C 01 to love : vp 31 a np	np np	np s, we need to s and

  vp 53 A . . . L dep. yield : Σ dep -→ Σ string and L dep. log : Σ dep -→ Σ Log .Table 2 provides examples of these two translations. L dep. yield : It translates any atomic type τ n or τ n M1 M2 . . . Mn where each Mi has type σ. Let us show for the sentence (1) how the ACGs defined above work with the data provided in Table 2. Its representation in Σ derθ is: T 0 = C 11 to love (C claims31 C Bill ) C seems53 C Mary C John . Then L der (T 0 ) = t 0 and L dep (T 0 ) = d 1 claims d Bill (d 53 seems (d 5 to love d Mary d John )) = t 0 and finally L dep. yield (t 0 ) = L yield (L d-ed trees (t 0 )) = λf.f (John + (Bill + (claims + ((Mary + ((seems + to love) + )) + )))) and L dep. log (t 0 ) = claim bill (seem (love john mary)

	L dep (C 11 to love ) L dep (C 10 to love ) L dep (C 01 to love ) L dep (C 00 seems53 ) L dep (C 01 seems53 ) L dep (C 11 seems53 ) L dep (C 01 seems5-5 ) = λV x.V (d 5-5 = λS V s o.S(V (d 5 to love s o)) = λS s o.S(d 3 to love s o) = λS V s o.V (d 3 to love s o) = λx.d 5 seems x = λV x.d 53 (V (d 5 seems x)) = λS V x.d 53 (S(V (d 5 seems x))) seems x) L dep (C 00 seems5-5 ) = λx.d 5-5 seems x Furthermore, we describe Σ Log 7 and define two lexicons: X with X ∈ {n A , n d A . . .} as a n-tuple of string (σ σ • • • σ) n+1-times σ. 8 Σ Log : Its atomic types are e and t and we have the constants: john, mary, bill of type e, the con-stant love of type e e t, the constant claim of type e t t and the constant seem of type t t. L dep. log : Each τ 2(n+1) is mapped to t, τ 1 np is mapped to (e t) t, τ 2 n A d is mapped to (e → t) (e t) t. The types 8 We encode a n-tuple M1, . . . , Mn as λf.f of non-complement-taking verbal or senten-tial adjunctions τ 2 vp and τ 2 s are translated as t t.

7

We refer the reader to

[START_REF] Pogodalla | Advances in Abstract Categorial Grammars: Language Theory and Linguistic Modeling[END_REF]

for the details.

Table 2 :

 2 Abstract constants of Their images by L dep. yield Their images by L dep. log Σ dep d John : τ 1 np John λP.P john d 5 to love : τ 1 np τ 1 np τ 5 λS O.λf.f O S to love λO S.S(λx.O(λy.(love x y))) d 3s to love : τ 1 np τ 1 np τ 3 λS O.λf.f O (S + love) λO S.S(λx.O(λy.(love x y))) d 3v to love : τ 1 np τ 1 np τ 3 λS O.λf.f (O + S) to love λO S.S(λx.O(λy.(love x y))) d 1 claims : τ 1 np τ 1 np τ 1 λS c.λf.c(λx1 x2 x3.f (x1 + S + claims + x2 + x3)) λS c.S(λx.claim x c) λgf.g(λx1 . . . xn.f x1 . . . (xn + xn+1 + xn+2) . . . x2n+1) λx.x : t t Lexicons for yield and semantics from the dependency vocabulary

	d 3 claims : τ 1 np	τ 1 np	τ 3 λS c.λf.c(λx1 x2 x3.f (x1 + S) (claims + x2 + x3))	λS c.S(λx.claim x c)
	d 5-5 seems : τ 5	τ 5		λc.λf.c(λx1 . . . x5.f x1 (x2 + seems + x3 + x4)x5)	λc.seem c
	d 5 seems : τ 5	τ 3		λc.λf.c(λx1 . . . x5.f x1 x2 (seems + x3) x4 x5)	λc.seem c
	d 2n-1 2n+1 : τ 2n+1	τ 2n-1
				disambiguated
				derivation
				trees
			L der	Λ(Σ derθ )	L dep
	L d-ed trees	derivation trees Λ(Σ derθ )	dep. trees Λ(Σ dep )
	derived trees
	Λ(Σ trees )		L dep. yield	L dep. log
	L yield	strings Λ(Σ string )	logical formulas Λ(Σ Log )

As the two other ones are not correct English sentences, we can rule them out. However, from a general perspective, we should take such cases into account.


Stanislas Vertu

Jean-Jacques Delaunay

Olivier Haeberlé

Diffraction microtomography with sample rotation: influence of a missing apple core in the recorded frequency space

Keywords: Image reconstruction, tomography, Fourier optics, holographic interferometry

Diffraction microtomography in coherent light is foreseen as a promising technique to image transparent living samples in three dimensions without staining. Contrary to conventional microscopy with incoherent light, which gives morphological information only, diffraction microtomography makes it possible to obtain the complex optical refractive index of the observed sample by mapping a three-dimensional support in the spatial frequency domain. The technique can be implemented in two configurations, namely, by varying the sample illumination with a fixed sample or by rotating the sample using a fixed illumination. In the literature, only the former method was described in detail. In this report, we precisely derive the three-dimensional frequency support that can be mapped by the sample rotation configuration. We found that, within the first-order Born approximation, the volume of the frequency domain that can be mapped exhibits a missing part, the shape of which resembles that of an apple core. The projection of the diffracted waves in the frequency space onto the set of sphere caps covered by the sample rotation does not allow for a complete mapping of the frequency along the axis of rotation due to the finite radius of the sphere caps. We present simulations of the effects of this missing information on the reconstruction of ideal objects.

Introduction

In transmission microscopy, the observation of nonfluorescent transparent or quasi-transparent samples poses a real challenge because of the inherent low contrast in refractive index associated with this type of samples. This low contrast makes it difficult to identify intracellular structures. Furthermore, conventional transmission microscopes suffer from a poor resolution, especially along the optical axis because of incomplete mapping of the observed object frequencies. The missing information, referred to as the "missing cone", induces anisotropy in the spatial resolution which is responsible for object deformation. To address these two issues, sample rotation and subsequent observation of the sample under different view angles can be used to record a more complete set of the object frequencies and reconstruct the threedimensional object from this extended frequency map. For non-diffractive samples, this method is well-known in the medical field under the name of Computed Tomography (CT). For weakly diffractive samples, the threedimensional distribution of the complex refractive index can be reconstructed from the knowledge of the scattered fields sampled under various view angles according to the diffraction tomography theorem [1,2]. Thus the observation of cell internal structures as well as cell arrangements in the three dimensions is in principle possible.

Three-dimensional observation of weakly diffractive samples have been so far realized by varying the sample illumination with a fixed sample [3,4,[START_REF] Haeberle | Modern Research and Educational Topics in Microscopy[END_REF][START_REF] Simon | [END_REF]7] or by rotating the sample using a fixed illumination [8,9,10,11]. In the sample illumination variation method, tomography is realized by varying the sample illumination angle in a range limited by the illumination system (usually a condenser) numerical aperture, drastically increasing the object spatial frequencies captured by this system in comparison to a conventional holographic transmission microscope, which uses only one direction of illumination. The three-dimensional refractive index distribution of the sample is reconstructed by applying the diffraction tomography theorem. Because of the limited range of illumination angles, the object frequencies are not captured isotropically, a "missing cone" remains and the reconstruction exhibits deformation along the optical axis.

In the sample rotation method, the sample is inserted in a microcapillary, which is used to precisely rotate the sample. This configuration allows for a complete rotation of the sample, but unavoidable displacements of the microcapillary may induce errors in the sample position, and therefore in the image reconstruction. The reconstruction of the variation in refractive index of transparent samples is usually obtained by backprojecting the measured sample phase using the Radon transform [8,9,10,11]. By applying backprojection, the obtained spatial resolution is isotropic and no information is missing along the rotation axis. However this reconstruction by backprojection assumes negligible diffraction, which can lead to reconstruction artefacts [9]. A more complete treatment that includes the effects of weak scattering from the sample can be obtained using the diffraction tomography theorem [9]. In this study, we derive the object frequency support mapped by diffraction tomography with sample rotation of a weakly scattering sample.

We found that diffraction tomography with sample rotation offered a nearly isotropic spatial resolution. Missing object frequencies were found to be restricted along the axis of rotation with a shape of the missing frequency support that resembles that of an apple core, therefore the chosen name of "missing apple core".

The non-diffractive reconstruction technique used in the backprojection of the phase is first reviewed in Section 2, then the tomography diffraction reconstruction technique is used in Section 3 to derive the support of the recorded object frequencies. Finally the effects of the missing object frequencies on the reconstruction of ideal objects are examined in Section 4.

Non-diffractive optical coherent microtomography

The backprojection reconstruction technique widely used in CT provides a means to reconstruct non-diffractive three-dimensional objects from the intensity measurement under different view angles. For non-diffractive transparent objects, the measurement of the object phase under different view angles and the subsequent phase backprojection make possible the reconstruction of the distribution of the refractive index difference in three dimensions. For weakly diffractive transparent objects, the assumption of negligible diffraction may be a useful approximation for objects exhibiting a slow variation in refractive index, as shown by results in [8,11]. The condition of a small variation in refractive index is satisfied by optically matching the sample with an index matching material. It should be noted however that the backprojection technique is strictly valid for non-diffractive objects only and that neglecting diffraction generates artifacts in observed images as illustrated in a recent work [9] where circular apertures in a hollow fiber (two-dimensional photonic crystal) were reconstructed with triangular shapes when using the backprojection technique.

Theoretically, for one angle of illumination and one ray of light, the intensity measured is related to the object by a line integral as shown in Figure 1. Let's denote the object by a two-dimensional function f (x, y) and define the line integrals by the (θ, t) parameters. Using a delta function, the Radon transform P θ (t) of the function f (x, y) can be written as:

P θ (t) = +∞ +∞ -∞ -∞ f (x, y)δ(x cos θ + y sin θ -t) dx dy. ( 1
)
The sample is illuminated by a parallel plane wave, so the projection is formed by combining a set of parallel ray integrals. The Fourier slice theorem relates the one-dimensional Fourier transform of a parallel projection P θ (t) of an image f (x, y) taken at an angle θ to a slice of the two-dimensional transform F (u, v) of this image, subtending an angle θ with the u-axis [START_REF] Kak | Principles of Computerized Tomography Imaging[END_REF]. In other words, the Fourier transform of P θ (t) gives the values of F (u, v) along the dashed line represented in the frequency domain on the right side of Figure 1.

Moreover a real microtomography optical setup has a limited Numerical Aperture (N A) imposed by the microscope objective or by the complete system. Consequently the setup acts as a three-dimensional rotationalsymmetric low-pass filter. Therefore the measured data in the frequency domain are limited by a disk for one direction of illumination. By applying the Fourier slice theorem with a fine enough step for θ, it is possible to isotropically map an extended support of object frequencies that completely fills a sphere.

Diffractive optical coherent microtomography

Diffraction by weakly scatterers can be treated within the framework of the first-order Born approximation [1,[START_REF] Born | Principles of Optics[END_REF] that gives an approximated solution to the inverse scattering problem. The situation is now depicted in Figure 2, where U (i) is the incident field and U (s) is the scattered field. The field incident on the weakly scattering object is taken as a monochromatic plane wave of unit amplitude and wavelength λ, propagating in the direction specified by the wave vector k i = k s i where k = 2π/λ and s i is a unit vector, so the expression for the incident field

U (i) ( r) = e i ki• r .
The scattered field propagating in the direction s d has a wave vector k d = k s d . Born and Wolf [1,[START_REF] Born | Principles of Optics[END_REF] have shown that within the first-order Born approximation and in the far zone approximation (k r → ∞), the expression for the scattering field f ( s d , s i ) is:

f ( s d , s i ) = V F ( r ′ )e -ik( s d -si)• r ′ d 3 r ′ , (2)
where F ( r ′ ) is the scattering potential of the medium which varies with the square of the complex refractive index of the medium and r ′ is a vector describing the volume V of the scatterer.

By introducing the vector K = k( s d -s i ) in Equation 2, the scattered field can be expressed as the Fourier transform of the scattering potential evaluated at K:

f ( s d , s i ) = F ( K) = V F ( r ′ )e -i K• r ′ d 3 r ′ . (3)
The vector K describes the different subsets for which the scattering potential frequency can be obtained from the scattered field.

The region of the frequency domain described by the K-vectors forms a sphere called the Ewald sphere [START_REF] Born | Principles of Optics[END_REF], which is shown in Figure 3. Equation 3 provides a very powerful relation between a quantity that can be determined by measurements f ( s d , s i ) and a quantity that is related to the complex refractive index of the object F ( K). In other words, by illuminating a weakly scattering object by a plane wave having direction s i , the knowledge of the scattered field in direction s d in the far field and the incident field allows to reconstruct a threedimensional subset of the object refractive index distribution in the frequency domain. The measure of the scattered field in all possible illumination directions and all possible diffraction directions would make it possible to completely cover the Ewald limiting sphere shown in Figure 3 and therefore obtain an isotropic spatial resolution.

Considering now a microtomography diffractive setup in transmission, the relation between the measured scattered field and the Fourier transform of the projected data is shown in Figure 4. In contrast to the backprojection case of Figure 1 where the Fourier transform values lay on a straight line, the Fourier transform values in the diffractive case are now along an arc when a twodimensional representation is used and cap of spheres considering a 3-D representation [3,[START_REF] Haeberle | Modern Research and Educational Topics in Microscopy[END_REF][START_REF] Simon | [END_REF]7]. Experimentally, the wave scattered by a weakly scattering object can be recorded on the surface of an image sensor. Under the first-order Born approximation, this measured scattered field is interpreted as a two-dimensional spherical subset of the Fourier transform of the sample scattering potential distribution.

This spherical subset of the Fourier transform is limited by the N A of the experimental setup as illustrated in Figure 5. By rotating the sample with a fixed illumination (constant vector k i ), different subsets of the threedimensional frequency distribution of the object scattering potential can be mapped (see Figure 6(a)). In contrast to the non-diffractive case, the extended support of frequencies mapped by recording spatial frequencies for a large number of rotation angles is not a complete sphere. Indeed by rotating a sphere cap along an axis of rotation tangent to the cap top as shown in Figure 6(a), one can cover a volume of points within a sphere except for the points near the rotation axis as depicted in Figure 6(b,c). The bend of the cap does not allow for the mapping of the frequencies along the axis of rotation. Furthermore, when slices perpendicular to the rotation axis are exam- ined, one find out that disks centered on the rotation axis are not mapped. The longer the distance from the frequency origin, the larger the disk area becomes that is not covered by the rotating caps. Accordingly, there exists a region of the frequency domain that is not mapped by the rotation. This missing volume in the frequency domain was named the "missing apple core" after its characteristic shape represented in Figure 7. Note that if the object would be rotating not only around the z-axis, but also around the y-axis, there would be no missing data anymore. In practice, the microscopic sample is usually embedded within a micropipette or a capillary [8,10,11] or is itself of cylindrical geometry [9], so that it is easy to both handle, and rotate the sample. However, this kind of geometry prevents a possible rotation along the second axis. Optical tweezers may be used to perform a rotation along two axes [START_REF] Kreysing | [END_REF], without mechanical contact with the sample, but have not yet, to our knowledge, been used in the framework of optical tomography, which is usually performed with only one rotation, which indeed motivated our work.

Simulations

In this section, the effects of the missing apple core on the reconstruction of ideal objects such as spheres, cylinders and membranes from the scattered fields recorded by sample rotation diffractive tomography are examined. From the shape of the apple core represented in Figure 7 where high frequencies are missing along the rotation axis, it can be inferred that the effects of the missing apple core should translate into blurring around image borders that are perpendicular to the axis of rotation.

A quantitative investigation into the effects of the missing apple core was conducted in the following way. Perfect three-dimensional objects were modeled and their three-dimensional Fourier transforms computed using Matlab standard functions. Then, the effect of the limited N A of the microtomography setup was simulated. This was done by applying a spherical low-pass filter on the computed object frequencies that filters out the high frequencies not collected by the microscope objective (only low frequencies within a sphere are used). Next, the missing apple core region of the frequency domain was removed from the computed object frequencies. Finally the three-dimensional inverse Fourier transform of the remaining object frequencies after low-pass filtering and missing apple core removal was computed.

The mapping in the frequency domain of the object frequencies requires the knowledge of the radius of the Ewald sphere and the effective numerical aperture of the instrument which depend on the detailed of the experi- The w-axis is the symmetry axis of the apple core and the z-axis is the axis of rotation of the object as shown in Figure 5.

mental setup arrangement. Here, we assumed that light collection by the instrument is limited by N A only as shown in Figure 5 and we chose N A = 1 for convenience. Doing so, we compute an extreme case where the relative importance of the missing apple core is maximal. Indeed, for lower numerical aperture, the relative volume of the missing apple core to the volume of effectively recorded frequencies diminishes, thus reducing the apple core effect on the specimen reconstruction quality.

An N A of 1 (in air) means that for each direction of illumination, the spherical cap collected on the image sensor is half of the corresponding σ Ewald sphere (in our case, the spherical caps of the σ spheres of Figure 3 that verify k i • k d ≥ 0). Under this circumstance, it is clear from Figure 3 that the cut-off frequency of the low pass filter is √ 2R Ewald . Consequently the maximum of the simulated object frequencies should be set to be at least √ 2R Ewald so as to map all frequencies collected by the simulated instrument.

In the following, simulations have been conducted using a matrix with size of 301 × 301 × 301 pixels (a compromise between computation time and reconstruction quality) and our cut-off frequency of √ 2R Ewald was set to 150 pixels as shown in Figure 7. The matrix values used to define the object and the background were set to 1 and 0, respectively. For all simulations, the z-axis was the rotation axis of the object and the w-axis the axis of revolution of the apple core in the frequency domain.

The effect of the missing apple core was examined on three different kinds of object shapes, namely solid spheres, solid cylinders and hollow spheres depicting membrane-like objects like vesicles or cell membranes. The geometry of the sphere provides border perpendicular to each possible direction in the object space, so that the comparison between the effect of the threedimensional low-pass filter and the effect of the missing apple core is made possible for all directions. Two cylin- ders with their axes of revolution perpendicular and identical with the axis of rotation were selected to observe the effect of the missing apple core on large surfaces perpendicular to the axis of rotation. Finally an empty sphere mimicking membrane objects such as cells was simulated.

Simulation results for a solid sphere are reported in Figure 8. The original sphere had a radius of 100 pixels and the sphere frequencies after applying the low-pass filter are shown in Figure 8(a). The reconstruction of the solid sphere from the frequencies of Figure 8(a) is shown in Figure 8(b-d). This reconstruction represents the best possible result for microtomography limited by the N A only. Figure 8(e) shows the frequencies of the same object after removing the apple core region in the frequency domain and Figure 8(f-h) the corresponding reconstruction by inverse Fourier transform. In contrast to the isotropic blurring effect of the low-pass filter, the effect of the missing apple core was chiefly observed on the two sphere tops perpendicular to the axis of rotation as evidenced by the comparison of Figure 8(c) and 8(g).

In addition to the border blurring, artefacts appeared in the background near the sphere tops perpendicular to the axis of rotation. A close look in Figure 8(d,h) at the region near a sphere top perpendicular to the rotation axis revealed that if the low-pass filter changed the background level of the reconstructed object, the missing apple core generated grey disks that did not belong to the original sphere.

Simulation results for the solid cylinders are shown in Figure 9. The two cylinders had a radius of 75 pixels and a height of 100 pixels. The axis of symmetry of the first cylinder shown in Figure 9(a,b) coincides with the rotation axis and the axis of the second cylinder shown in Figure 9(c,d) is perpendicular to the axis of rotation. The original cylinders are shown on the left side of Figure 9 and the reconstructed cylinders on the right side. Blurring of the cylinder borders perpendicular to the axis of rotation is observed in the zooms of Figure 9(c,d). The extent of border blurring is larger when the cylinder symmetry axis coincides with the rotation axis because in this case the surface border perpendicular to the rotation axis possesses high frequencies along the rotation axis that are filtered out due to the missing apple core.

Simulation results for membranes that have a similar structure with biological samples are shown in Figure 10. Simulations were performed on two types of membranes, namely spherical and cylindrical. The spherical membrane had a membrane thickness of two pixels defined by the 99 and 100 pixels. The cylindrical membrane consisted of two cylinders forming a membrane with thickness of 2 pixels. The reconstructed membranes of Figure 10(c,d) show that the blurring of the borders perpendicular to the rotation axis is more pronounced than in the case of the solid objects of Figures 8 and9. Particularly the surfaces perpendicular to the axis of rotation of the cylinder membrane are poorly defined. Moreover, the reconstructed backgrounds exhibit variations that did not belong to the original objects.

Finally, the effect of the object size on the reconstruction of spherical membrane-like objects is investigated by fixing the illumination light wavelength at 633 nm and representing different object sizes by the same number of pixels. The physical radius of the Ewald sphere being defined by the wavelength, it is therefore kept constant, but numerically represented by a different number of pixels in the frequency domain. Figure 11 shows the simulation results for the object sizes of 44, 31.5, 9.5 and 3 µm, corresponding to the Ewald sphere radii of 105, 71, 21 and 7 pixels. For large sizes (Fig. 11(a-b)), the relative influence of the missing frequencies decreases resulting in very good reconstructions. For small sizes (Fig. 11(cd)), however, an elongation of the reconstructed object along the z-axis can be observed. Note that this elongation becomes more and more apparent as the object size is decreased. This effect is very similar to the ef- fect of the missing-cone in transmission microscopy or fluorescence microscopy, which influence becomes more and more visible for smaller object, and which precludes an efficient specimen reconstruction, even after deconvolution [15]. The main difference is that in tomography with specimen rotation, the axis of lower quality image reconstruction corresponds to the physical rotation axis of the specimen, while in conventional microscopy, the optical axis is the direction of worst imaging conditions. Note however that the observed elongation along the rotation axis in diffractive tomography with sample rotation is less pronounced than that observed in standard transmission microscopy or in fluorescence microscopy along the optical axis [15,16]. This can be easily understood if one considers the so-called missing-cone in transmission or fluorescence microscopy [17]: while high frequencies are captured along lateral axes, no frequencies are measured along the optical axis, and even the maximum thickness of the captured frequency support along this direction is several times smaller than its lateral extension. Note that this frequency support has the same shape in diffractive tomography with variable illumination [1,2,3]. On the contrary, in diffractive tomography with sample rotation, the relative volume of the missing apple core compared to the captured frequency support is rather small (see Fig. 7), which explains the good quality of the simulated reconstructions, even if, strictly speaking, the obtained images do not exhibit isotropic properties.

Conclusion

The mapping of the observed object frequencies in diffraction tomography using coherent light with sample rotation along one axis does not allow for a complete mapping of the frequency along the axis of rotation due to the finite Ewald sphere radius. Under the first-order Born approximation, the projection of the diffracted waves in the frequency space onto the set of sphere caps covered by the sample rotation features a missing part that has a characteristic shape resembling that of an apple core. The main effects of this missing apple core, as revealed by numerical reconstructions of ideal objects, is the presence of a more important blur of the reconstructed object borders perpendicular to the axis of rotation, a slight modification of the background close to these borders, and a slight elongation along the rotation axis. The later effect is similar to the elongation observed in transmission microscopy along the optical axis, but less noticeable. This elongation effect is found more pronounced for objects having sizes of the order of the wavelength of the illumination light. We also noticed that the effects were more pronounced for membrane-type objects than for solid objects.

Figure 1 :

 1 Figure 1: Schematic of the Fourier slice theorem showing the relation between the Fourier transform of the projected data of the object f (x, y) and the Fourier transform of the same object. The Fourier transform values of the projected data are distributed along a straight radial line.

Figure 2 :

 2 Figure 2: Definition of the propagation vector of the scattered light from a medium of volume V .

Figure 3 :

 3 Figure3: Two-dimensional representation of the Ewald limiting sphere Σ L and the support of the Ewald sphere Σ 0 , the radius of which is the wavenumber k of the incident light. Σ 0 represents all possible directions of incidence and Σ L is the largest frequency domain covered by the scattered vectors when all possible incidence directions are mapped. A σ Ewald's sphere represents all possible scattered directions for one illumination direction. Note that a transmission microscope collects at best half of the σ spheres.

Figure 4 :

 4 Figure 4: Schematic of the Fourier diffraction theorem showing the relation between the Fourier transform of the projected data of the object f (x, y) and the Fourier transform of the same object. In contrast to the non-diffracting case of Figure 1, the Fourier transform values of the projected data are distributed along an arc of a circle. Note that the theorem is valid under the first-order Born approximation.

Figure 5 :

 5 Figure 5: Mapping representation of the object frequencies in the case of scattered light collected in transmission. (a) The object scattered frequencies collected through the objective numerical aperture for an incident plane wave of wave vector k i lie on the surface of a spherical cap. (b) The Fourier transform of the object scattering potential are distributed over the surface of a spherical cap, the top of which coincides with the frequency origin.

Figure 6 :

 6 Figure 6: Representation of the object frequency mapping obtained by object rotation along the z-axis. (a) Spherical caps of the object scattering frequencies mapped for θ = 0 and θ = 0. The extended support of the mapped frequencies is obtained by integrating over a large number of rotation angles. Slices of the extended supports are shown at (b) w = 0 and (c) w = 0. The regions of the frequency domain covered by rotating the object are shown in light grey; note the formation of a missing disk for w = 0, the surface of which increases with the distance from the frequency origin. These missing frequencies form a volume that resembles that of an apple core.

Figure 7 :

 7 Figure 7: Representation of the missing apple core in the frequency domain as obtained in the case of an object rotation along the z-axis and measurements of forward scattered fields with N A = 1. (a) Slice crossing the w-axis of the three-dimensional object frequencies. The missing frequencies are shown in black and the cut-off frequency of the low-pass filter is indicated by a white circle. (b) Three-dimensional representation of the missing frequencies forming a volume similar in shape with that of an apple core.The w-axis is the symmetry axis of the apple core and the z-axis is the axis of rotation of the object as shown in Figure5.

Figure 8 :

 8 Figure 8: Simulated effects of the missing apple core on the reconstruction of a sphere. (a) Slice in the uw-plane of the complete object frequencies, that is, without the missing apple core but after applying the low pass filter. Slices in the (b) xy-plane and (c) xz-plane of the reconstructed sphere obtained by inverse Fourier transform of the sphere frequencies as shown in figure (a). (d) Slice of the reconstructed sphere taken at constant z at one of the extremities of the sphere. (e) Slice in the uw-plane of the incomplete object frequencies, that is, with the missing apple core and after applying the low pass filter. Slice in the (f) xy-plane and (g) xz-plane of the reconstructed sphere obtained by inverse Fourier transform of the sphere frequencies as shown in figure (e). The inset of figure (g) shows the sphere extremity using an enhanced contrast. Note the deformations in the reconstructed sphere from the incomplete frequency information. Particularly noticeable are deformations in the z-direction corresponding to the rotation axis of the object which creates the missing apple core along the w-axis in the frequency domain. (h) Slice taken at constant z corresponding to the extremity of the sphere shows a ring pattern generated by the missing spatial frequencies of the apple core. The object edges perpendicular to the z-axis are the most blurred.

Figure 9 :

 9 Figure 9: Simulated effects of the missing apple core on the reconstruction of cylinders with main axis (a,b) parallel and (c,d) perpendicular to the z-axis of rotation. The object frequencies comprised in the apple core of figure 7 were removed and then the objects were computed by inverse Fourier transform. Three-dimensional representations of the original objects are shown in figure (a) and (c). Slices in the xz-plane of the reconstructed cylinders from their object frequencies with the missing apple core are shown in figure (b) and (d). Note the deformation along the z-axis in figure (b) and (d).

Figure 10 :

 10 Figure 10: Simulated effects of the missing apple core on the reconstruction of membrane-type objects having (a,b) a spherical shape and (c,d) a cylindrical shape. The inner and outer of the membranes have the same properties. The figures (a,c) show slices crossing the symmetry axis of the original objects and the figures (c,d) show the same slices for the reconstructed objects. The reconstruction is done by inverse Fourier of the original object frequencies with a missing apple core and after application of a low pass filter.

Figure 11 :

 11 Figure 11: Simulated effects of the elongation due to the missing apple core on the reconstruction of a membrane-type object having a spherical shape with a membrane thickness corresponding to 10 pixels. The inner and outer of the membrane have the same properties. Different membrane sizes of 44, 31.5, 9.5 and 3 µm were used for figures (a), (b), (c) and (d), respectively. The reconstruction is obtained by inverse Fourier of the original object frequencies with a missing apple core and after application of a low pass filter. The figures (a,b,c,d) show slices of the reconstructed object in a plane containing the rotation axis z. The reconstructed membrane object shows an elongation along the z-axis, the effect being pronounced for small objects.


Iraklis Leontiadis
email: leontiad@eurecom.fr

Constantinos Delakouridis

Leonidas Kazatzopoulos

Giannis F Marias
email: marias@aueb.gr

ANOSIP: Anonymizing the SIP Protocol

Keywords: C .2.2 [Network Protocols]: Applications, K.4.1 [Public Policy issues]: Privacy Design, Experimentation, Performance, Measurement, Security Anonymity, Privacy, SIP

Enhancing anonymity in the Session Initiation Protocol (SIP) is much more than sealing participants' identities. It requires methods to unlink the communication parties and relax their proximity identification. These requirements should be fulfilled under several prerequisites, such as time limitation for session establishment, involvement of several functional entities for session management, inter-domain communications and support of streaming services when the session is established. In this paper we propose the usage of a privacy enhancement framework, called Mist, as a solution to the anonymity issue in SIP. For achieving anonymity, the original Mist architecture was modified to be adapted in the SIP framework. We evaluate the adapted Mist framework to SIP and measure how efficiently it supports anonymity features.

Introduction

Every day new malicious actions on internet activity, available by exploiting the vulnerabilities of the end-systems or network protocols, are reported. The need to protect the personal freedom and privacy, achieve digital dignity, and, moreover, defend confidentially in the societal space, as well as in human relationships, is becoming more essential than ever. In this scope, privacy and anonymity over the Internet gained substantial consideration in the technical, procedural and legal domain. For every new service that is lunched and massively adopted in the Internet, privacy concerns arise immediately. The same applies for VoIP services, and especially for SIP which currently prevails in this new market. There are various reasons why an end-user wishes to maintain its anonymity when communicating using SIP. Firstly, a caller might wishes to conceal its identity at the receiver's phone. On the other hand, a callee might want to be unlinkable from her personal preferences and direct marketing campaigns. In its original specification, SIP supports anonymity, since the originator of a call could remain "Anonymous" to the callee, and for that reason default values are used when the user agent initiates a call. This feature supports caller anonymity against the callee, but not to the entire set of SIP realms, since practically the user agent server of the serving domain requires strong authentication of the caller. Additionally, using tunneling techniques, and especially end-to-end S/MIME encryption, selective anonymity can be supported. This option enables caller's privacy within the set of intermediate relays and the serving domains, if authentication is not required, but not against the callee. Finally, if network analysis tools are used in the network, then a malicious third party can track the locations, using the address-of-record fields, of the caller. In such a case it could link address-of-records to physical locations, using data mining techniques, and finally with people, since there would be only a few people that make phone calls from particular residential addresses during a day. So, the question is whether total anonymity is possible in SIP, and how this could be applied to shield the identity. In this paper we propose a new scheme for SIP protocol to enforce anonymity and privacy.

Our Contributions:

In this paper we adopt MIST anonymity architecture to SIP protocol. We evaluate our architecture under an attack scenario and calculate the anonymity based on the undermentioned architecture by obfuscating the identity and the location of the SIP client through tree architecture of MIST. We evaluate Organization. The rest of the paper is organized as follows. Section 2 briefly describes the motivations of the paper. Section 3 reviews anonymity architectures. Section 4 presents the Anosip architecture. Sections 5 describes the attacking scenario whereby we measure the anonymity. Section 6 presents the results from the simulation of Anosip and section 7 concludes the paper.

Motivation

To apply anonymity in SIP we should discriminate roles and actions. Even if various servers, intermediate proxies, and end-entities contribute on SIP, the set of actions, or service building blocks, that they contribute is actually restricted. Subscription, registration, location (or redirection), call forwarding (or routing), call setup initiation-termination, and, optionally, authentication. This set of actions normally is performed by the entities belonging into two district sets of service providers: those of the callee and those of the caller. Thus, if we consider a model were an attacker wishes to reveal the identity of the calling parties, we can then define four legitimate parties in a SIP session: the caller, the callee, the service provider of the caller, and the service provider of the callee. In this direction we can define some privacy protection classes: Except the first privacy class, the other three are disjoint, and may coexist. In next sections we will see how the existing SIP anonymity proposal and specifications deal with these four classes. We should mention here that the potential attacker might be one of the service providers or the callee, depending on the privacy protection class. For instance, the attacker might be a callee that aims to expose the name of any caller who wishes not to display her name to the peer party. To support these privacy classes, any anonymity architecture should make an attacker unable to distinguish between the occasions when a callee transmits or receives a SIP message and the occasions when she doesn't. Additionally, it should take into account some characteristic of the SIP, such as:

1. the SIP messages should not be delayed 2. the sequence of SIP messages should not be violated 3. the traverse path of the SIP messages might be pre-determined, according to service agreements between local, regional and national operators Moreover, any anonymity architecture should protect the physical location of the end-user. No one into system, neither the system itself, should know from which point a user is connected. Even if the relation of the transmitted or received SIP messages with a particular callee is not possible, the anonymity system should prevent attackers from linking the messages with physical locations. This will avoid the provable exposed conditions, whereas an attacker can prove the identity of the sender to others. For instance consider a user who decided to use anonymous SIP features. The UAC uses a meaningless URI, such as sip:thisis@anonymous.invalid [START_REF] Reed | Anonymous connections and onion routing[END_REF]. If this meaningless URI is always used for this particular user, then it is possible to intercept SIP traffic, and connect this URI with different "Addresses-of-Record" (AoR). Then, using commercial or open source tools the attacker will link these AoRs with physical locations, and then with end-users' identities.

Anonymity architectures

To enhance or provide privacy in the internet services several privacy enhancement technologies (PET) have been proposed. Chaum's Mixes [START_REF] Chaum | Untraceable electronic mail, return addresses, and digital pseudonyms[END_REF], Stop-and-Go Mixes and MixeNets [START_REF] Kesdogan | Stop-and-go MIXes Providing Probabilistic Security in an Open System[END_REF],

Crowds [START_REF] Reiter | Crowds: anonymity for web transactions[END_REF], Hordes [START_REF] Levine | Hordes: A multicast-based protocol for anonymity[END_REF], Onion Routing [START_REF] Reed | Anonymous connections and onion routing[END_REF], and Mist [START_REF] Al-Muhtadi | Routing Through the Mist: Privacy Preserving Communication in Ubiquitous Computing Environments[END_REF] are some of the preserving techniques. Tor [START_REF]Mimic Tex with MS Word®: Combining WYSIWYG with Post-Processing unpublished manuscript[END_REF] has gained the interest of many researchers as it is becoming a standard architectur for anonymous web browsing. The idea behind Tor is based in Onion routing. A user selects a number of realaying nodes which encypt and send the user data to the final destination obfuscating the end-to-end path of the transmission.

For the most of these PET approaches, applied mainly for email and asynchronous web communications, there are some deployment difficulties when adapted to SIP. Latency is an issue, since SIP a call setup request, e.g., an INVITE, requires immediate response. This feature is not supported directly. Additionally, these PETs do not support bidirectional communications, excluding the onion routing, a characteristic that is essential for SIP. Moreover, anonymity should be semantically supported. In that sense, the PET mechanism should support unlinkability of location where calls are initiated (or terminated) from SIP URIs, or physical addresses (e.g., IP addresses). The most of the previously mentioned PETs support anonymity in transit, and do not have means to support unlink-ability.

A promising privacy system that overcomes these drawbacks is the Mist. The Mist [START_REF] Dıaz | Designing Privacy EnhancingTechnologies[END_REF] handles the problem of routing a message through a network while keeping the sender's location private from intermediate routers, the receiver and potential eavesdroppers. The system consists of a number of routers, called Mist routers, ordered in a hierarchical structure. According to Mist, special routers, called "Portals", are aware of the user's location, without knowing the corresponding identity, whilst "Lighthouse" routers are aware of the user's identity without knowing her exact location.The "Lighthouse" routers, hereafter will be referenced to as LIG.

Anosip Architecture

SIP protocol specification suggests that the Home Server (Registrar, Redirect, or Proxy server) keeps knowledge of both user's ID and current location. Our goal is to distribute this knowledge to more than one entity. If though, it will be difficult for eavesdroppers to inference user's location information. Since a SIP user registers to Home Server (using her ID) and this server is the one that all SIP entities refer to in order to locate the registered user, we could consider that Home server corresponds to user's Mist LIG. Furthermore, we define as Mist Portals all the Remote SIP servers that user is connected to in order to establish communication through SIP. In general, we presume that each

Figure 1. Establishment of a Mist circuit

SIP server (hereafter called MSIP Server) can act as Mist LIG (for the users that have been registered to it), Portal (for the users that at some point can connect to the SIP network) or Mist router. To enforce Mist to support anonymity in SIP, small modifications are required in SIP. Currently, SIP location service is an LDAP directory that keeps the current physical position of registered users. However by applying Mist, the location of the users is no longer known to Home Server. Instead, the latter will have knowledge of a way to route packets to the user. In terms of Mist, the Mist user's binding table can be used to replace the location service. This table keeps routing information about the Mist communication circuits with each user. Furthermore, we consider that:

1. A Mist Hierarchy has been applied. Mist Hierarchy considers that all Mist servers are ordered in a treebased hierarchical structure. However, to apply Mist routing in SIP, we have to alter this structure by adding connections between the siblings of each level of the tree. Thus, a MSIP server is able to forward packets apart from its ancestor, to its siblings. The reason for this modification is discussed later.

2. A PKI has been established, pairs of keys have been created, and the corresponding public-key certificates have been distributed to MSIP servers. Furthermore the authentic public keys are accessible from every MSIP Server. Additionally, each user holds a pair of keys, related only to the user's nick name (using e.g., anonymous certificates) and not real-life information.

Registration procedure

Suppose Alice has a WiFi connected laptop and place calls using SIP. When she triggers this service for the first time, her handset initializes SIP Registration routine and connects to the first available Registrar SIP server. During this registration phase Alice is prompted for personal information, nickname and password. Note that since she doesn't wish to reveal her real identity, she registers to the system hiding her personal information. However, she will use the nick name "Mother", so that her friends that know her nick name can call her. From a Mist point of view, the registrar SIP server considers to be her LIG. The LIG will be the point of contact for other SIP users in order to get in touch with her. Upon registering, the LIG sends a Mist notification to the Lookup Service to inform it that user "Mother" has been registered to this LIG.

Mist circuit establishment

Alice is visiting a friend on the other part of the city and wants to be reachable by SIP clients but not traceable. She connects to the first available SIP server. From the Mist point of view, this considers to be her Portal. Next step is to setup a Mist Circuit between Alice Portal and LIG. Note that the Portal, contrarily to the original Mist procedure, does not forward to Alice's laptop the list with all the available LIGs since, as we mentioned earlier, Alice's LIG is the SIP server where she was originally registered to (i.e. the home registrar server of the SIP protocol). Accordingly, her laptop encrypts a predefined message with the public key of the LIG and forwards it to the Portal. The latter routes this update packet to her LIG. Note that since Alice LIG is predefined, it is likely that this LIG is not an ancestor of her Portal. To ensure that the update packet will reach the LIG, regardless its position on the tree, the Mist Portals forward packets to their ancestors, as well as to their direct connected siblings. In more de-tails, if the MSIP server receives a packet from its predecessor, it forwards the packet to the ancestor and to the directly connected siblings. Otherwise, if it receives a packet from a sibling server it forwards the packet to the next sibling. Upon receiving the update packet, the LIG stores the Mist circuit information to the user binding table. At this point, the Mist circuit has been established. The LIG is able to forward packets to Alice (actually to "Mother") without knowing her exact location.

Sip session

Suppose that Bob wants to call Alice. Both users have established a Mist circuit with their corresponding LIGs. Bob is aware that Alice's nickname is "Mother". The call establishment procedure is as follows:

1 They both acknowledge, the SIP circuit is formed, and they have an established call.

Taking in account the untraceability of the packets routed through the Mist and the distribution of knowledge (i.e., Portals know "where", LIGs know "who") we can preserve the privacy of the location of the users. Furthermore, considering only users that are registered to the system using their nickname, and realistically assuming that the corresponding private keys have been The aforementioned technique assumes that the communicating parties have knowledge of each other (Bob knows that Alice's nickname is "Mother" and vice versa).A problem arises when the two parties have no prior knowledge. Therefore, we introduce the Trusted Third Party directory which is called "ID Directory". This directory stores tuples with the following format: <NickName A, ID A> Where ID A is the user's real name e.g. "Alice" and Nick-Name A is the nickname that the latter is using e.g "Mother". Should someone i.e. Alan wants to communicate with Alice for the first time, he presents to the ID Directory a authentication credentials in order to use the requested tuple. After validating user's credentials it will send to Alan the corresponding tuple for Alice. During ANOSIP communication establishment, Alice receives on step 6, an invitation from "Grandfather" which is Alan's nickname. Alice inquires the ID Directory for the tuple <"Grandfather","Alan"> using the aforementioned authentication procedure. Upon receiving the corresponding tuple, she decides whether or not to answer back to Alan.

Attacking scenario

Shannon [START_REF] Shannon | A Mathematical Theory of Communication[END_REF] introduced entropy as an information theoretic concept that provides a measure of the uncertainty of a random variable . Let X be a discrete random variable with probability mass function pi = Pr(X = i), where i represents any possible value that X may take with probability pi > 0. We denote by H(X) the entropy of a random variable, and by N the number of subjects in the anonymity set (i.e., Lighthouses, Portals and Routers). H(X) can be calclated as:

In our case, pi is the probability of SIP user i being linked to an identity and location (since knowledge of only the location or only the identity of the user is supported in MIST). Thus, our analysis is focused on the uncertainty of connecting a user associated with a particular attribute (i.e. identity) to a particular place (e.g. IP address). So an effective attack scenario is the one that some of the nodes m in the number in the network collude to associate identity and location. Obviously, N=P+R, where P and R is the number of Portals, and Routers in the Mist hierarchy re-spectively. A user ui is served by one Portal (Pi) and Rir Routers (vector Rr1, Rr2, … , Rrk), R≥r≥1. The pi probability is defined as:

where pf is the probability of a node to be controlled by an intruder.

This entropy definition was enhanced in [START_REF] Dıaz | Designing Privacy EnhancingTechnologies[END_REF] and the effective anonymity concept was introduced. When launching an attack against an information system, the attacker's goal is to evaluate, with high precision, the distribution of probabilities that link any distinguished subjects (e.g., user, process, transaction) to the particular item of interest (target). According to [START_REF] Shannon | A Mathematical Theory of Communication[END_REF] different subjects might illustrate higher or lower probability pi to link with the target, depending on the information obtained by the adversary using the attack, or actual relationships. So, if N is the total number of subjects which are linked by the adversary to the target with a non-zero probability (i.e., pi > 0, i = 1..N) then the effective anonymity set size is defined as the entropy H(X) of the distribution X of probabilities that link the subjects of the anonymity set to the target. In [START_REF] Dıaz | Designing Privacy EnhancingTechnologies[END_REF], the entropy is normalized to express a degree of anonymity in the scale 0, …, 1. The effective anonymity set size is maximized if all the N subjects are connected with equal probability (i.e., pi=1/N) to the target. This corresponds to the maximum entropy, denoted by HMax where HMax=log2(N). The amount of information gained by the adversary with an attack is the difference in the entropy before and after the attack, that is: HMax -H(X). The degree of anonymity d is defined as the normalized value of this difference: Figure 3 depicts the anonymity degree as previously described. We randomly choose the value of the pf probability. It is obvious that the more the colluding portals along with the higher pf the less the anonymity degree. As such there is a trade-off between the number of the intermediate routers and the degree of anonymity.

Figure 3. Anonymity degree

p i = N -R- m p * p f N d= 1- H M -H ( x) H M = H ( X ) H M H ( X )= ∑ p i * log ( p i)

Simulation results

Once the mist circuit is created between the lighthouse and the user then the lighthouse operates as a representative of the user. This correlation between the Lighthouse and a user should be saved in each domain to enable questions from other Lighthouses to be answered from Lighthouse located in the domain of each user. To implement the location service we have used the database MySql 5.0.67. The Mist entities that communicate with the location service are the Lighthouses. Using the "Hibernate" library we have created an interface for the lighthouse to record and query the location service. The relational table used in the form <Lighthouse, User>. The "hibernate" library aims to link the objects created in an object-oriented programming language (Java) to the tables of a relational database.

For the efficiency of the architecture we have used a traffic generator for SIP messages, the SIPP v 3.1 [START_REF] Sipp | [END_REF]. In this scenario (Figure 4) we have assumed the following category of SIP chats: Children equipped with mobile phones are communicating with their parents or their supervisors to indicate their location for safety reasons. This is a real user scenario in schools trips. To reduce the cost of communication the children are connected in a wireless-access point and through SIP clients they talk with their supervisors. In such situations 30secs of conversation are sufficient to indicate the real location of the children or to mention an emergency situation as fire or earthquake. The SIP traffic generator sends registration requests to SIP registrar server and we are interested to see our response times for successful registrations. Once a sip user is registered through ANOISIP she is able to receive calls and make calls as well. We consider of crucial importance the overall registration time. We assume that potential users wouldn't use the VOIP service if the registration time overdraws a reasonable time threshold. As such for 30 seconds we measured the overall response times for the successful registration responses whose code is 200 from the registrar server. To implement the registrar and the proxies servers we used the SIP servlet container [START_REF]Sip Servlets[END_REF] inside the Tomcat 6.0.14 web application server. SIP servlets contain the SIP stack. In Figure 5 we can see the response times for successful registrations for the all the registration requests. We note that the first responses come quickly and then they are slow enough (2.5-3 secs). At the vertical axis there is the time in ms and at the horizontal is the time period for 30seconds that the experiment was running.

Summary and future directions

In this paper we have presented ANOSIP, a privacy enhancement framework for the SIP protocol. We have taken into account a specific privacy threat: the correlation of a session or a receiver with a specific caller. We have adopted in ANOSIP the Mist privacy framework, proposing significant enhancements and modifications to overcome weaknesses and strength the anonymity of the Mist users. We have analyzed ANOSIP by measuring the degree of anonymity based on different attacking scenarios. Finally, some preliminary simulation results show that Mist does not introduce significant delay overhead during operation in special use case scenarios whereby the caller seeks to learn the location of the callee in emergency cases as fires, earthquakes, children awareness by their supervisors or parents, in which the communication overall time is around 30seconds. Our future directions include the simulation of more complex calls with a SIP traffic generator and the deployment of ANOSIP to planetlab [12] as a VOIP infrastructure.

Figure 2 :

 2 Figure 2: Applying Mist to SIP issued based on this nickname, anonymous communications are actually supported.The aforementioned technique assumes that the communicating parties have knowledge of each other (Bob knows that Alice's nickname is "Mother" and vice versa).A problem arises when the two parties have no prior knowledge. Therefore, we introduce the Trusted Third Party directory which is called "ID Directory". This directory stores tuples with the following format:

Figure 5 .Figure 6 .

 56 Figure 5. Registration response times

Table 1 Classified number of responses

 1 As table 1 illustrates, the majority of successful responses on SIP Invite (i.e., OK method) are less than 40ms. That indicates an negligible extra overhead to the registration procedure through MIST.

	Response of 200 calls	#number of responses
	0ms-10ms	0
	10ms-20ms	0
	20ms-30ms	58
	30ms-40ms	39

Acknowledgments

Most of the work has been done while Iraklis Leontiadis was at Athens University of Economics and Business in Mobile Multimedia laboratory. The authors thank the comments of the anonymoys referees.