L Gantel

A Khiar

B Miramond

A Benkhelifa

F Lemonnier

L Kessal

Dataflow Programming Model For Reconfigurable Computing

Keywords: reconfigurable computing, dataflow programming, hardware actors, real-time operating systems, multiprocessor architectures, FPGA, image processing

This paper addresses the problem of image processing algorithms implementation onto dynamically and reconfigurable architectures. Today, these Systems-on-Chip (SoC), offer the possibility to implement several heterogeneous processing elements in a single chip. It means several processors, few hardware accelerators as well as communication mediums between all these components. Applications for this kind of platform are described with software threads, running on processors, and specific hardware accelerators, running on hardware partitions. This paper focuses on the complex problem of communication management between software and hardware actors for dataflow oriented processing, and proposes solutions to leverage this issue.

I. INTRODUCTION

Heterogeneous Systems-on-Chip (HSoC) platforms provide good performances but are often difficult to program. For programming efficiency in an industrial context, it would be better if the developer can describe its application in a single language, independently from its future mapping. In this way, we need a homogeneous API (Application Programmable Interface) and specific operating system services to manage hardware accelerators with so much flexibility as what is done with software threads. Using Dynamically and Partial Reconfiguration (DPR) capabilities of the latest Xilinx c FPGAs, and the future Altera c FPGAs, we pose the problem in the context of dynamic hardware threads.

The needed homogeneous API is defined in the existing literature as middleware. The most popular definition of a middleware is the following: "The middleware is the software that assists an application to interact or communicate with other applications, networks, hardware, and/or operating systems. This software assists programmers by relieving them of complex connections needed in a distributed system. It provides tools for improving quality of service (QoS), security, message passing, directory services, etc. that can be visible to the user" [START_REF] Bishop | A survey of middleware[END_REF]. Middleware provides a higher-level abstraction layer for programmers than API provided by the operating system, such as sockets.

It reduces significantly the work of application programmers by relieving them of tedious and error-prone programming. Middleware is designed to mask some of the kinds of heterogeneity that programmers of distributed systems must deal with [START_REF] Muller | A flexible operating system for dynamic applications[END_REF]. It always masks heterogeneity of networks and hardware processing units.

We are interested in the FOSFOR project, by providing communications on the platform, whose components are heterogeneous with dynamic hardware. This is why we set up a communication protocol between these components. It is important to note that, to have a transparent, flexible and scalable platform, its global communication medium must be defined and take into account this heterogeneity.

In this article, we propose to follow up the properties of a data-flow model of computation dedicated to the heterogeneous Systems-on-Chip from the actor-level down to the thread implementation. An overview of state of the art is given in section II. Section III details the design flow used to mitigate the complexity of the platform. Section IV describes the hardware actor model specified to be implemented at a lower level. The basis of the communication framework are explained in Section V. Section VI is about first experiments and results obtained with a real application.

II. RELATED WORK

Embedded systems interact with the physical world. Most of these systems include heterogeneous designs that are specific to an application. Conceptually the distinction between the software and hardware implementations, in a computation point of view, is relative to their degree of concurrency and their performance limitations. The issue lies in the manner to identify the appropriate abstraction for representing the global system.

Among the dataflow design approaches, the Actor-oriented paradigm offers the abstraction to rise above the heterogeneity. This approach orthogonalizes component definition and component composition. A tool that refines heterogeneous actororiented models into software-based design and hardwarebased program-level description is proposed in [START_REF] Lee | Actor-oriented design of embedded hardware and software systems[END_REF].

Several other data-flow oriented models of computation exist to design heterogeneous systems, but there is a lack in the partitioning of the application into a reconfigurable platform. We propose in this paper to reduce the gap between the highlevel properties of the input specification and the final implementation onto a partially and dynamically reconfigurable architecture by defining the notion of reconfigurable software and hardware actors.

Verdoscia et. al. [START_REF] Verdoscia | Actor hardware design for static dataflow model[END_REF] already introduced a model of hardware actor, defined in a dataflow graph model, and implemented in hardware. Each actor was described as a Functional Unit (FU), executing simple operations such as additions, multiplications, loops and conditionnal instructions. As in the upper level of its model, the execution of this FU was conditioned by two input tokens and fired one output token. FUs are organized in clusters whose communication is based on Message Passing through shared memories. However, FUs inside the same cluster are connected together with a crossbar to improve latency.

A model of computation for the reconfigurable computing involves the definition of a reconfigurable dynamic hardware actor. By reconfigurable, it means a thread, implemented in hardware, which has a similar behaviour to a software thread.

To attack this issue, some operating systems which are able to manage both software threads and hardware accelerators have been developed. This is the case of BORPH [START_REF] So | Improving usability of fpga-based reconfigurable computers through operating system support[END_REF], a Linux based operating system. It offers kernel drivers to control the execution of hardware accelerators. Santambrogio et. al [START_REF] Rana | Partial dynamic reconfiguration in a multifpga clustered architecture based on linux[END_REF] also present a Linux driver to control ICAP port of the FPGA. Thus they can dynamically reconfigure hardware accelerators by writing commands in well-known IOCTL registers.

Much complex accelerators have then been developed, such as Hybrid Thread [START_REF] Anderson | Supporting high level language semantics within hardware resident threads[END_REF]. In this article, the authors define a model of POSIX compliant hardware thread, capable of processing operating system calls through a shared memory, as software thread do. In the same way, ReconOS [START_REF] Lubbers | A portable abstraction layer for hardware threads[END_REF] authors present their own model, which achieves system calls via an API composed of VHDL procedures. In both cases, thread behaviour is described by a finite state machine for thread state execution, and the system calls are processed by a software proxy thread, running on a distant processor.

The drawback of this approach is that it leads to important time overheads. So Hybrid Thread authors realized a hardware implementation of the synchronization and scheduler services in order to lighten processor load [START_REF] Agron | Hardware microkernels for heterogeneous manycore systems[END_REF]. This solution was also experimented in [START_REF] Nordstrom | Application specific real-time microkernel in hardware[END_REF] where µC/OS-II was extended with hardware implementation of few services. At the expanse of some hardware resources, this can lead to more efficient platforms and takes advantage of the FPGA parallelism capacities.

When programming heterogeneous platforms, differencies between hardware and software threads have to be hidden, so a virtual layer has to be added. DNA Operating System [START_REF] Guerin | A system framework for the design of embedded software targeting heterogeneous multi-core socs[END_REF] proposed a component-based system framework. Components are described to manage hardware dependent issues such as endianness, multiprocessor management, memory allocation, synchronizations and exceptions, or task context management.

The proposed interface has been developed in order to provide homogeneous interface for all applications. Maejima et al. [START_REF] Nojiri | Domain partitioning technology for embedded multicore processors[END_REF] presented a hardware module which permits segregation between critical and non-critical services to make application safer. Petrot et. al [START_REF] Senouci | Fast prototyping of posix based applications on a multiprocessor soc architecture: "hardware-dependent software oriented approach[END_REF] addressed the same issue and proposed a POSIX API running on top of the Mutek operating system. This layer called Hardware dependent Software offers a homogeneous API for all the processing elements in the platform.

III. DATA FLOW PROGRAMMING MODEL FOR RECONFIGURABLE COMPUTING

A. Design flow

Today, embedded systems face increasingly higher performance requirements. Deeply pipelined processor architectures are being employed to meet desired system performances and system architects critically need modeling techniques to rapidly design the required platform. So, we propose to reduce the gap between the initial system specification and the final implementation, especially when targeting dynamically reconfigurable architectures. The main idea is to conserve the semantic of the components manipulated at high-level when refining the model till the hardware level. The concept, that already exists in the pure software domain with middleware approaches, has been extended to also consider hardware components.

Thus, the management of reconfigurable architectures is not limited to a specific technical solution anymore but is considered as a whole from the top to the bottom. A specific abstraction layer is developed (a hardware and software middleware) in relation to the semantic of the high-level components. This layer helps to map the high-level interactions between the actors of a specific application onto the abstracted platform. It also facilitates rapid exploration of candidate architectures under given design constraints such as area, clock frequency, power, and performance. Finally, it allows to foresee the future automatic generation of actor codes.

As illustrated in Fig. 1, we consider, from high level, a coherent and interoperable vision of communicating actors. This abstraction of communications facilitates the number of possible refinements into a subsequent abstraction layer (Programs) in the design flow.

To achieve this goal, the semantic of the managed components is based on the Synchronous DataFlow (SDF) model of computation (MoC) [START_REF] Lee | Synchronous data flow[END_REF]. Actors description is made from the standard graphical language UML (Unified Modeling Language) and their interfaces are described using IDL3 (Interface Language Description).

At the higher level we represent each block of the application that performs a specific task by an actor which, receives and sends data through virtual channels. Those actors share the same API of the global virtual platform.

B. Communication semantic

We want to virtualize the communications into a distributed heterogeneous embedded Multiprocessor System-on-Chip (MPSoC) platform containing reconfigurable hardware computing units. We propose a unified management of the communication, implemented both in software and in hardware, that provides the designer a single programming interface, accessible from the abstract actor layer. The global system is then controlled in a distributed manner by several communication managers implemented on each execution unit: processors and hardware accelerators (see section IV for more details).

Communication can be respectively homogeneous or heterogeneous. The first type is related to communication between two actors implemented simultaneously in the hardware domain (Hw / Hw) or in the software domain (Sw / Sw). The second type concerns communication between two actors implemented separately in two different execution domains: (Hw / Sw) and (Sw / Hw).

To ensure synchronization and exchange between the elements of a platform, two types of transfer are needed (Fig. 2): i) data exchange : each time a calculation block finishes its processing on the input data, this data can be passed to the next block for another type of calculation according to the principle of synchronous dataflow transfer. ii) state coherency : control information should be exchanged between the communication managers (see section V) in order to maintain a permanent consistency of the actors location and states, even during reconfiguration.

IV. RELOCATABLE HARDWARE ACTOR

A. Target architecture

The FOSFOR project [START_REF] Muller | A flexible operating system for dynamic applications[END_REF] (Flexible Operating System FOr Reconfigurable platform), aims to define a new kind of execution platform. This platform (Fig. 3) targets heterogeneous applications in the sense that threads could be either software (running on one of the processors), or hardware (running as an accelerator in a partition of the FPGA). At this level, the communication between the actor and the rest of the system is managed by using a system call paradigm. An actor can then be associated with the notion of Thread.

In the context of this project, hardware threads are managed by a hardware operating system (Flexible HwOS). It takes advantage of the DPR to schedule hardware threads on the available partitions, and implements similar services in hardware to those offered by the software operating system. Existing services include thread management, semaphore counters and mailboxes. The flexible HwOS allows hardware threads to process fast system calls without the need to pass through a software proxy thread [START_REF] Lubbers | A portable abstraction layer for hardware threads[END_REF]. Software threads are managed by the RTEMS operating system (OS) [START_REF]Rtems[END_REF]. This OS allows to abstract heterogeneity using its MultiProcessor Communication Interface (MPCI). Starting from this point, FOSFOR also implements this interface and permits hardware threads to access to any services in the system, both software and hardware, in a transparent way. Moreover, FOSFOR provides virtual channel services which abstract inter-thread communication and memory management (see Section V).

B. The generic hardware actor

A hardware actor has been defined to abstract dynamic reconfiguration provided, for instance, in the Xilinx c FPGAs. Thus, it is composed of two main parts : a static part which contains all the interface with the rest of the system, and a dynamic part, specific to the actor which contains the Finite State Machine (FSM) controlling its execution, its accelerator and its private memory (Fig. 4). The static part provides an interface to communicate with the operating system (OS Interface). It is composed of a standard double port memory in which the thread can write the identifier of a system call and its parameters. The call is read by the operating system via a dedicated bus connecting all the reconfigurable partitions (Fig. 3). Once the system call done, returns values are written back in the memory and are read by the thread. This static part also includes a Network Interface and allows the thread to communicate with the external world through a dedicated Network-on-Chip (NoC) [START_REF] Devaux | Flexible communication support for dynamically reconfigurable fpgas[END_REF].

Once instantiated by the operating system, the hardware actor is able to execute four basic commands : start, suspend, resume and stop. As the actor is located into a dynamically reconfigurable partition, its state (from an OS point of view) has been specifically defined as described in the finite state machine of Fig. 5. As illustrated in this figure, a hardware actor is either preemptible or non-preemptible. In the latter case, the scheduler can not suspend or move the actor to another place. To come back to a preemptible state, the actor notifies it explicitly (blocking system call or call to a specific primitive).

The main advantage of a hardware component is its parallel nature. In order to be consistent with the SDF computation properties of the high-level specification (see Section III), we have added the architectural mechanisms that allow the actor to support software pipelining. According to a buffer management by the User FSM (Fig. 4), a hardware actor would be able to process three actions in parallel: i) Receive data from the network ii) Compute data stored in its private memory iii) Send data to the network At low-level, the transfer of data between relocatable hardware threads is thus ensured by the management of Virtual Channels. Thus the middleware offers, both in hardware and software, additional services on top of the existing RTOS services. Threads can then use these services by subscribing to one or more channels. A subscription to one channel allows threads to be independent from the location of the others, thereby bringing closer the specification and its implementation.

A. Middleware

The middleware must provide a set of system features available to the application to access to the execution resources, the communication and the memory in a transparent way. System features virtualize the OS services and the application can then access those services regardless their physical location within the platform. This layer can request any service from the OS despite their location and the mechanics of invocation.

Its role is to enable communication between system resources ensuring synchronization of data exchange. The concept of control includes synchronization aspects, sending and receiving events, access to mutual exclusion semaphores, etc. We identify two types of communications: data transfer and control transfer. The middleware form the communication medium for transferring data between two thread, as shown in Fig. 7. This layer is described from two perspectives: the data transfer part (MW2), and the control part (MW1).

We took as a starting point the existing middlewares, and in particular the principle of the ORB 1 which, in our case, will be represented by the notion of Virtual Channel (VC). A VC is a channel designation indicating a particular virtual circuit on a network that will use the local and the distant services of the couple (OS, Middleware).

Two approaches are possible for the communications of the homogeneous type: a-The first one corresponds to a synchronous communication when the sender and the receiver are present during the communication. In this case, the exchange or transmission of data is done by directly sending data packets from transmitter to receiver. In this case we define the notions of VirtualChannelSend / VirtualChannelReceive and the synchronization of the exchange and the reservation of resources necessary for communication. b-The second type of communication occurs when one thread is not present (preempted or relocated) in the system at the time of communication.

From the latter case, there are then two possible scenarios: i) The current thread waits for the other one. However when a timeout (proposed as a service parameter) is reached the control is handed back to the system through the middleware, so that it continues its normal execution. ii) The middleware stores temporarily data in global memory and shares it in order to free resources from the first thread once the copy is complete. This

1 Object Request Broker last case corresponds to an asynchronous communication.

In addition to the historical services of the OS, the virtual channel services are currently viewed as additional services that are mapped on top of the existing OS services beyond those offered by the MPCI layer.

Currently the implementation of these services of Virtual Channel is ongoing. It includes the OpenVirtualChannel primitive, which establishes a point to point communication between actors and determines the type of communication (synchronous or asynchronous). The sending and receiving services of the middleware : VirtualchannelSend and Virtu-alChannelReceive, which allows sending and receiving messages on the VC, from memory when copying the contents of transfer, or directly from the thread's buffer.

The service EndCommunication is only used by hardware threads to indicate the end of data transfer to the middleware and make threads preemptible again (FSM of Fig. 5). Indeed, as depicted in Fig. 4, unlike software threads, the hardware threads manage their own local memory and must then inform the Flexible HwOS of the end of transactions.

The service CloseVirtualChannel allows the closure of the channel, thus the channel becomes free again for a new transaction. Each call to a service available on this platform requires to update the Virtual Channel tables, distributed both in hardware and software, onto the FOSFOR architecture (Fig. 8). This control flow is managed by the middleware on top of the message queue service of the underlying RTOS. Fig. 9 shows the attributes of the services and the return value of each of them.

B. Network interface

The Network Interface (NI) is the static interface of the Hw Thread (Fig. 4). It is connected to a dedicated Network-on-Chip (NoC) [START_REF] Devaux | Flexible communication support for dynamically reconfigurable fpgas[END_REF] implemented, in order : This interface provides two low-level services, namely a procedure to send data from the thread's private memory to the NoC, and another to receive data from the NoC and write it into the same memory. Especially, this network has been designed to support bi-directional transactions, and so allows to implement efficient software pipelining mechanisms inside the hardware threads.

NI architecture is shown in Fig. 10. Two FIFOs allow the User FSM to stack Send and Receive requests. These requests are then respectively processed by a Packetizer and a Depacketizer. A DMA connected to the internal memory of the actor, is driven on one hand by the Packetizer to read data in memory and send it through the NoC. On the other hand, the Depacketizer receives data from the NoC and writes it into the internal memory. Elements connected to the NoC communicate through it by sending data packets over the network. A protocol has been specified and implemented to provide two main features to a thread.

The first one consists in writing data to an element connected to the NoC. This element can be another thread, a memory or another kind of peripheral. The second is reading data from another element. In the case of a passive element, such as a memory, a special packet has been defined to allow read operation in two phases : one request from the thread and an answer from the memory.

The protocol adopted for the network has been thought to provide these two features in a transparent way for the developer. Moreover, additional data constitute the header of a packet, and make possible the routing of a packet between the hardware domain (ie. the NoC), and the software domain (ie. the AMBA bus), via a bridge able to understand this protocol (See Fig. 3).

VI. EXPERIMENTS A. Image processing application

The application deployed on the FOSFOR platform is a target tracking application represented in Fig. 11. This application is responsible for detecting, tracking and recognizing targets existing in an infrared input video stream. The spatial resolution is 640x480 pixels by frame, and acquisition frequency at the output of the camera is 25 Hz. Application is divided into four static actors, and a dynamic one. The first actor of the static part corresponds to the acquisition of the data from the camera (Acquisition). It is followed by another one for the detection of the targets (Detection). The third actor gets the results from the tracking actors and ensures the coherency within a list of the current tracked targets (CCM). A last actor asks for this list and displays the encompassing square of each target into the input image (Incrustation).

The dynamic part of the application corresponds to the tracking actor, responsible for maintaining the coordinates of one of the target detected in the video (Tracking) by computing the Continuously Adaptive Mean shift (camshift) algorithm [START_REF] Cheng | Mean shift, mode seeking, and clustering[END_REF]. As a result, they provide to the CCM actor the bounding box coordinates of the target they are tracking.

B. Application partitioning

Application has been ported first on a monoprocessor platform based on the Leon/SparcV8, running at 80 MHz on a V5SX50 FPGA. Table I shows the timing results for the detection actor which is the most time consuming. Some parts of the application are well suited to be implemented in hardware, such as ghv filter and closing operator. However, in the delay of the project, we chose to not focus on the performance, and privilege the demonstration of the dynamic management provided by the platform. Finally, the detection parts are deported on a standard PC and connected to the FPGA through an Ethernet link. Thus, the hardware part of the application consists in the different tracking actors which will be created dynamically depending of the number of detected targets.

C. Hardware implementation

For the demonstrator, we choose the ML506 board [18]. The software OS is RTEMS, which allows the communication between the two LEON3 processors [START_REF]Gaisler research library[END_REF].

The Camshift algorithm is divided into four steps. In the first step, it is waiting for a new image to process. Then it receives the frame of the image. In the third step, it processes the centroid of the target. Finally, when receiving the last data of the frame, it indicates if the target has been detected. The developed Camshift IP (Fig. 12) is a dataflow IP encapsulated into the hardware actor container of Fig. 4. A start signal indicates the beginning of a new frame. After starting, it consumes pixels corresponding to the frame and so, tracks a target into the frame calculating the centroid of the target. Once it receives the end signal, it delivers a result. This result is the coordinates of the centroid and indicates the processing convergence.

The control of the IP is decoupled into two channels. The first one is used to start and stop the processing. The second one to get data to process from the private memory. After processing, results are sent in an internal buffer which will be transfered on the NoC afterwhile.

D. Application deployment

In order to map the dataflow model onto this target architecture, hardware actors have to support software pipelining. One solution to achieve this goal is to make the synchronization explicit between the NI Packetizer component, the NI Depacketizer component and the accelerator, into the request. A request will be composed of the information needed by the component to process the request, plus additional information about its synchronization with the other components (Fig. 13). Such a view fits into the dataflow model in which input tokens are generated and exchanged between the synchronization modules, regarding the requests instructions. II shows the FPGA resources used by the components needed to encapsulate the dataflow IP. Synchronization module is under development and will be integrated soon.

Adding the hardware reconfigurable container to the IP is not free, it represents a 13% overhead of the LUTs, and a 150% overhead of the registers for the small camshift accelerator. However the major part (static) of this container will be reused by the other reconfigurable actors and remains a poor percentage of the resources available in the current FPGA. Yet

VII. CONCLUSION AND FUTURE WORK

In this article, we presented a high-level model of computation dedicated to the heterogeneous Systems-on-Chip. We intend to propose a full flow in which the low-level hardware implementation matches with the concept brought by a SDF model of computation. In this way, a middleware layer has been added to an existing operating system in order to abstract the heterogeneity and the location of the different actors of the application.

A model of hardware actor has been evaluated, which takes into account, on one hand the advantage provided by the partial dynamic reconfiguration, and on the other hand the need of abstraction regarding the model of computation. With the increase of the FPGA circuits size, intermediate results reinforce our choice of providing generic interfaces, both for hardware and software actors. Such an abstraction facilitates the partitioning and also the design exploration of more and more complex heterogeneous Systems-on-Chip.

In the future work, we will continue to implement the middleware and the synchronization mechanisms of the hardware actors.

Fig. 1 .

 1 Fig. 1. Design flow for reconfigurable data flow applications

Fig. 2 .

 2 Fig. 2. Communications into the platform

Fig. 3 .

 3 Fig. 3. FOSFOR Architecture

Fig. 4 .

 4 Fig. 4. Hardware Thread Architecture

Fig. 5 .

 5 Fig. 5. Hardware Actor States

Fig. 6 .

 6 Fig. 6. FOSFOR layers

Fig. 7 .

 7 Fig. 7. Middleware layers

Fig. 8 .

 8 Fig. 8. Middleware communication

Fig. 9 .

 9 Fig. 9. Virtual Channels services

Fig. 10 .

 10 Fig. 10. Network Interface architecture

Fig. 11 .

 11 Fig. 11. Target Tracking Application

Fig. 12 .

 12 Fig. 12. Wrapper Camshift

Fig. 13 .

 13 Fig. 13. Synchronization modules

req. by User FSM 6 Pop wr. req. by Packetizer 7 Process wr. req. by Packetizer and DMA 8 Push rd. req. by User FSM 8 Pop rd. req. by Packetizer 9 Process rd. req. by Packetizer and DMA 10 Write (transfer on NoC + process BRAM) 16 Read (transfer on NoC + process BRAM) 21

  can be a limitation for the number of reconfigurable slots into the FPGA.Timing measurements for the Network Interface are shown in TableIII. Measurements are done on the time to push and pop a requests in the FIFOs, and the time taken by the NI to decode the request and process it. Write and Read measures give the latency to write and read one 32-bit-width word in an internal memory (ie. a BRAM), connected on the top of the NoC.

	Component	Registers LUTs	BRAMs	DSPs
	OS Interface	38	41	1	0
	System FSM	4	6	0	0
	Network If.	509	602	0	0
	Packetizer	186	88	0	0
	Depacketizer	67	103	0	0
	DMA	132	184	0	0
	Memory	0	0	1	0
	Wrapper	129	75	0	0
	Camshift IP	454	5387	0	5
			TABLE II
	HARDWARE THREAD RESOURCES OVERHEAD
	Operation			Time (in
				cycles)
	Push wr. TABLE III
	NETWORK INTERFACE COMMUNICATION MEASUREMENTS

it

VIII. ACKNOWLEDGEMENT

FOSFOR is a research project funded by the French National Research Agency (ANR). The authors would like to thank all those who have helped in the realization of this article.


Yue Ma

¸ois Lévy

Sudeep Ghimire

Reasoning with Annotations of Texts

Linguistic and semantic annotations are important features for text-based applications. However, achieving and maintaining a good quality of a set of annotations is known to be a complex task. Many ad hoc approaches have been developed to produce various types of annotations, while comparing those annotations to improve their quality is still rare. In this paper, we propose a framework in which both linguistic and domain information can cooperate to reason with annotations. The underlying knowledge representation issues are carefully analyzed and solved by studying a higher order logic, which accounts for the cooperation of different sorts of knowledge. Our prototype implements this logic based on a reduction to classical description logics by preserving the semantics, allowing us to benefit from cutting-edge Semantic Web reasoners. An application scenario shows interesting merits of this framework on reasoning with annotations of texts.

Introduction

In Natural Language Understanding (N.L.U.), several kinds of tools have been tuned for certain particular usages -morphological analysis, chunking and tagging, syntactic analysis, etc.. Meanwhile, a trend grows toward platforms allowing to use different tools on the same text (see e.g. (Enjalbert, Habert, and Bontcheva. 2008) for some descriptions, Stanford CoreNLP 1 suite for an implementation and the UIMA norm 2 for a framework). The interaction of different levels of analysis is well known by linguists, but the cooperation of different tools has been rarely equipped with formal description or reasoning mechanisms. Relying on a standard representation of different typed annotations attached to text fragments, we propose a logical framework that is able to cope with the results of different tools in a common formalism, to express logical relations linking them and, on this basis, to detect incoherences or to add inferred annotations. An example and a prototype implementation sketch the operationalization of our formalism.

Annotation is a powerful and flexible device to assign diverse kinds of information to text fragments (e.g. words, sentences, paragraphs). In this paper, we mainly consider two categories viz. syntactic and semantic. Syntactic annotation is traditionally used in the field of N.L.U. for information extraction (henceforth I.E.), while semantic annotation is required to make semantic analysis of texts and therefore largely emerges in cutting-edge texts oriented applications. For syntactic annotation, annotation types are defined according to linguistic functions of a text fragment in the sentence: their hierarchy is rather flat and inference does not matter so much. Contrarily, semantic annotations are intended to represent meaning of texts and generally rely on a formal reasonable ontology that has a deep structure with complex inference mechanisms. Note that a series of ontology reasoning tasks, such as OWL3 (ontology web language) reasoning4 , have been widely studied and shown useful for exploring implicit data in the field of Semantic Web.

As explained in section 3, describing several types of annotations in the same classical formalism may cause modeling errors or block the expected inferences. To provide a proper modeling of annotations of texts, the new formalism proposed in this paper is equipped with a non-classical semantics to cope with various types of text annotations. Moreover, the computation of this formalism is shown able to be reduced to classical OWL reasoning, so that operations over annotations can be done by reusing cutting-edge Semantic Web techniques.

The paper is structured as follows. Related work is firstly discussed in Section 2 and then building blocks of our platform are described in section 3. The knowledge representation issue and solution are given afterwards as the theoretical support of this framework in section 4. Finally, a specific application and its implementation are studied in section 5.

Related Work

Knowledge acquisition or information extraction systems aim to acquire knowledge from texts, such as event extraction, named entity recognition, ontology construction. The acquired results are usually stored separately and used as semantic resources for other applications. Different from these systems, our work coincides with semantic annotation approaches (e.g. KIM 5 and Semantic Turkey6 ) with a focus on revealing the meaning of texts explicitly, by marking texts with suitable annotations from some ontological vocabularies. Naturally, to automate the semantic annotation process, I.E. techniques are beneficial and have been explored [START_REF] Uren | Semantic annotation for knowledge management: Requirements and a survey of the state of the art[END_REF][START_REF] Ma | Formal description of resources for ontology-based semantic annotation[END_REF]. Refer to [START_REF] Uren | Semantic annotation for knowledge management: Requirements and a survey of the state of the art[END_REF]) for a significant review of this field and interesting scenarios on using ontology for annotating texts.

Note that most existing semantic annotation systems only consider a part of ontological elements: individuals and their conceptual categories [START_REF] Fallucchi | Semantic turkey -a new web experience in between ontology editing and semantic annotation[END_REF][START_REF] Kiryakov | Semantic annotation, indexing, and retrieval[END_REF]). However, our application is to annotate domain specialized regulatory texts which differ from them in scaleeach corpus is incomparably smaller -and in scope -the annotations have to cover a larger part of the content. In our case, annotation labels are from domain ontologies built by experts and thus extend far beyond general labels like Person, Location, Organization. Additionally, concept or role occurrences in these texts are much more frequent than that of individuals. This need for varied fine-grained annotations leads to knowledge modeling problems. Therefore, while many specific semantic annotation systems have been extensively studied, this paper is to study the knowledge representation issue underlying ontology-based multi-layer annotation systems, and to provide a sound way to take advantage of different kinds of annotations.

A problem highlighted in [START_REF] Uren | Semantic annotation for knowledge management: Requirements and a survey of the state of the art[END_REF]) and left for ongoing research is about keeping annotations consistent with evolving resources, particularly in combination with evolving ontologies. Our formalism provides a step in this direction by studying a way to detect conflicts in annotations with regard to domain ontologies, which is not supported by trivial representations of annotations as shown in Section 3.

Last, (logic-based) declarative I.E. systems [START_REF] Poon | Joint inference in information extraction[END_REF][START_REF] Shen | Declarative information extraction using datalog with embedded extraction predicates[END_REF][START_REF] Reiss | An algebraic approach to rulebased information extraction[END_REF][START_REF] Suchanek | Sofie: A self-organizing framework for information extraction[END_REF] have been developed to encode annotation process in logics, possibly with some predefined predicates for linguistic annotation patterns (e.g. patternOcc, disambPrior, express). Different from them, our framework aims to be part of an annotation platform on which users can uniformly analyze various linguistic and semantic annotations and their interactions.

Building Blocks

An annotation witnesses a link between a text fragment and some knowledge, so it relies on several models: a text model on one side to describe annotated fragments, a knowledge model on the other to describe annotations [START_REF] Lévy | An environment for the joint management of written policies and business rules[END_REF]). To cope with several sorts of knowledge, independent knowledge models are needed. In this paper, we deal with a syntactic and a semantic model. They are described as OWL ontologies, which has a good compromise between expressive power and computability.

A naive modeling could cause loss of information or representational mistakes. For instance, suppose we use a binary relation hasSemAnno(tf, C) to represent that a text fragment tf is semantically annotated by concept C. Then two annotations, such as hasSemAnno(tf, C 1 ) and hasSemAnno(tf, C 2 ), are consistent even if disjointness of C 1 and C 2 results from a domain ontology. Suppose now that the same annotation is plainly represented as tf is a C, i.e. C(tf ). Although the previous inconsistency can be computed, due to multiple ontologies we may have to write both City(tf ) and N oun(tf ), which together entail that the concept City and the grammatical category N oun have overlaps -it is not intended either. Note that although the "punning" feature7 of OWL 2 relaxes the separation between the names of e.g., classes and individuals, it is not enough to solve the above representation problems.

To solve the problem, semantic annotations are considered apart, and annotation assertions are used to account of them. Globally, annotation assertions allow to perform standard OWL inferences over annotations as given in Section 4, and, as described in section 5, to bridge inferences about constraints between semantic and linguistic levels by SWRL8 (Semantic Web Rule Language) rules. Before any formalization, this section explains the underlying ideas of our formalism and its preconditions.

Semantic annotation types

Ontological knowledge is built from different kinds of entities, all of which can be used for annotation. Therefore, we need to differentiate the distinct relations between an annotation label and a text span. Listed below are four annotation types mainly considered in our formalism, with their formal names given in brackets. Figure 1 illustrates this idea by an example where all these types are involved: Concept Annotation (sa:Concept) : Some text fragments denote ontological concepts by themselves (e.g. "non-elite status member"). Such text fragments are usually referred as elements of a domain terminology. This is the most frequent case in our working corpus.

Role Annotation (sa:Role) : Similarly, text fragments may also denote conceptual roles if the underlying notions have been encoded as roles rather than as concepts in the ontology (e.g. "applies to", "be discontinued for" or "reservation").

Individual Annotation (sa:Individual) : Some text fragments directly denote ontological individuals. They are traditionally referred to as named entities, such as "X Airline" which refers to a specific airline company, or "the minimum mileage guarantee", a special policy name. In this case, the semantic annotation is the ontological individual itself.

Individual-Concept Annotation (sa:Ind-Con) : Other text fragments refer to individuals but their annotations indicate the concept they belong to. This is the often case when using concept City as a label of "Paris" or when labeling "the minimum mileage guarantee" by concept P olicy.

Note that when a concept from a reference ontology is used to annotate a text fragment, two cases are possible: either the text fragment talks about a special instance of this concept (sa:Ind-Con), or it is about the concept itself (sa:Concept) instead of any specific individual.

Ontologies

Besides a domain ontology, a language ontology is required. The former is to provide semantic labels for semantic annotation, and represents domain knowledge, while the latter embeds text model and linguistic knowledge.

The upper part of Figure 1 is a domain ontology example. More details of the domain ontology used for annotating our corpus is described in Section 5. For our formalism, it accepts any OWL ontology as the semantic one. The language ontology first describes textual level information. As a basis, it has a concept name T extF ragment, whose individuals are annotatable segments of texts. As two or three text fragments can be grouped to form a new one, role names contains, contains2, and contain3 are also included. They satisfy the following conditions (OWL axioms are written using OWL functional syntax 9 ):

(1) ObjectPropertyDomain(R T extF ragment), (2) ObjectPropertyRange(R T extF ragment),

where R ∈ {contains, contains2, contains3};

(3) T extF ragment (≤ 2)contains2. T extF ragment;

(4) T extF ragment (≤ 3)contains3. T extF ragment.

(5) SubObjectP roperty(contains2, contains) (6) SubObjectP roperty(contains3, contains)

The first (resp. second) OWL axiom says that the Domain (resp. Range) of all three roles is T extF ragment. The third (resp. fourth) puts a constraint on contains2 (resp. contains3): any given T extF ragment instance can only be related with at most two (resp. three) T extF ragment instances. The fifth and the sixth state that contains2 and contains3 are sub-roles of contains. A usage scenario of this textual ontology is given in Section 5.

In this same language ontology, we can have various linguistic annotation types. In this paper, we take the noun compound modifier (nn for short, [START_REF] Marneffe | Generating typed dependency parses from phrase structure parses[END_REF][START_REF] Séaghdha | Learning compound noun semantics[END_REF]) as an example. But other linguistic annotation types can be represented, e.g. any set of binary syntactic relations with the help of as many roles, 9 //http://www.w3.org/TR/2008/ WD-owl11-syntax-20080108/. For writing simplicity, we ignore ontology prefixes before ontological elements.

or POS tagging with the help of relation hasPos and POS constants, as in hasPos(tf, Verb).

Interpreting Semantic Annotations

Annotating is attaching a label to a text fragment, but does not decide precisely how this attachment must be interpreted: this depends on the intention supporting the attachment. Below is an informal description of our interpretation, while the formal one is given in section 4.

For the sa:Concept (resp. sa:Role) annotation type, if a text fragment tf is annotated by a concept or a role, the intention is to state that the meaning of tf is covered by its annotation -but not necessarily equal to it (the exact meaning can be a subtype of the annotation). In practice, it often happens that a concept which is not the exact meaning is chosen to annotate a text fragment. This happens either because sometimes the most refined annotations are not necessary for applications, or because they are hard to be discovered or lack in the given semantic ontology. For annotations of type sa:Individual, the meaning of the text fragment is supposed to be the instance in the semantic ontology. Finally, for annotation type sa:Ind-Con, it states that the meaning of the text fragment is a special instance of the annotation concept, and the choice of the concept is a matter of relevance.

Formalism for Reasoning with Annotations

This section provides a formalism for reasoning with annotations of texts. Syntactically, it considers a domain ontology, a language ontology, and annotation assertions using four possible annotation types. To allow inferences on annotations, the interpretation is higher-order. Then reasoning is done by a reduction to classical OWL semantics, which enables us to invoke highly optimized OWL reasoners to infer from syntactic and semantic annotations taking into account the domain and language ontologies. Due to space limitation, examples are found in Section 5 and proofs are left out.

Syntax

Description logic (DL) languages, the logics underlying OWL, are the syntactic base of our formalism. We assume that readers are familiar with basic description logics; [START_REF] Baader | The Description Logic Handbook: Theory, Implementation and Applications[END_REF]) provides a comprehensive background.

Each classical DL language L assumes a vocabulary N L composed by three pairwise disjoint parts: a set of concept names (or atomic concepts) N c , a set of role names N r , and a set of individuals N i . Then, complex concepts are built from N L by a set of concept construction operators of L. In this paper, we use the DL language ALCH whose complex concepts can be defined inductively as follows, where A ∈ N c , R, S ∈ N r :

C → A | C 1 C 2 | C 1 C 2 | ¬C | ∀R.C | ∃R.C
Axioms in ALCH can be in the form of C D, R S, A(a), and R(a, b) with a, b ∈ N i . More expressive domain and language ontologies, not required for our current application scenario, can be treated similarly if necessary.

In the formalism, we are given three pairwise disjoint sets of names N type , N domn , N lang , where N type ={sa:Concept, sa:Role, sa:Individual, sa:Ind-Con}, N domn and N lang are

Semantics

As illustrated in Section 3, semantic concepts or roles need to be dealt with as individuals when annotating text fragments, and as concepts or roles to perform reasoning on annotations. All the same, different text fragments may be interpreted one as concept, another as role or individual. We now extend classical model-theory semantics of description logics with the ability of interpreting annotation assertions, which is inspired by the higher-order semantics of description logics [START_REF] Giacomo | On higher-order description logics[END_REF]). An interpretation I is first defined, which interprets the semantic elements and the text fragment individuals in a higher-order way, leaving other elements of the language ontology and the four annotation types interpreted classically.

Definition 3 For a text annotation knowledge base T aKb, an interpretation I is a 4-tuple (∆, I i , I c , I r ), where the set ∆ is called the domain of I, and where the mappings I i , I c , I r satisfy:

1. I i : N domn ∪ Individual(N lang ) → ∆; 2. I c : ∆ ∪ Concept(N lang ) → 2 ∆ ; 3. I r : ∆ ∪ Role(N lang ) ∪ N type → 2 ∆×∆ ;
An interpretation I = (∆, I i , I c , I r ) is called extensible if and only if I i can be extended to a mapping of complex concepts of the domain ontology into ∆ such that: Definition 5 (Satisfiability of Semantic annotations) An interpretation I satisfies a semantic annotation assertion T A = tf, ot, at , written I |= e T A, if and only if I is extensible and satisfies:

-I c (I i (¬C)) = ∆ \ I c (I i (C)); -I c (I i (C ∧ C )) = I c (I i (C)) ∩ I c (I i (C )); -I c (I i (C ∨ C )) = I c (I i (C)) ∪ I c (I i (C
• (tf, I i (ot)) ∈ I r (at) • I i (tf ) = I i (ot) if at = sa:Individual; I c (I i (tf )) ⊆ I c (I i (ot)) if at = sa:Concept; I i (tf ) ∈ I c (I i (ot)) if at = sa:Ind-Con; I r (I i (tf )) ⊆ I r (I i (ot)) if at = sa:Role.
Given a text annotation knowledge base T aKb = O domn ∪ O lang ∪ AnnoSet, an interpretation I satisfies (is a model of) T aKb, written I |= e T aKb, if and only if I is extensible and satisfies O domn , O lang , and AnnoSet, as defined above. T aKb is said satisfiable if it has a model.

For the computation of the satisfiability of text annotations as defined above, it can be achieved by adopting the reduction method given in [START_REF] Giacomo | On higher-order description logics[END_REF] such that the satisfiability checking of T aKb can be reduced to the classical satisfiability checking of a transformed DL ontology. Due to the space limitation, we omit details here.

SWRL Rules for Reasoning with Annotations

Reasoning with annotations can include different aspects, among which is the inconsistency checking of a set of semantic annotations regarding to a domain ontology as discussed above (see A in Figure 2). Another aspect is to use SWRL rules to produce more conclusions on semantic and syntactic annotations. This can be illustrated by the B part in Figure 2 and is further detailed in Section 5. Note that the B part of Figure 2 does not consider domain ontology. In this way, higher-order semantics of SWRL rules is avoided, since the plain set of semantic and syntactic annotations together with the SWRL rules (see Section 5) only form a classical SWRL rule base.

In this section, to show benefits of providing a platform for reasoning with various kinds of annotations of texts, we extend the language ontology O lang with the extra syntactic annotation type nn (noun compound modifier).

Focusing on noun compound is a good choice to exemplify the cooperation because, compared to roles, concept names are dominant in the given domain ontology 11 (211 classes vs. 37 roles). In consequence, noun phrases are more often semantically annotated by concepts. Quantitatively, among 808 semantic annotations we have on the corpus, 53% contain text fragments with at least one nn annotation. Whilst, among 660 syntactic annotation nn on the corpus, 64% have at least one semantic annotation associated to their text fragments. Considering that there are 48 syntactic dependency types defined by Stanford Parser 12 , these numbers mean that the overlap between semantic annotations and nn annotations is remarkable. Indeed, in recent years there has been significant ongoing interest in noun compound in NLP [START_REF] Séaghdha | Learning compound noun semantics[END_REF][START_REF] Kim | Interpreting semantic relations in noun compounds via verb semantics[END_REF], mainly concerned with using suitable paraphrasing verbs or prepositions to interpret relations between noun components 13 . Applications include machine translation, page ranking and query refinement. Contrarily, our work aims to detect missing and erroneous (syntactic/semantic) annotations for noun compounds.

In the following, four SWRL rules are introduced with examples to show the benefits of analyzing annotations together, including propagating new semantic annotations (Rules 1 and 2), reporting missing semantic annotations (Rule 3), and detecting incoherence between syntactic and semantic annotations (Rule 4). Generated semantic annotations are checked for consistency with respect to domain ontology in our platform, which is necessary to assure their soundness. Table 1 gives the statistics about the coverage of the rules for our annotated corpus. These rules cover most of nn instances in our corpus except 235, either by the limitation of logical rule language or the lack of semantic annotations. This is reasonable since not every sentence in the corpus is semantically related to domain ontology.

Adopting Stanford Parser notations, nn(tf 1 , tf 2 ) is used to say that tf 1 (the head) and tf 2 (the modifier) have nn syntactic relation, where tf 1 , tf 2 are text fragments. Since a semantic annotation is frequently associated with more than one word, different from Stanford Parser, our formalism allows for multi-word text fragments. Text fragments are generated as follows: 1. Each word is a text fragment; 2. A group of two (resp. three) consecutive words is a text fragment, which has contains2 (resp. contains3) relation with the inner smaller text fragments. For example, if tf 1 and tf 2 are the first and second words in a sentence, they are 1-word text fragments and tf 12 (the 1st and 2nd words together) is a 2-word text fragment. Moreover, contains2(tf 12 , tf 1 ), of nn" is divided based on whether its head or its modifiers are semantically annotated. For example, the type "head but not modifiers" means that its head has semantic annotation but not any modifier. The "Appl. rule" is the rule that can be applied directly without considering recursive reasoning.

contains2(tf 12 , tf 2 ) are in O lang . Similarly for 3-word text fragments.

Rule 1 (Recognizing semantic annotations)

nn(tf 2 , tf 1 ) ∧ contains2(tf 3 , tf 1 ) ∧ contains2(tf 3 , tf 2 ) ∧ tf 2 , A, sa:Concept → tf 3 , A, sa:Concept
That is, if the head of nn is semantically annotated by concept A, the whole text fragment containing the head and modifier should have the same semantic annotation A.

For the sentence in the corpus "Your summary includes participant mileage", its syntactic and semantic annotation are nn(tf 4 , tf 5 ) and tf 5 , AA M ileage, sa :Concept , where tf 4 ("participant") and tf 5 ("mileage") are 1-word text fragments. By Rule 1, a new semantic annotation tf 45 , AA M ileage, sa :Concept can be recognized for the 2word text fragment tf 45 ("participant mileage").

Rule 2 (Recognizing semantic annotations) nn(tf 3 , tf 1 ) ∧ nn(tf 3 , tf 2 ) ∧ tf 23 , B, sa:Concept ∧ i=2,3 contains2(tf 23 , tf i ) ∧ i=1,2,3 contains3(tf 123 , tf i ) → tf 123 , B, sa:Concept . This is a 3-word text fragment case extension of Rule 1. That is, for a text fragment tf 123 = tf 1 tf 2 tf 3 with syntactical structure nn(tf 3 , tf 1 ) and nn(tf 3 , tf 2 ), if its sub-text fragment tf 2 tf 3 has a concept semantic annotation, tf should have the same semantic annotation. This is the case of the sentence: "AAdavantage flight mileage credit is determined on the basis of nonstop distances..." with a semantic annotation tf 2 tf 3 , M ileage Credit, sa:Concept for 2-word one tf 2 tf 3 ("mileage credit"). By nn relations among 1-word text fragments tf 1 ("flight"), tf 2 ("mileage"), tf 3 ("credit"), this rule says that the 3-word text fragment "flight mileage credit" should have a semantic annotation M ileage Credit.

Rule 3 (Reporting missing semantic annotations)

nn(tf 2 , tf 1 ) ∧ tf 1 , A, sa:Concept → tf 2 , U * , sa:Concept), where U * is a new concept name.
That is, if the modifier of nn has some semantic annotation concept, the head should be semantically annotated, but by which concept is unknown. Intuitively, if a modifier carries some meaningful semantic information, so should its head. An example sentence is "AAdvantage flight awards may not be combined with other AAdvantage flight awards" with annotations nn(AAdvantage, awards) and AAdvantage, AA P rogram, sa :Concept hold but leaving no semantic annotation for the text fragment "awards". For this, Rule 3 reports that semantic annotation for "awards" is missing (indicated by the semantic label U * ).

Rule 4 (Conflicting syntactic & semantic annotations) nn(tf 3 , tf 1 ) ∧ nn(tf 3 , tf 2 ) ∧ tf 12 , A, sa:Concept ∧ contains2(tf 12 , tf 1 ) ∧ contains2(tf 12 , tf 2 ) ∧ tf 1 = tf 2 → isWrongNN(tf 3 , tf 1 ) ∧ addNN(tf 2 , tf 1 ), where isWrongNN and addNN are two new roles to report a wrong nn relation and to suggest a new nn relation between two text fragments, respectively.

That is, for a text fragment like tf 1 tf 2 tf 3 if tf 3 is the nn head of tf 1 , tf 2 , but tf 12 = tf 1 tf 2 is a text fragment with some semantics, then it is highly potential that nn(tf 3 , tf 1 ) is wrong but nn(tf 2 , tf 1 ) holds. An example is "Only individual persons eligible for AAdavantage program membership" with annotations nn(tf 3 , tf 1 ), nn(tf 3 , tf 2 ), and tf 12 , AA P rogram,sa:Concept with 1-word text fragments tf 1 ("AAdvantage") and tf 2 ("program"), and 2-word text fragment tf 12 ("AAdavantage program").

The reasoning formalism in Section 4 and this use case has been implemented in our system prototype in Java. Text corpus stored as RDF is processed using Jena to extract text fragments and the relationship between consecutive text fragments. Semantic annotations (RDF format) and Syntactic annotations (XML format) are input for the system and the SWRL reasoning service is implemented by using Pellet 14 . In whole, various kinds of annotations of texts can be reasoned with by invoking highly-optimized reasoners.

Conclusion and Perspectives

We have motivated and formally defined an approach for reasoning with annotations of texts with respect to various kinds of background knowledge. Our approach is based on an extended higher-order description logic. An application scenario has illustrated that linguistic and semantic annotations are mutually beneficial for deducing extra annotations or detecting problematic ones. A tool has been developed and implemented via a reduction to classical entailment such that state-of-the-art ontology reasoners can be reused for reasoning with text annotations.

The approach opens two perspectives for future work. First we shall study in detail more linguistic and semantic annotation types to discover new rules and gain more knowledge. Second, the added annotations can also in principle improve results of other tools. Richer treatment architectures become possible if new or problematic annotations can be re-injected in some tools, possibly interactive ones. We shall define and experiment some re-injection architectures.

Figure 1 :

 1 Figure 1: Ontology-based Semantic Annotation on texts "...the minimum mileage guarantee will be discontinued for any non-elite status member....This change applies to travels on X Airline,...".

  vocabularies of a domain ontology O domn and a language ontology 10 O lang , respectively. The set of concepts (resp. roles, individuals) names of an ontology O is denoted asConcept(O) (resp. Role(O), Individual(O)), or, abusing the notation, Concept(N O ) (resp. Role(N O ), Individual(N O )).Definition 1 (Semantic annotation assertion) A semantic annotation assertion is a triple in the form of tf, ot, at satisfying tf ∈ T extF ragment and the following conditions:• If at ∈ {sa:Concept, sa:Ind-Con}, then ot ∈ Concept(O domn ); • If at ∈ {sa :Role}, then ot ∈ Role(O domn ); • If at ∈ {sa:Individual}, then ot ∈ Individual(O domn );Finally, a text annotation knowledge base is defined below:Definition 2 A text annotation knowledge base is T aKb = O domn ∪ O lang ∪ AnnoAsserSet,where AnnoAsserSet is a set of semantic annotation assertions.

  )); -I c (I i (∀R.C)) = {x | ∀y.(x, y) ∈ I r (I i (R)) implies y ∈ I c (I i (C))}; -I c (I i (∃R.C)) = {x | ∃y.(x, y) ∈ I r (I i (R)) and y ∈ I c (I i (C))}. Definition 4 Given an extensible interpretation I, 10 N lang contains at least {T extF ragment, contains, contains2, contains3}. Other concepts in N lang can be the concept POS with instances Verb, Noun, Adj, Adv, etc. Other roles can be nn as discussed in Section 5 and hasPos in Section 3.2. • I satisfies C D if and only if I c (I i (C)) ⊆ I c (I i (D)) for C, D in O domn , I c (C) ⊆ I c (D) otherwise; • I satisfies R S if and only if I r (I i (R)) ⊆ I r (I i (S)) for R, S in O domn , I r (R) ⊆ I r (S) otherwise; • I satisfies C(a) if and only if I i (a) ∈ I c (C) for C ∈ Concept(N lang ) and I i (a) ∈ I c (I i (C)) otherwise; • I satisfies S(a, b) if and only if (I i (a), I i (b)) ∈ I r (S) for S ∈ Role(N lang ) ∪ N type and (I i (a), I i (b)) ∈ I r (I i (S)) otherwise.

Figure 2 :

 2 Figure 2: Reasoning with Annotations

Table 1 :

 1 Coverage of Rules on the Annotated Corpus, where "type

	11 available	on	http://ontorule-project.eu/
	outcomes?func=fileinfo&id=32
	12 http://nlp.stanford.edu/software/
	lex-parser.shtml
	13 https://docs.google.com/View?docid=
	dfvxd49s_35hkprbcpt

http://www.w3.org/TR/owl-ref/

Refer to http://www.cs.man.ac.uk/ ˜sattler/ reasoners.html for a list of reasoners.

http://www.ontotext.com/kim/

http://semanticturkey.uniroma2.it/

http://www.w3.org/TR/owl2-new-features/

http://www.w3.org/Submission/SWRL/

http://clarkparsia.com/pellet

Acknowledgments

This work was realized as part of the Quaero Programme (funded by OSEO, French State agency for innovation) and of the FP7 231875 ONTORULE project. We are thankful to American Airline who is the owner of the corpus that has been used as a working example within the ONTORULE project.


Abstract-In line with preliminary studies [START_REF] Henriksson | Non-iterative MUSIC-type algorithm for eddycurrent nondestructive evaluation of metal plates[END_REF] and in harmony with a set of investigations led on fast, non-iterative MUSIC-type imaging algorithms in electromagnetics, acoustics and elasticity, by the authors' research group and others, e.g., [START_REF] Ammari | MUSIC-type electromagnetic imaging of a collection of small three-dimensional inclusions[END_REF], among many references, we are presently considering such an approach in the case of diffusive electromagnetic fields. That is, let us assume that some thick highly-conductive horizontal plate has been somehow damaged, the resulting defects being a small collection of isolated 3-D bounded voids, hidden inside the plate or opening in air at the top interface of the plate (top, as seen vs. the position of the sources, described next), which might also get close to one another in limit cases, e.g., in crack-like fashion. A time-harmonic, eddy-current probe array, which consists of a small number (say, a few tens at best) of identical electric current loops that are either closely packed or well separated from one another within a given planar surface is placed close to and parallel with the plate, above the zone where the defects are assumed to be found; each current loop (assimilated with an ideal magnetic dipole orientated vertically) is excited one after another, the anomalous vertical magnetic field observed at all loop centers (in effect, it is proportional to the variation of impedance which is traditionally measured) being collected, yielding us a multi-static response matrix in a rather restricted polarization mode (vertical magnetic dipoles and vertical components of the magnetic fields) however.

The method of imaging itself relies on a first-order asymptotic formulation of the anomalous magnetic field as is induced by the defects. The latter is valid when those appear small enough with respect to the skin-depth at the frequency of operation, yet we still expect to get some useful information when sizes are not so small (but always well smaller than the skin-depth, which is a realistic hypothesis in eddy-current non-destructive testing). Then, a singular value decomposition of the multistatic response matrix collected as indicated in the above is carried out. Discrete singular values and vectors emerge in so doing, which can be separated into quantities respectively associated to a signal subspace and a noise subspace; from that distinction, which means also that the level of noise is not such that the singular spectrum is too corrupted, we can compute a MUSIC indicator (in effect, several indicators can be introduced, as it will be shown in the presentation) expected to peak at the location of the defects. After a brief presentation of the mathematical formulation behind the approach, and some reminder of the validity and limits of the asymptotic field formulation via a comparison with results provided by means of the modeling CIVA platform from CEA, we will exhibit singular value patterns and MUSIC images. Here, a high-level Gaussian distributed noise is added to the data, and a number of arrangements of the source array and locations and distributions of the defects, at various frequencies (usually a low, median and high one, in effect allowing closeto-surface, median and deep imaging), will be considered. This will enable us to highlight pros and cons of the approach, as well as signaling paths of further research, notably in terms of thin perfectly-isolating cracks, for which so far only 2-D models in the frame of scalar scattering and for propagative fields appear to have been dealt with via non-iterative methods similar to the one herein, refer, e.g., to [START_REF] Park | Electromagnetic MUSIC-type imaging of perfectly conducting, arc-like cracks at single frequency[END_REF].

  Fast Imaging of Void Defects in Conductive Half-space T. Henriksson, M. Lambert, and D. Lesselier Département de Recherche en Electromagnétisme, Laboratoire des Signaux et Systèmes UMR8506 CNRS, SUPELEC, Univ Paris Sud, France