Arthur Casals

Assia Belbachir

Amal El Fallah-Seghrouchni

Anarosa Alves

Franco Brandão

Amal El-Fallah

Fostering agent cooperation in AmI: a context-aware mechanism for dealing with multiple intentions

Introduction

Ambient Intelligence (AmI) is a reference to electronic environments in which electronic devices or systems can perceive and respond to the presence of people, while also being able to communicate with each other [START_REF] Aarts | Ambient intelligence[END_REF]. In such environments, cooperation and coordination among different systems may exist in different forms, and Arthur Casals Escola Politécnica -Universidade de São Paulo, SP, Brazil, e-mail: arthur.casals@usp.br Assia Belbachir IPSA, Paris, France, e-mail: assia.belbachir@ipsa.fr Amal El-Fallah Seghrouchni Sorbonne Université, LIP6-CNRS UMR 7606, Paris, France e-mail: amal.elfallah@lip6.fr Anarosa Alves Franco Brandão Escola Politécnica -Universidade de São Paulo, SP, Brazil, e-mail: anarosa.brandao@usp.br 1 for different purposes. This paper presents an approach to cooperatively deal with multiple intentions for a specific type of intelligent agent that interacts with AmI environments, denominated ambient agent (AA). The cooperative model in place is opportunistic, i.e., cooperation may exist if there are favorable conditions for it to occur. Since AmI environments provide dynamic contextual information, the AA's reasoning process must adapt to environment changes as efficiently as possible, while still making it possible for the AA to achieve its goals.

Adopting Multiagent Systems (MAS) to deal with contextual information in AmI applications is interesting because of its very nature, where different entities autonomously interact in a dynamic and uncertain environment [START_REF]Engineering Multi-Agent Systems -4th International Workshop[END_REF][START_REF] Piette | A multi-agent solution for the deployment of distributed applications in ambient systems[END_REF]. MAS whose agents follow the BDI model are specially tailored for AmI due to its inherent use of contextual information in the form of beliefs. These agents, however, may have different and independent goals, and still need cooperation to perform specific tasks. This can be illustrated in a real-world situation: if a person has an appointment but cannot be there in time, getting a ride from someone will make this goal achievable. Other similar AmI-related situations include cooperative collision warnings in vehicular ad-hoc networks [START_REF] Dua | Efficient Data Dissemination in Vehicular Ad Hoc Networks[END_REF] and opportunistic problem-solving using ontology negotiation [START_REF] Sidney | Cooperation between intelligent information agents[END_REF].

While extensive research has been conducted in the field of intelligent agent cooperative planning [START_REF] Di Febbraro | An agent-based framework for cooperative planning of intermodal freight transport chains[END_REF][START_REF] Torreno | Fmap: Distributed cooperative multiagent planning[END_REF][START_REF] Engesser | Cooperative epistemic multi-agent planning for implicit coordination[END_REF][START_REF] Nigon | Self-adaptive model generation for ambient systems[END_REF], most of the existing work relies on central coordination or communication mechanisms. Such restrictions can make it difficult to use the existing research in AmI scenarios where agents possess individual goals, but cooperation without previous commitment is still beneficial. With that in mind, we propose a cooperative planning mechanism that can be used by an AA to delegate specific plans to other agents. The objective is to provide cooperation in each of the agents' planning processes without having to commit to common goals, or make use of central planning engines of any kind. In terms of scientific contribution, this work also makes it possible to deal with multiple intentions while maintaining the collaboration mechanism among intelligent agents strictly opportunistic. In addition, we also improve the BDI agent reasoning mechanism by using a preemptive planning mechanism in conjunction with contextual planning. Thus, the proposed mechanism makes possible for different agents to cooperate among themselves to achieve goals otherwise unachievable by delegating the execution of specific plans. It is important to notice that the cooperation mechanism does not assume benevolent agents, nor it is based in existing commitments of any sort: AAs only cooperate among themselves if it is on their best interests.

This paper is organized as follows: Section 2 introduces relevant aspects of planning and cooperation used along this paper, with a description of the contextual planning system (CPS [START_REF] Chaouche | Learning from situated experiences for a contextual planning guidance[END_REF]). Section 3 describes the Collective CPS (CCPS) by presenting its formal structure and related algorithms. Section 4 presents, as proof of concept, an implementation of CCPS in a real-world based scenario, and describes the experiments performed. Finally, Section 5 concludes this paper and presents some perspectives for future work.

Background

In this section we present an overview of planning and cooperation in the domain of BDI agents, followed by the CPS, which is the contextual planning mechanism used as a basis for the present work.

Planning and Cooperation

The planning process used by a BDI agent involves choosing a set of actions to be executed and it is triggered whenever new information is perceived. Re-planning over new information allows the agent to adapt its plans accordingly and re-evaluate its goals at each interaction, so it can adopt the best course of action at the time.

Environmental changes can occur independently from the agent (such as the natural passage of time), or as a consequence of an executed action. One agent's actions can impact the perceptions of other agents in the same environment. If agents have different goals, one agent's actions may cause another agent's goals to become unachievable. Using coordination mechanisms can mitigate these impacts [START_REF] Durfee | Scaling up agent coordination strategies[END_REF], and eventually increasing the overall planning efficacy or efficiency in face of a dynamic environment [START_REF] Jung | An architecture for distributed cooperative planning in a behaviour-based multi-robot system[END_REF][START_REF] Osawa | A metalevel coordination strategy for reactive cooperative planning[END_REF]. It may also be the case that coordinated planning is a requirement for solving the problem at hand.

While there exist solutions aimed at solving situations that require cooperative planning processes [START_REF] Di Febbraro | An agent-based framework for cooperative planning of intermodal freight transport chains[END_REF][START_REF] Torreno | Fmap: Distributed cooperative multiagent planning[END_REF][START_REF] Engesser | Cooperative epistemic multi-agent planning for implicit coordination[END_REF], they usually consider joint goals situations, either relying on central coordination systems or being limited by the problem domain. AA could benefit from cooperative planning in situations where individual efficiency is affected by environmental conditions, ultimately executing certain tasks more efficiently. If multiple agents were to cooperate, context-dependent tasks could be delegated among them, and otherwise unachievable goals could be successfully achieved. Our approach aims at exploring situations where contextual-dependent tasks may be delegated by one AA as part of its planning process, giving the coordination process a contextual dynamic characteristic. We will detail this approach in the following paragraphs, from the formalism involved to the planning mechanism.

Contextual Planning System (CPS)

In the original BDI-agent model, an interpreter manages the agent states related to its beliefs (B), desires (D), and intentions (I) in order to achieve goals through planning. Let A = {A 1 , A 2 , ..., A n } be the set of agents and A i ∈ A.

Chaouche et. all [START_REF] Chaouche | Learning from situated experiences for a contextual planning guidance[END_REF] proposed a model to deal with multiple intentions for an agent A i . It represents an agent plan P(A i ) as a tree structure composed of a set of intention plans ( Pj ) and elementary plans (P l,k ). P(A i ) is composed of multiple intention plans Pj , and each intention plan corresponds to the achievement of an agent's intention.

An intention plan Pj can be an alternate of multiple elementary plans: Pj = {P j,0 , ..., P j,q }. Alternating elementary plans allows achieving an specific intention in different manners, each one expressed by an elementary plan.

Elementary plans P j,k are described by AgLOTOS expressions [START_REF] Chaouche | A Higher-order Agent Model with Contextual Management for Ambient Systems[END_REF], referring to behaviour expressions E i,k expressed as an ordered finite set of observable actions a i to be executed by the agent. Any AgLOTOS expression is associated with contextual information related to the (current) BDI state of an agent. These elementary plans are obtained from a library of plans (LibP).

Using this model, Chaouche et al. [START_REF] Chaouche | From intentions to plans: A contextual planning guidance[END_REF] proposed a predictive planning mechanism that uses the contextual information to verify which among the actions known by the agent are feasible. "Feasibility" of an action is determined by any conditions the agent must met to execute it. For instance, moving from point A to point B is only feasible if agent is at point A. Once this verification occurs, CPS selects an execution path that maximizes the number of satisfied intentions [START_REF] Chaouche | From intentions to plans: A contextual planning guidance[END_REF], producing an optimal plan P(A i ). In the next section we will explain how this plan is used by the Collective Contextual Planning System (CCPS) in conjunction with its cooperative mechanism.

agent's environment or by taking the opportunistic aspect into account. The concepts involved in CCPS will be formalized and explained in the next paragraphs.

Formal framework

In this section, we introduce some of the definitions necessary to formally describe the CCPS and its algorithm.

• Environment: Env(t) is a set of logical propositions representing contextual information that can be perceived by any agent at time t. • Action: An action a represents the finest granular activity performed by the agent in the environment. If an agent A i moves from point X to point Y , there is an associated action move(X,Y ). Each action a is subject to three sets of logical propositions (as in STRIPS [START_REF] Richard | Strips: A new approach to the application of theorem proving to problem solving[END_REF]): preconditions list (Pre(a)); delete list (Del(a)); and post-conditions list (Post(a)). An action a if feasible if all of its preconditions Pre(a) are satisfied by the conditions of Env(t). After an action a is executed, its conditions can be changed by Del(a) or Post(a)also altering Env(t). • Intention: Each agent A j ∈ A has a set of intentions, and each intention is associated with a weight factor that serves as a comparator index, used to determine order of importance between two intentions. Thus, the intention function over the known agents is defined as I : A -→ IxW, and the set of intentions for an agent is expressed by:

I(A j ) = {(i 0 , w 0 ), (i 1 , w 1 ), ..., (i n , w n )}, A j ∈ A, i 0 , ..., i n ∈ I, w 0 , ..., w n ∈ N *
Two intentions are comparable according to their associated weight factors: given (i p , w p ), (i q , w q ) ∈ I(A j ), 0 ≤ p, q ≤ n, i p is at least as important as i q if w q ≤ w p .

• Plan: Plan definition follows exactly the one from CPS, presented at 2.2.

• Plan Feasibility: Being a composite and partially ordered set of actions, the feasibility of an elementary plan P i, j can be given by the feasibility of its actions: P j,k is feasible in Env(t) if and only if all of its actions are feasible in Env(t). An intention plan Pj is feasible if and only if at least one of its elementary plans is feasible. In the case of an agent plan P(A i ), we determine that it is completely feasible if and only if all of its intention plans are feasible.

There might be situations where it is necessary to consider partial feasibility of an agent plan P(A i ). Suppose that P(A i ) contains a set of intention plans { P1 , ..., Pq } referring to I j = {(i 0 , w 0 ), (i 1 , w 1 ), ..., (i j , w j )}, I j ⊆ I(A i ). In this case, if only Pj is unfeasible and w j is relatively much lesser than the other intentions' weights, it could make sense for the plan P(A i ) to be executed anyway, while the intention I j is still unfeasible. However, if we have a situation where w j is relatively much greater than the other intentions' weights, we should not want to proceed with P(A i ) at all, and re-planning becomes necessary.

Let us also consider the following notations: the average weight of all intentions associated with all intention plans in P(A i ) is given by w I , and the average weight of all intentions associated with all feasible intention plans in P(A i ) is given by w F . With that in mind, we define the concept of partial feasibility for an agent plan: P(A i ) = { P1 , ..., Pj } is partially feasible if w F ≥ w I . In the rest of this work, we will consider an agent plan P(A i ) unfeasible if it is not partially feasible. In the same manner, a plan P(A i ) will be considered feasible if it is at least partially feasible.

It is also important to formalize a few aspects related to agent communication -in particular, the aspects involving the exchanged messages between agents, and their possible effects on the CCPS mechanism. When an agent A j requests help to other agents, this is done through a message M containing at least one unfeasible action selected from P(A j ). This message also contains temporal limits and a deadline. Temporal limits are associated with actions, and are formed by two different limits: a beginning (when an action should start), and an end (when an action should be finished). The deadline, on the other hand, is associated with the message and it is the time limit for the message to be answered. Once the deadline expires, the agent won't expect any replies to that particular message.

The concepts of complementary and equivalent intentions are also important to the CCPS mechanism since they are related to the cooperative process. Suppose that there are no other agents present in the environment, or no other agent can provide help. In this case, the agent asking for help tries to find any complementary and equivalent intentions that may exist within its original set of intentions. Complementarity and equivalence are defined considering that different intentions can have similar or equal results when their plans are executed. We consider that two intentions are complementary if at least one precondition of one of the intentions corresponds to a post-condition of the other. Additionally, two intentions are equivalent if at least one precondition of these intentions is identical, and if all the post-conditions of both intentions are the same.

Experiments

To verify the proper functioning of the CCPS structure, we implemented a proof-ofconcept (PoC) version of the mechanism and tested it in conjunction with an application scenario. The CCPS PoC mechanism used the algorithm previously described and was implemented in Java. All interactions between the agents were simulated with the use of the JADE framework1 . This implementation was evaluated according to a formal experimentation process appropriate for case studies in the Software Engineering domain [START_REF] Wohlin | Experimentation in software engineering[END_REF]. The study protocol used in this evaluation was: (i) Using the concept of opportunistic cooperation as a basis, create a scenario with predictable outcomes; (ii) Defining the situations in which the scenario would be executed; (iii) Defining the theoretical outcome of the scenario for each of the situations; (iv) Running the scenario for each of the situations, using the PoC implementation; (v) Analyzing the results, comparing the obtained data with the expected outcomes for each situation; and (vi) Discussing the results, pointing out any relevant issues or points of attention regarding the evaluation and its elements.

The objective of the evaluation was to observe if the CCPS mechanism could properly identify and act on situations involving opportunistic cooperation. Hence, we decided to study a specific scenario considering (i) isolated agents, with no communication in-between, and (ii) agents that are able to communicate and delegate individual tasks to each other. We used the CCPS formalization as a frame of reference to determine which would be the behavior in both situations, so that we could compare the outcome of the experiments with a theoretical baseline. By running the same scenario under different contextual conditions (simulating a dynamic environment), we wanted to compare how the use of the newly implemented opportunistic cooperation mechanism would affect the performance of each agent in terms of reaching individual goals. Our expectation was that the use of the CCPS mechanism would allow the agents to reach their individual goals more frequently when exposed to different environment conditions.

Scenario

To evaluate the CCPS mechanism in the domain of Ambient Intelligence (AmI), we chose to model a scenario related to Smart Cities, as described by Streitz [START_REF] Streitz | Citizen-centred design for humane and sociable hybrid cities[END_REF]. According to this author, one of the goals of designing smart cities should be "enabling people to experience everyday life and work". Achieving this goal could be done through the use of location-based services and communication infrastructure used to connect different citizens among themselves and the city.

Having these concepts in mind, we based our scenario in a situation involving four different agents: Alice, Bob, Claire, and Damien. All agents play different roles within the campus of a University. Some of the agents could cooperate to achieve their individual intentions, such as retrieving a specific resource (book) or getting to a specific location (parking) in a specific time (taking the bus respecting the bus schedule). Cooperation among the agents was passively stimulated with the use of contextual restrictions, such as means of transportation, the agents' initial locations, temporal restrictions (duration of different actions, and time limits in which they should be performed), and so on. The scenario location was modeled after a university campus, and possesses different locations: a laboratory, three different offices, a parking lot, a bus stop, and the residence of all agents. Each of the agents possess the following routines (used to model their intentions): (i) Morning preparation (actions that take place before each agent leaves their residence); (ii) Going to the university; (iii) Going to work; and (iv) Going back home. Also, individual conditions were attributed to the agents (Alice and Claire have cars, but Bob and Damien take the bus; Alice and Bob work in the same office; and a few others).

Situations and expected outcomes

The scenario described above was executed in three different environment conditions (contexts), considering starting time (enough time to achieve time-sensitive intentions), inherently unachievable intentions, and the presence of equivalent intentions. Considering the aforementioned experiment situations, the expected results in the next paragraphs refer to the situations where communication between the agents is possible. The situation where the agents cannot communicate with each other was used as a reference to measure the efficacy of the implementation.

In the first context (1), the scenario started at 8 a.m., and each agent was given a set of intentions to be evaluated and eventually achieved along the day (e.g., going to work, working, coming back home). These intentions did not necessarily require cooperation of agents, and the temporal restrictions related to all actions involved were set in a manner that cooperation was not necessary at any part of the planning process. In this context, we expected that none of the agents would ask for any help.

In the second context (2), the starting time was kept at 8 a.m., but a few unsatisfiable intentions were also included (e.g., asking a book to the agents when none of them have it), with no equivalent or complementary intentions that could be used. In the case of the satisfiable intentions, in some cases we included equivalent intentions to reach the same goal (going back home by bus or by a ride in another agent's car). In this context, we expected that the agents with unsatisfiable intentions to ask the other agents for help; however, since they were designed to be absolutely unfeasible, we expected the agents to ask for help and -in the absence of any replies -to try and find any equivalent intentions that could be used. Ultimately, we expected that the agents to discard the unfeasible intentions and re-plan using the remaining intentions.

In the third context (3), we started the scenario at 9 a.m., but included unfeasible intentions with equivalent feasible intentions. This context was supposed (i) to allow opportunistic cooperation to effectively take place and (ii) to allow the agents to properly use the equivalent intention mechanism. In this context, we expected the agents to use more time in the planning process, but also to achieve more goals (compared to the non-communicating situation).

Results

Once properly coded and parametrized within the implementation, the scenario described in section 4.1 was executed, and the results were compared with the expected outcomes for each context.

In the first experiment (context 1), the agents behaved as expected. Both the non-communicating and the communicating agents were able to generate achievable plans for all of their intentions using the same amount of time. Our conclusion was that the verification involved in checking if cooperation was needed had no impact in the computational resources required.

In the second experiment (context 2), the communicating agents spent considerable additional time (about 200% more) trying to ask for help and trying to find an equivalent intention before reaching the same plan as the non-communicating agents. However, the outcome was still consistent with the expected results.

In the third experiment (context 3), the communicating agents also took considerably more time to reach a final plan, but in this case their plans also had much more achievable intentions than the non-communicating agents. In some cases, where all intentions were dependent on the achievability of a single one (duration and temporal limit for reaching specific locations), some non-communicating agents had considerable less intentions included in their plans, since the others were simply not achievable (as expected). On the other hand, the plan created by the communicating agents, while feasible, took a considerable amount of time to be generated.

Conclusion and future work

In this paper we formally presented CCPS, a cooperative contextual planning mechanism to be used by AA in AmI scenarios. CCPS was designed reusing an existing contextual planning mechanism (CPS) in conjunction with cooperation based on delegation. The resulting structure makes it possible for an agent to achieve goals otherwise unachievable through the cooperation with other agents running in the same environment. We were able to properly evaluate the CCPS mechanism by simulating a specific scenario in different contexts, using a proof-of-concept implementation and comparing the obtained results with the theorized expected situations. While we were able to confirm the proper functioning of the mechanism, there are a few considerations that must be taken into account.

The first one is related to efficiency: we observed that taking advantage of opportunistic cooperation situations also drastically increased the planning process time. In a real-world situation, this could negatively impact the goal achievement success rates of the agents using the CCPS mechanism. This situation is not completely unexpected, however, and we expect to address in future research.

Another consideration related to the experiments performed was related to the communication process. When the CCPS mechanism finds an unfeasible intention, the communication process that takes place is simple, but not optimal. I a worstcase scenario, the environment might be flooded by help requests. We also intend to study this limitation by testing different constraint mechanisms.

Finally, there are multiple aspects yet to be explored in the proposed CCPS mechanism. Different parts of its algorithm can be detailed studied, and concepts such as complementary and equivalent intentions can be refined. Implementation can also be extended to support multiple scenario variations in runtime, and more complex scenarios can be used to verify how the CCPS mechanism performs under different conditions. We intend to explore all of these aspects in future work.

Collective Contextual Planning System (CCPS)The Collective Contextual Planning System (CCPS) structure is designed to process plans from multiple CPS-capable agents. The novelty here, in comparison with the CPS mechanism, is that when an agent plan cannot be executed for any reason, the agent can ask for help and delegates part of this plan to other agents, avoiding re-planning. By doing this, the agent eliminates the problem while maintaining the consistency of its goals. At the same time, all the parallelism and concurrence taken into consideration by the original CPS mechanism are maintained.In the first step of the CCPS mechanism, an agent has an initial plan resulting from the CPS mechanism execution and verifies if it can be executed without the help of any other agent. If that is not the case, the agent detects which actions are preventing the plan from being executed. These actions are listed in a help request message that is sent to other agents. After receiving this message, each agent decides about offering help for each action and reply its answer. The requester agent and decides about accepting help and inform the helper agent its decision. In the case where no other agent is able to provide help, the agent tries to replace the intention associated with the plan that cannot be executed with a different one that could provide similar results. If no such intention is found, then the original intention is removed.The idea behind this mechanism is similar to the contract net protocol[START_REF] Reid | The contract net protocol: High-level communication and control in a distributed problem solver[END_REF], designed for distributed problem-solving. Aspects related to connection and contract negotiation, however, are simplified -either by considering that it is provided by the

http://jade.tilab.com

Acknowledgements Arthur Casals is supported by CNPq, grant no. 142126/2017-9.


Carlos Eduardo Pantoja
email: pantoja@cefet-rj.br

Cefet / Rj

Heder Dorneles Soares

José Viterbo
email: viterbo@ic.uff.br

Tielle Alexandre
email: tiellesa@id.uff.br

Arthur Casals
email: arthur.casals@usp.br

Amal El-Fallah Seghrouchni

A Resource Management Architecture For Exposing Devices as a Service in the Internet of Things

Keywords: Internet of Things, Embedded Systems, Ubiquitous Computing

This work proposes an architecture for sharing devices' resources in the Internet of Things providing real sensor data for its users. The main idea is based on the fact that users such as developers and researchers do not always have access to the necessary hardware and resource sharing should impact these persons activities. Taking advantage of the Sensors as a Service model, we propose an architecture where several sensors and actuators can be coupled to environments and they also are represented virtually in a web system becoming available to be consumed by users and platforms. The architecture is composed of three layers and a model representing devices, the cloud, and clients, and how they interact with each other. A study case for testing the whole approach is also presented.

I. INTRODUCTION

The number of computing devices used in daily tasks, the internet coverage as well as how to handle data, are increasingly being used to improve people's lives and together with the Internet of Things (IoT), they are the key to the development of a wide range of applications [START_REF] Santos | Logistics sla optimization service for transportation in smart cities[END_REF]. These large number of components open up relevant issues, such as sharing data in heterogeneous environments once sensors deployment often employs high costs. Then, mechanisms for resource sharing should play a major role in this scenario.

These applications gather data from several sensors and the number of devices can make the project unfeasible. There is an emerging cloud computing model named Sensors-asa-Service, where users can make public their own sensors' data to be consumed by other clients [START_REF] Perera | Sensing as a Service Model for Smart Cities Supported by Internet of Things[END_REF]. However, it is difficult to integrate and deploy such systems due to the heterogeneity of devices and communication technologies [START_REF] Weiser | Some computer science issues in ubiquitous computing[END_REF], [START_REF] Pantoja | An architecture for the development of ambient intelligence systems managed by embedded agents[END_REF]. Considering this, middleware for IoT play an important role in these systems since they can deal with the heterogeneity of hardware, data distribution, and communication protocols.

So, the objective of this paper is to propose an architecture for the management of resources and to expose them as a service in an IoT network. This Resource Management Architecture (RMA) is divided into three layers of abstractions where devices are responsible for keeping the real resources independently from the core of RMA, which deals with the virtualization, registering and updating of data from devices. DOI reference number: 10.18293/SEKE2019-187 Then, clients can consume this data as a service using exposed web services that access the virtualization layer. The aim of RMA is to provide an integrated solution to be used in any domain since its general architecture is not bounded to any application provided and to work as a repository of devices where researchers can make their data consumable to other persons who might be interested in them.

The RMA is built over instances of a robust middleware for IoT in its layers, which treats the connectivity and scalability of devices [START_REF] Endler | Past, present and future of the contextnet iomt middleware[END_REF]. Besides, we also propose a structure for the development of devices able to self-configuration in the RMA. Finally, the RMA can be accessed by web services or other web solutions. The rest of this paper is structured as follows: in section II, we present the related works; section III presents our proposed architecture and their components; in section IV, it is described the implementation of RMA; section V the RMA is evaluated based on software engineering methods. Finally, conclusions are discussed in section VI.

II. RELATED WORKS

During the last years, several approaches try to deal with shareable resources in different domains. For example, the research in Ambient Intelligent has been searching for technological strategies to improve the people life quality and solve problems caused by population growth in urban areas. A lot of papers explore technologies for improving citizen services and how to add value to public administration in Smart Cities [START_REF] Neirotti | Current trends in smart city initiatives: Some stylised facts[END_REF]. In these cases, there are data coming from people, social networks, household, organizations (public and privates), and so on. Devices are often used in such approaches however, issues as interoperability, communicability, and how to turn data public and consumable are not in their scope. In this paper, we present an architecture that can be used to provide a layer of consumable devices that can be applied in any domain and deal with those issues.

When considering systems that use sensors as a service, there is an interoperable system [START_REF] Priyantha | Tiny web services: design and implementation of interoperable and evolvable sensor networks[END_REF] that offers a web service description language interface designed for users to access sensors. However, its main focus is on low-power wireless sensor nodes and energy profile. The SOCRADES middleware [START_REF] De Souza | Socrades: A web service based shop floor integration infrastructure[END_REF] is a solution for business integration that offers a web service-oriented architecture that integrates different types of intelligent objects. It uses an enterprise business solution system to provide the ability of users to construct services based on physical objects using the Web of Things [START_REF] Guinard | Towards the web of things: Web mashups for embedded devices[END_REF] and using REST applications [START_REF] Ostermaier | Webplug: A framework for the web of things[END_REF]. These approaches tie the design of the device to the web system restraining new devices to be added at runtime. In our proposed approach, devices have their own mechanism for dealing with the core system at runtime.

III. THE RESOURCE MANAGEMENT ARCHITECTURE

In this section, we present the Research Management Architecture (RMA), an architecture responsible for the virtualization of devices that act as IoT objects, exposing their sensors and actuators to be accessed and consumed by who might be interested in their functionalities. These resources' data are maintained at runtime in a model that can be publicly visualized and subscribed for several purposes. Exposing devices as a service that can be virtually consumed brings some advantages since users do not need to have their own devices, reducing eventual costs in creating new ones. In this way, users can provide a shareable resource component that can be exploited for several purposes. The proposed architecture (Figure 1) is composed of three different layers:

1) Device: in this layer, the devices have an embedded system enhanced with a processing cycle where (i) it connects and registers in the Cloud layer at the very first time; (ii) it gathers data from all its sensors to be sent to the cloud layer and; (iii) it receives from the Cloud layer actions that must be executed by the device's actuators. 2) Cloud: it is capable of maintaining updated information from devices hosted in environments and running over an IoT middleware. The Resource Management Component (RMC) manages (i) the registering process of devices; (ii) the sensors' data updating process, and; (iii) the actions that must be executed by devices. Besides, it also capable of exposing RESTful web services for several purposes. 3) Client: it is responsible for the visualization of devices and environments. In this paper, it is represented as a web solution. It implements a publish and subscribe mechanism for allowing developers and researchers in obtaining data from real sensors without possessing them and it offers an infrastructure for those who want to provide sensors as a service.

In the RMA, a device is an IoT object equipped with a micro-controller (hardware) where sensors and actuators are plugged in. The devices host an embedded system capable of connecting and registering to the Cloud layer for providing current data to be consumed by users. The embedded system dynamically registers itself in the RMC by sending all its functionalities (available resources, data and action commands) and the environment it is situated. Once connected, the device receives a confirmation and it starts to send data gathered from its sensors directly to the RMC, which keeps the most recent value available to be consumed or visualized in a web panel in the Visualization layer. Besides, the embedded system deals with the action commands coming from the RMC that need to be executed by the device's actuators. The RMC is the main component in the RMA and it maintains information about devices and environments to be consumed as a service by other layers. It has a mechanism for registering devices in given environments, storing their information in the Virtualized Components Database (VCDB). The VCDB keeps updated the data coming from devices by considering only the new values that have changed since the last data message was received. In addition, this layer exposes web services for providing different services such as visualization layers for mobile applications or allowing new technologies to interact and access the VCDB. Web services use a RESTful architecture for system interoperability and it uses Json files for exchanging information (data, requisitions, and execution commands) between the Cloud and Client layers.

The actions that need to be executed by devices are managed by the RMC. Any user that desire to perform an action in any available actuator must send an action command by accessing one of the provided services. The RMC redirects the action directly to the specific device. The technical information about hardware and actuators is transparent to the end user, that just need to know the available commands of the device he or she wants to interact. While one device is being used, the RMC blocks the specific actuator or the entire device for avoiding conflicts in the lower layer. The respective resource is unlocked after the execution or after a timeout boundary.

The RMC is a server-side solution running an IoT middleware instance where the devices must connect to. The middleware provides the connectivity and communicability necessary for devices to interact with the RMC layer and it should guarantee the scalability of the system. These issues are not the focus of this work, however more technical details about the chosen middleware are provided later in Section IV.

For facilitating the environments managing, this layer provides a web page where all the environments can be accessed at real-time and users can create their own public or private environments. This web system shows all the public environments allowing users to select and see their available information and subscribe to have access to a specific and personalized group of information. In this work, an environment is defined by a logical representation of a physical space where several devices can co-exist sharing information in an IoT network.

IV. IMPLEMENTING THE RMA'S LAYERS

In this section, it is presented the implementation of the Device, Cloud and Client layers considering technological components and how these layers communicate with each other. For both Device and Cloud layers, we employ the ContextNet middleware [START_REF] Endler | Past, present and future of the contextnet iomt middleware[END_REF], which is an IoT middleware for context reasoning and data sharing in a large scale environment. It is a context-providing service for stationary and mobile networks, which already addresses data communication issues such as fault tolerance, load balancing, node disconnect support (handover), and security. It uses the OMG DDS [START_REF] Pardo-Castellote | Omg data-distribution service: Architectural overview[END_REF] protocol for handling messages between clients.

The Device layer uses a low coupled serial interface [START_REF] Lazarin | A robotic-agent platform for embedding software agents using raspberry pi and arduino boards[END_REF] for communicating with the micro-controllers that hosts the sensors and actuators. This interface isolates the high-level programming from the low-level using serial commands for activating users' pre-defined functions, which controls actuators or gathers data from sensors. The Client layer employs a web system capable of managing environments, showing their available resources, and it has a publish and subscribe mechanism for users interested in specific resources. All layers consider a model where these resources are part of devices situated in pre-existing environments in the architecture. For instance, the environments have to be manually registered by the user to facilitate their management and for security issues. This model is represented as a class diagram (Figure 2) shared between the three layers. The classes that can be found in our solution are described as follows:

• Action: the action that is executed at the low-level hardware in a device. Every command sent by the the Client and Cloud layers becomes an action in the Device layer. ers. The resources keep information about the serial port where the resource is connected, the available commands to be executed, and the availability of the resource. • Resource Management: it is the main class of the cloud layer and it is a server instance of the ContextNet. It keeps a list of environments mapped and the devices registered for each one. It is responsible for the process of registering and updating devices and resources. It also exposes the web servers and the interfaces to the database. • Serial Communication: the serial interface between the micro-controller and the system hosted at devices.

A. The Device Layer

The Device layer comprises devices running an embedded system with enough processing power interfacing sensors and actuators. There is a physical and logical architecture for clients where the first one uses hardware technologies and it is composed of a tiny mobile board with Bluetooth and WiFi connections (e.g. Raspberry Pi) connected to one or more micro-controllers using serial communication for accessing sensors and actuators. The logical architecture of the Device layer comprises both micro-controllers' programming and the embedded system. They are able of gathering the raw data from the sensors and then send it to the embedded system. After that, the embedded system sends the data to the Cloud layer or receive commands to be executed by actuators.

The micro-controller is programmed in a loop for verifying if there are messages coming from other layers. So, it accesses all the sensors and mounts a string to be sent by serial communication to the embedded system. Otherwise, the execution action is verified and if exists an equivalent programmed, an action is executed in the respective actuator. registerDevice()

The embedded system controls the microcontroller and it uses a ContextNet client able to communicate with the Cloud layer. For this, there is a cycle (Algorithm 1) for synchronizing the reception of data coming from sensors to be sent to the Cloud layer and the actions that need to be sent and executed in the micro-controller because both cannot execute at the same time for avoiding undesired conflicts. So, the actions received from the Cloud layer are put in a queue of actions to be executed one step after the data from sensors are collected through serial ports. It is also capable of performing a selfconfiguration and registration at the Cloud layer when it starts running and there is a cloud server available. For this, the device keeps an XML file describing all the available resources, commands, and the server configuration information. Once the file is correctly filled, the system performs everything automatically. The following information must be provided:

(i) Server: the gateway of the server and the port must be provided in order to connect to the Cloud layer where the server instance of the ContextNet is installed. Besides, the time interval of sending data to the server must be set. (ii) Environment: for instance, it is necessary to inform in which environment the device is inserted into. For this, the identification number of the environment must be declared in the configuration file. The environment's identification is generated when users register an environment in the web system. (iii) Resources: all the resources available must be mapped in the configuration file. All the resources have the serial port where it is connected, its name, and a non-mandatory description. If the resource is an actuator, it also has the available execution commands.

The embedded system architecture is composed by the Cycle class, which instantiates an instance of ContextNet client (represented by the EmbeddedClient class) capable of exchanging message with other clients and the cloud server. Besides, the EmbeddedClient is responsible for the serial interface and it deals with a queue of actions received from the Cloud layer that has to be executed. The SerialCommunication and Action are the classes responsible for these behaviors.

B. The Cloud Layer

The cloud layer is a server instance of the ContextNet running a core system responsible for the virtualization of environments, devices and available resources. The devices register at the cloud informing their resources and environment where they are situated. This process starts when the core receives the file containing all the information of the device. Then, the system extracts the necessary information from the file and it registers the device at the system in the informed environment. Afterward, it sends back a message to the device authorizing the beginning of sending data from sensors.

Once the devices start sending data, the core system registers the new values and updates the old ones in VCDB (Figure 1). For every device, there are resources that can be sensors or actuators. In the case of sensors, if it is the first time that a new value of a resource is received, the system inserts this new value at the VCDB. Otherwise, if the value has changed since the last data reception, this new value is updated in VCBD. In the case of actuators, there is no data to be stored but it is kept the information about the availability of the resource. For example, the system informs if a certain actuator is being used or it is free for executing commands.

The core system deals with commands requisitions coming from the Client layer (a web system or by exposed web services) to be sent and executed at devices. The Client layer does not need to know technical details of hardware or even in which device the command will be executed. The commands are specific for a resource and the core system avoids duplicated resources and commands. Besides, it also redirects a received command to the respective device registered at the system by sending a message using ContextNet.

In the Cloud layer, there is also a locking process for avoiding conflicts in executing actions when two or more clients try to execute commands in the same actuator. For this, every time that a client needs to use a specific actuator, the core system locks this resource until the client informs that is no longer using it, the action was performed, or a timeout boundary is reached. During this process, the locked resource is unavailable for all clients. It is important to remark that sensors are not part of the locking process because the nature of sensors is to provide data to be consumed. If the data is considered confidential, the environment can be set as private.

As stated before, web services can be exposed for extending the functionalities of the RMA in the Cloud layer. For creating RESTful web services it is used as an embedded servlet container and web server named Jetty. The available web services are a requisition service for agents applications for using resources with contextual planning; an execution service for activating or deactivating the actuators based on available commands; and a web service for providing data access to mobile applications.

The Cloud layer's model is composed of the ResourceManagement class where the ContextNet server is instantiated. Besides, it hosts a list of Environments with their Devices, Resources, and Commands classes.

C. The Client Layer

The idea behind the Client layer is to provide a layer capable of showing environments' resources in any kind of platform such as web pages, web services or mobile applications. Besides, it is responsible for providing some basic mechanisms that are not available in previous layers such as environments creation and, publish and subscriber mechanisms for example. The Client layer is represented as a web page for showing all the resources of environments and some basic functions for interacting with the resources. The user is able of creating environments to virtually host his devices and to expose them to be consumed by other users. Besides, the actuators have commands that users can activate by interacting with the Client layer's web system. The technologies employed are relational databases, Java web pages and Ajax.

Besides that, users can choose to follow some of the resources without the need to access the environments every time that he needs to get those values. The publish and subscriber mechanism allows users to access values always that a change is perceived by the core system in the Cloud layer. It allows the user to set basic rules such as defining a desired value to be announced when reached. All existing modules can co-exist without interfering in each other since all functions are managed by the Cloud layer. They all have to connect to the Cloud layer's database or use an exposed web service to access information.

V. EVALUATION

In this section, it is presented an initial case study evaluation in the assisted environment domain using the proposed RMA using a software engineering based approach. Case studies are employed because they are suitable for evaluation of software engineering methods involving development, operation, and its maintenance and artifacts [START_REF] Wohlin | Experimentation in software engineering[END_REF].

The scenario will be held in a hypothetical Smart City where the government has access to a hospital where the RMA is implanted. Some rooms in the hospital building have devices for controlling the temperature and luminosity (as sensors), and light lamps of the room (as actuators), and other devices for measuring some of the patients' information such as heartbeat frequency. Therefore, every room in the hospital endowed with devices is considered an environment in the RMA and its devices' resources are exposed as a service for the board of directors, government and everyone interested in them. It is important to remark that, even in this hypothetical scenario, there is no real personal contact of patients available.

Based on this, two devices were prepared for a room, named Room 403. Both devices use a Raspberry Pi Zero connected to an Arduino board. The first device is connected to a temperature and a luminosity sensor for the basic sensing of the room. The second one is a device with a light lamp connected to the Arduino working as an actuator and informing if the lamps are on or off. Besides, virtual devices were simulated in order to stress the RMC functioning. For this, the serial interface between the embedded system and the hardware were disabled, and several resources were simulated for each virtual device, which sends random data to the Cloud layer. So, one device for monitoring the heartbeat frequency of a patient and devices identical to the real ones above were simulated in each room. In general, 20 environments were prepared where the environment Room 403 has two real devices and one simulated, and the other 19 have three simulated resources.

The case study approach is divided into four steps: case study design, preparation for data collecting, the data collecting and data analysis. The following Table I shows the details and aim of the descriptive case study.

TABLE I THE CASE STUDY DESIGN

Design Description

Objective A descriptive analysis of the behavior of the RMA functioning.

Case

The asynchronous process of transferring information from devices to the Cloud layer to be consumed by clients using web solutions.

Questions

Is the device connects correctly to the Cloud layer? Is the communication process between all layers works? Is the Client layer showing the correct data? Method Qualitative data analysis using negative case analysis and observation method.

Some tests were conducted trying to deny the research questions above. The preparation for the data collecting consisted in store both dynamic registration at the RMC and the answer that devices receive before starting sending data from sensors. Afterward, it is verified if these data arrives at all layers properly by analyzing the transferring process between hardware and device, device and cloud, and cloud and client. A string of data that comes out from the hardware is collected and compared if the data read arrived correctly at the embedded system. Between Devices and the Cloud layer, all devices should keep sending data to be stored at the VCDB in the RMC. Finally, between Cloud and Clients, these same data should be read by clients when data update occurs.

The data collecting and analysis were performed in an arithmetic progression from 1 to 20 devices. Firstly, the server instance was running properly to verify the effectiveness of RMA and then it was disabled. Once there is no server instance available, they should not send data. Then, the data should be properly stored and read by Cloud and Client layers. Table II shows the resumed results from tests. The communication between hardware and the embedded system is done using a serial interface, which guarantees no losses in the data transferring. None errors were observed in this process. As expected, when the server instance is disabled, it is observed that devices try to connect to the Cloud layer but there is no response from the server and no data is sent from any device. Otherwise, the device is registered and receives a confirmation to start sending data to the Cloud. All devices work properly considering an available server instance.

The most recent information available coming from devices is updated in the VCDB. Considering that the VCDB is implemented as a relational database, there are no big deals in this process not even in the visualization of the devices by the Client layer. This case study focused on observing the communication and the correctness of data flowing through the architecture. More experiments focusing on performance and a proper formalization were left for future efforts.

VI. CONCLUSION

In this work, it was presented a low-coupled three-layer architecture for exposing devices as a service to be consumed by clients. The devices are able of connecting to an IoT server, registering their resources (sensors and actuators) in a core system, which turns all the public data available that can be accessed by clients using web services and a web platform. A case study was proposed and evaluated integrating the Device, Cloud and Client layers for monitoring an environment.

RMA architecture employs different technologies in its layers. Devices are autonomous and uncoupled from the Cloud layer because they are built using hardware platforms enhanced with wi-fi connections and it uses a serial interface for communicating with micro-controllers. These technologies provide the necessary autonomy, heterogeneity of hardware employed, and communicability to the Cloud layer. The Con-textNet middleware provides client and server instances and it is used in the architecture because of the middleware guarantees connectivity, communicability, reliability, and scalability, in addition to using an industrial market standard protocol.

The Client layer offers web solutions for managing environments and for the visualization of their respective resources. Besides, it is possible to subscribe specifically to resources that one might be interested in. Moreover, the RMA aims to provide an architecture for exposing devices as a service to be consumed by persons that do not have access to these kinds of resources either for the cost or complexity of creating from scratch an architecture for that purpose.

Nowadays, the designer of the device should program how data is mounted and captured by the micro-controller and sent to the embedded system. As future works, it is important to create an automatized plug-and-play way of configuring the device in low-level. Besides, as micro-controllers are connected to the serial port of the tiny computer of the device, a similar process for the identification of serial ports by the embedded system is also interesting. The environment has to be set manually at the device's configuration file for security and control reasons, nevertheless, it is possible to identify and register autonomously the environment based on access points.

Fig. 1 .

 1 Fig. 1. The Resource Management Architecture's (RMA) components.

Algorithm 1

 1 Device's Processing Cycle 1: procedure CYCLE(conf igurationF ile)

Fig. 2 .

 2 Fig. 2. The class diagram of the overall architecture comprising the Client, Cloud and Device layers.

  • Command: it is the representation of commands available to be executed if the resource is an actuator. Sensors do not have commands because they are data providers. • Cycle: it is the functioning cycle of the embedded system hosted in devices. It is responsible for synchronizing the device activities of sending data and executing actions. • Device: it is the device representation used in the Client, Cloud and Device layers. It keeps the identification, name and description of a device and it is composed resources. • Embedded Client: it is the ContextNet client instance responsible for receiving messages from the Cloud layer and other clients, and sending the data from sensors to the Cloud layer. It also maps the components of the configuration file into its respective components. • Environment: the virtual representation of environments in all layers. Each environment is composed of devices. • Main: the main class that starts a device. • Resource: it represents both sensors and actuators in all lay-


Jean-Franc ¸ois Baget

Michel Leclère
email: leclere@lirmm.fr

Marie-Laure Mugnier
email: mugnier@lirmm.fr

Éric Salvat
email: imerirsalvat@imerir.com

Some Structural Properties of the Logic of Rules

We study the properties of semantic consequence in a particular subset of first-order logic with equality and no function symbols, under the unique name assumption. Formulas in this subset of logic are rules of form ∀ x(H → ∃ yC) where the hypothesis H and the conclusion C are conjunctions of atoms (possibly with equality), x contains the variables in H and y the variables in C that are not in H. This subset is particularly expressive since it can encode a universal Turing machine, at the cost of decidability of reasoning. We propose new decidable subclasses of this problem, by combining restrictions on both the structure of the rules themselves and the structure of the interactions between rules, encoded in the graph of rule dependencies. The most general decidable subclass presented here is based on a mixed forward/backward chaining algorithm. Finally, we relate our rules to other notions (tuple-generating dependencies in databases, conceptual graph rules, the TBox in description logics) and explain how the associated deduction problems could benefit from our results.

Introduction

In this paper, we study satisfiability, validity, and semantic consequence of formulas in the rule fragment of first-order logic (FOL) without functions, with equality, and under the unique name assumption, as often the case in KR. Its formulas are rules of form ∀ x(H → ∃ yC) where the hypothesis H and the conclusion C are conjunctions of atoms. This fragment of FOL is particularly expressive: it is a computation model (it can encode a universal Turing machine), but satisfiability and deduction are undecidable.

Our goal is to present new decidable subsets of this rule logic. To achieve that goal, we study the internal structure of rules as well as the structure of their interactions, and combine them in a mixed forward/backward chaining framework. The foundations of this work have been developed using the conceptual graphs (CGs) formalism: a graph-theoretical encoding of these formulas highlighting their structure. This work extends our previous results by considering a more expressive language (equality is added), and by strictly generalizing the decidable fragment of rules (the notion of finite unification sets is new).

Copyright c 2008, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

In the first section, we show that we can restrict our study, without loss of generality, to the satisfiability and validity of standard knowledge bases, partitioned into facts, standard rules, constraints, and equality rules, and to deducing a fact from such a KB. In the following section, we present a forward chaining algorithm (SM96) that allows us to state the complexity and decidability of our three decision problems in different fragments of our logic of rules. Finite expansion sets of (BM02) ensure that forward chaining will generate in finite time a fact that contains all information that can be deduced from rules. Then, we present the backward chaining mechanism of (SM96). Its originality resides in its ability, in the rewriting of queries, to erase more than one atom (since the unifiers involved unify whole subsets of atoms at the same time). The finite unification sets introduced here ensure that backward chaining will generate a finite number of non redundant rewritings of the query. The next section combines finite expansion and finite unification sets in a mixed forward/backward chaining algorithm, relying on the graph of rule dependencies of (Bag04). From this algorithm stems a new decidable fragment for the logic of rules. Finally, we relate our rules to other notions (tuple-generating dependencies in databases, conceptual graph rules, the TBox in description logics) and explain how the associated deduction problems could benefit from our results.

Preliminaries

Definition 1 (Facts, rules) An atom is either a standard atom p(t 1 , . . . , t k ) built from a predicate p of arity k and a k-tuple of terms (variables or constants, but no other function symbols), the true atom , the false atom or an equality atom x =y between two terms. A fact is a set of atoms. A rule is a couple (H, C) of facts where H is called the hypothesis of the rule and C its conclusion. We note respectively terms(X), vars(X) and consts(X) the sets of terms, variables and constants appearing in the atoms of a fact or a rule X. If R = (H, C) is a rule, we call frontier of R and note fr(R) the set of variables that appear both in H and C.

Semantics

The translation Φ assigns a closed formula in first-order logic (FOL) to each fact or rule. If F is a fact, we note F ∧ the conjunction of all atoms in F . Then Φ(F )

is the existential closure of F ∧ . If R = (H, C) is a rule, then Φ(R) = ∀h 1 . . . ∀h k (H ∧ → (∃c 1 . . . ∃c q C ∧ ))
where {h 1 , . . . , h k } = vars(H) and {c 1 , . . . , c q } = vars(C) \ vars(H). Φ(R) can be equivalently written as ∀f 1 . . . ∀f p ((∃h 1 . . . ∃h l H ∧ ) → (∃c 1 . . . ∃c m C ∧ )) where {f 1 , . . . , f p } = fr(R), {h 1 , . . . , h l } = vars(H) \ fr(R) and {c 1 , . . . , c m } = vars(C) \ fr(R). Every formula in the FOL fragment naturally associated with the forms above can be translated back into a fact or a rule (this inverse translation removes multiple occurrences of the same atom). We consider the usual semantics of FOL formulas with equality, assuming, as often in KR, the unique name assumption (two distinct constants cannot have the same interpretation). A model of a fact or rule X is thus a model of the formula Φ(X), X is said valid (resp. satisfiable) when Φ(X) is valid (resp. satisfiable), and X is a semantic consequence of the facts or rules X 1 , . . . , X p (and we note X 1 , . . . , X p |= X) when Φ(X) is a semantic consequence of Φ(X 1 ), . . . , Φ(X p ). Two facts or rules X and X are said equivalent (and we note X ≡ X ) iff X |= X and X |= X.

Since any fact F is equivalent to a rule (∅, F ), we can consider that a knowledge base (KB) is composed of rules. The general problems we address here can be stated as follows: given a KB, is its set of rules satisfiable (resp. valid) ? Given a KB and a rule R, is R a semantic consequence of the rules in the KB ? We respectively call these decision problems SATISFIABILITY?, VALIDITY? and DEDUCTION?.

Standard knowledge bases

We will now distinguish between different kinds of rules, and refine the above problems according to the kinds of rules that composes the KB. Definition 2 (Standard KBs) A standard fact is either a fact that contains only standard atoms or the absurd fact { }. A standard rule is a rule (H, C) where both H and C are non empty disjoint sets of standard atoms. A constraint is a rule of form (H, { }) where H is a non empty set of standard atoms. We note this constraint ¬H since Φ((H, { })) ≡ ¬Φ(H). An equality rule is a rule of form (H, {t =t }) where H is a non empty set of standard atoms and t, t are either two distinct variables in vars(H) or a constant and a variable in H. A standard KB is a KB that contains one standard fact, a set of standard rules, a set of constraints, and a set of equality rules. Property 1 (Standard KBs) Any rule KB is semantically equivalent to a standard KB.

Computing an equivalent standard KB takes linear time. From now on, we thus focus on standard KBs.

Depending on the kind of rules a (standard) KB contains, different logical fragments are obtained. Let us note F a standard fact, R a set of standard rules, E a set of equality rules and C a set of constraints. The fragment FRCE is obtained with KBs of form K = (F, R, E, C), it thus encodes the whole rules fragment (PROP. 1). More specific fragments are obtained by considering only some of the above sets (they are denoted by the names of the sets considered, e.g. the F-fragment or the FC-fragment). A short notation for "the problem P in the fragment f ", will be f -P , e.g. F-DEDUCTION?.

From deduction of rules to deduction of facts

The general deduction problem (which asks if a given rule can be deduced) can be reformulated as the deduction problem of a fact instead of a rule, as pointed out below.

Definition 3 (Substitution) A substitution is a mapping from a set V of variables to a set T of terms. Let σ : V → T be a substitution, and F be a fact. We note σ(F ) the fact obtained by replacing, for each variable x ∈ V ∩ terms(F ), each occurrence of x in F by σ(x). If R = (H, C) is a rule, we note σ(R) = (σ(H), σ(C)).

A safe substitution is a bijection from V to a set of new variables (i.e. that does not appear in the formulas involved in the reasoning). A freezing substitution is a bijection from V to a set of new constants.

Property 2 Let R be a set of rules, and R = (H, C) be a standard rule. Then R |= R iff σ(H), R |= σ(C) where σ is a freezing substitution of vars(H).

DEDUCTION? can be recast, without loss of generality, as "is a fact Q a semantic consequence of a standard KB?".

The Case of Constraints

Finally, to further bound the our investigation, and without loss of generality, let us consider the following properties:

Property 3 (Constraints) Let us consider a standard KB K containing a set C of constraints. Since no constraint is valid, K is valid iff C = ∅ and K \ C is valid. K is un- satisfiable iff K \ C is unsatisfiable or there is ¬H ∈ C such that K \ C |= H. Let Q be a fact, then K |= Q iff K is unsatisfiable or K \ C |= Q.
Semantic properties of a standard KB with constraints can thus be reformulated in terms of those of a standard KB without constraints. The next section is devoted to solving problems in FRE with a forward chaining mechanism.

Forward Chaining in FRE

We will first concentrate on the F fragment, which provides the basic mechanism for reasoning, namely homomorphism.Then we focus on reasoning with standard and equality rules, in a forward chaining framework.

Reasoning in F and FC

The problems F-SATISFIABILITY? and F-VALIDITY? are trivial: the only valid standard fact is the empty fact ∅ and the only unsatisfiable standard fact is the absurd fact { }.

Note that the computation of validity and satisfiability of facts was already included when computing the standard equivalent KB, but this computation took only linear time.

Solving F-DEDUCTION?, is based on a particular kind of substitution called a homomorphism (it is indeed a homomorphism, if we see facts as algebraic structures).

Definition 4 (Homomorphism) Let F and Q be two facts.

A homomorphism from Q to F is a substitution such that σ(Q) ⊆ F . Theorem 1 (F-DEDUCTION?) Let F and Q be two stan- dard facts. Then F |= Q iff F = { } or there is a ho- momorphism from Q to F .
Proof: This result is basically from (CM92) (soundness and completeness of the simple CGs homomorphism).

Deciding whether there is a homomorphism from Q to F is NP-complete. It becomes polynomial when Q has a structure decomposable into trees. More precisely, let FOL(∃, ∧) be the fragment of FOL composed of existentially closed, positive and conjunctive formulas, i.e. formulas corresponding to facts. Let k be a fixed positive integer. If in all problem instances, Q is in the k-variable fragment of FOL(∃, ∧), or equivalently if it has a treewidth less than k when seen as a graph, then homomorphism checking is polynomial (KV00). Similarly, if Q is a k-guarded formula, or equivalently if has a hypertreewidth bounded by k when seen as a hypergraph, then homomorphism is polynomial too (GLS01).

From PROP. 3 and the complexity of the decision problems in F, it follows that FC-VALIDITY? can be decided in linear time, FC-SATISFIABILITY? is co-NP-complete and FC-DEDUCTION? is NP-complete. Note that FC-SATISFIABILITY? and FC-DEDUCTION? become polynomial when we impose the same restrictions on constraints that the above-mentioned restrictions on Q.

Reasoning in FREC

Let us now consider reasoning in general standard KBs (thanks to PROP. 3, we can restrict that study to FRE).

Property 4 (Validity of standard and equality rules)

There is no valid equality rule. A standard rule (H, C) is valid iff σ(H) |= σ(C) where σ is a freezing substitution of vars(H) (this is indeed a particular case of PROP. 2).

As a consequence, FR-VALIDITY? is an NP-complete problem (and so is FR-VALIDITY?). It can be solved in linear time when there is no standard rule in the KB.

Definition 5 (Application of a rule) Let F be a standard fact and R = (H, C) be a standard rule or an equality rule. Then R is applicable to F iff there is a homomorphism σ from H to F . The application of R on F according to σ produces a standard fact α(F, R, σ) (called an immediate derivation of F ) built as follows: if R is a standard rule, then α(F, R, σ) = F ∪ σ(σ (C)) where σ is a safe substitution of vars(C) \ fr(R); and if R is an equality rule, then either a variable (say t) of the equality t =t is mapped by σ to a variable, or none is. In the first case, α(F, R, σ) = σ (F ), where σ is the substitution from {σ(t)} that maps σ(t) to the constant a if t = a, and to σ(t ) otherwise. In the second case, if

σ(t) = σ(t ) or σ(t) = t , then α(F, R, σ) = F , otherwise α(F, R, σ) = { }.
Definition 6 (Derivation) Let F and F be two standard facts, and R be a set of standard and equality rules. F is called an R-derivation of F if there is a finite sequence (called the derivation sequence)

F 0 = F, F 1 , . . . , F k = F of standard facts such that ∀1 ≤ i ≤ k, there is a rule R = (H, C) ∈ R and a homomorphism σ from H to F i-1 with F i = α(F i-1 , R, σ).
Since standard rules cannot yield unsatisfiability:

Property 5 (FRE-SATISFIABILITY?) A FR KB is unsat- isfiable if and only if F = { }. A FRE KB (F, R, E) is unsatisfiable iff { } is an (R ∪ E)-derivation of F . Theorem 2 (FRE-DEDUCTION?) Let K = (F, R, E) be a FRE KB, and Q be a standard fact. Then K |= Q iff there is a homomorphism from Q or { } to a (R ∪ E)-derivation of F .
If Q is a semantic consequence of the KB K = (F, R, E), then a breadth-first exploration of all possible rule applications will necessarily generate either the absurd fact (when we have deduced that two constants are equal, which is absurd due to the unique name assumption) or a standard fact containing an answer to Q. No sound and complete algorithm, however, is ensured to stop on all negative instances of the problem: FRE-DEDUCTION? is a semi-decidable problem (see in particular (BM02)).

As a consequence, FRE-UNSATISFIABILITY? is also semi-decidable, and thus FRE-SATISFIABILITY? is undecidable. Note that, since the application of an equality rule either merges two variables or replaces a variable by a constant, an E-derivation has a length less than |terms(F )|. Thus both FE-DEDUCTION? and FE-SATISFIABILITY? are NP-complete problems (and so are FEC-DEDUCTION? and FEC-SATISFIABILITY?).

Decidable subclasses of FRE-DEDUCTION?

Since the satisfiability and deduction problems are no longer decidable as soon as standard rules are involved, finding decidable cases, as expressive as possible, is extremely important. We recall below definitions and results from (BM02), which are adapted to include equality rules (see the section about related works for more details). A set of rules is called a finite expansion set if it is guaranteed for any fact that after a finite number of rule applications, all further rule applications will become redundant. More precisely:

Definition 7 (Finite expansion set and full derivation) A set of standard or equality rules R is called a finite expansion set iff for any standard fact F , there is a R-derivation F of F s.t. for every rule R = (H, C) ∈ R, for every homomorphism σ from H to F , there is a homomorphism from α(F , R, σ) to F (called a full R-derivation of F ).

If R ∪ E is a finite expansion set, then a forward chaining algorithm that checks whether a rule has effectively added non redundant information and stops when all rule applications produced redundancy is still complete, and is ensured to stop in finite time. This algorithm effectively produces a standard fact that contains all information that can be deduced from F . However, finite expansion sets are an abstract characterization of such a behavior, that does not help us to predict that forward chaining will effectively stop (note, moreover, that all decidable subclasses of the problem do not rely upon finite expansion sets). As a concrete example of finite expansion sets, let us cite the range restricted rules, used in particular in positive Datalog, that do not generate any new variable (i.e. standard rules (H, C) such that vars(C) ⊆ vars(H)) and disconnected rules (standard rules R such that fr(R) = ∅). As stated above, a set of equality rules is also a finite expansion set. Note that the union of two finite expansion sets is not necessarily a finite expansion set ((BM02) shows that any Turing machine can be encoded by a set of range restricted and disconnected standard rules).

(BM02) proves that if standard rules are restricted to either range-restricted rules or disconnected rules, FR-DEDUCTION? is NP-complete (provided that the arity of predicates is bounded by a constant). We have shown here that the same result holds for equality rules. It follows that, assuming the same restrictions, FREC-DEDUCTION? and FREC-SATISFIABILITY? are also NP-complete.

The forward chaining paradigm is used to define finite expansion sets and characterize some decidable subclasses of FREC-DEDUCTION?. The backward chaining paradigm that we present now allows for a new characterization of decidable subclasses, namely finite unification sets.

Backward Chaining in FR

A backward chaining mechanism is generally based upon a unification operation, that matches part of a current goal with a rule conclusion. This mechanism is typically used in logic programming, where rules have a conclusion restricted to one literal. Since standard rules have a more complex conclusion, the associated unification operation is also more complex. It relies on the piece notion (which stems from a graph vision of rules (SM96)).

Definition 8 (Cut points, Pieces) Let F be a fact and T ⊆ terms(F ). A piece of F according to T is a subset of F recursively defined as follows: two atoms p and q are in the same piece iff either (vars(p) ∩ vars(q)) \ T = ∅; or there is an atom r ∈ F such that p and r are in the same piece and r and q are in the same piece. The cut points of a rule R = (H, C) is the set of terms cutp(R) = fr(R)∪consts(C). A piece of R is a piece of C according to cutp(R).

A piece notion represents a "unit" of knowledge brought by a rule application. As expressed below, a rule R can be decomposed into an equivalent set of rules with exactly one piece in conclusion.

Property 6 The conclusion of standard rule R = (H, C) can be partitioned into k pieces C 1 , . . . , C k . R is semantically equivalent to the set {(H, C i )} 1≤i≤k .

Rewritings in FR

The definitions and results concerning rewritings presented hereafter are a reformulation of those of (SM96).

Definition 9 (Unifier) Let Q be a standard fact and R = (H, C) be a standard rule.

A unifier of Q with R is a tuple µ = (T Q , Q , σ Q , σ C ) where: • T Q is a subset of terms(Q),
and Q is a fact composed of all atoms in one or more pieces of Q w.r.t.

T Q ; • σ Q is a substitution from the variables of T Q to consts(C) ∪ T Q and σ C is a substitution from fr(R) to consts(C) ∪ T Q ; • there is a homomorphism σ from σ Q (Q ) to σ C (C) s.t. for all t ∈ T Q , there is t ∈ cutp(R) with σ(σ Q (t)) = σ C (t ).
Definition 10 (Rewriting of a fact) Let Q be a standard fact, R = (H, C) be a standard rule, and µ =

(T Q , Q , σ Q , σ C ) be a unifier of Q with R. The rewriting of Q according to R and µ produces a fact β(Q, R, µ) = σ (σ C (H)) ∪ σ Q (Q \ Q ),
where σ is a safe substitution from vars(H) \ fr(R).

The two following lemmas state the precise relationships between an immediate derivation and a rewriting. Lemma 1 Let µ be a unifier of a standard fact Q with a standard rule R = (H, C). Then there is a homomorphism σ from H to F = β(Q, R, µ) such that there is a homomorphism from Q to α(F, R, σ). Lemma 2 Let us consider a standard rule R, and F, F and Q three standard facts such that F = α(F, R, σ) and there is a homomorphism from Q to F that is not a homomorphism from Q to F . Then there is a unifier µ of Q with R such that there is a homomorphism from β(Q, R, µ) to F .

These lemmas are used to prove inductively (on the length of the derivation / rewriting) that a derivation sequence and a rewriting sequence encode the same reasoning in FR. Definition 11 (Rewriting sequence) Let Q and Q be two standard facts, and R be a set of standard rules. We say that Q is a R-rewriting of Q iff there is a finite sequence (called the rewriting sequence)

Q 0 = Q, Q 1 , . . . , Q k = Q such that ∀1 ≤ i ≤ k, there is a rule R = (H, C) ∈ R and a unifier µ of Q i-1 with R such that Q i = β(Q i-1 , R, µ).
Property 7 Let F and Q be two facts, and R be a set of standard rules. Then there is a R-rewriting Q of Q and a homomorphism from Q to F iff there is a R-derivation F of F and a homomorphism of Q to F .

Then , as a direct consequence of the previous property: Theorem 3 (Backward Chaining in FR) Let K = (F, R) be a FR KB, and Q be a standard fact. Then F, R |= Q iff there is a R-rewriting Q of Q such that there is a homomorphism from Q to F .

Note that using backward chaining to check the unsatisfiability of a KB K = (F, R, C) requires to check whether the hypothesis of a constraint can be deduced from (F, R).

Though we could define a unifier that takes equality rules into account, both space requirements as well as the inefficiency of the obtained algorithm led us to take only standard rules into account in this backward chaining framework.

Finite unification sets

Finite expansion sets are used to ensure that all information deducible from a fact in forward chaining can be encoded in a finite standard fact computed in finite time. The finite unification sets we present hereafter are used to ensure that only a finite number of rewritings will be necessary in backward chaining. Definition 12 (Finite unification sets) A set of standard rules R is said a finite unification set (f.u.s.) iff for every fact Q, there is a finite set Q of R-rewritings of Q such that for any Q ∈ Q, for any rule R ∈ R, for any unifier µ of Q with R, there is a homomorphism from a fact in Q to β(Q , R, µ). We say that Q is a full R-rewriting set of Q.

If the set of standard rules involved is a f.u.s., then the backward chaining algorithm that does not rewrite facts more specific than those that have already been explored is still complete and is ensured to stop in finite time. Similarly to f.e.s., f.u.s. provide an abstract characterization, that should be instantiated with concrete examples. We introduce in this paper two kinds of f.u.s.: the atomic hypothesis rules, and the domain restricted rules.

Definition 13 (Atomic hypothesis rules) A standard rule R = (H, C) is called an atomic hypothesis rule (a.h.) if H contains only one (standard) atom.

Property 8 A set of atomic hypothesis rules is a f.u.s.

Proof: See that for any standard fact Property 9 A set of domain restricted rules is a f.u.s.

Q, if R = (H, C) is a.h., and µ = (T Q , Q , σ Q , σ C ) is a unifier of Q with R, then |Q| ≥ |β(Q, R, µ)| (
Proof: Let us call k-limited fact, a fact Q such each piece P of Q according to consts(Q) is such as |vars(P )| ≤ k.
There is a finite number N of facts with at most k variables (up to a variable renaming), and a bounded number of constants and predicates. Thus, a k-limited fact containing more than N pieces contains equivalent pieces which can be removed to obtain a fact with at most N pieces. We observe that if a rewriting according to a d.r. rule produces a new variable, then it also produces a new piece which is the only piece containing this variable. Indeed, either the unifier concerns an atom that contains all variables of H and it does not generate new variables, or it creates a new piece. Thus if R contains only d.r. rules, the number of R-rewritings of Q without duplicate pieces is bounded by N .

Since the number N involved in the previous proofs is polynomial w.r.t. the size of the knowledge base (provided that the arity of all predicates is bounded by a constant), then the restrictions of FR-SATISFIABILITY? and FR-DEDUCTION? to knowledge bases containing either a.h. or d.r. rules are NP-complete problems.

The graph of rules dependencies

Both f.e.s. and f.u.s. allows to characterize decidable subsets of the rule fragment of FOL by checking independently on each rule if they verify some properties. We now present the graph of rules dependencies as a mean to explore new decidable subsets by studying the structure of the interactions between these rules.

Let us rephrase lemma 1. Its converse means that if R is a standard rule and there is no unifier of a fact Q with R, then the set of homomorphisms from Q to any fact F and the set of homomorphisms from Q to α(F, R, σ) are the same. In other words, there is no need to check the applicability of a rule (H, C) at a point of the forward chaining algorithm when there is no unifier of H with a rule that produced new information during a previous step of the algorithm. Moreover, as shown in (Bag04), an off-line computation of unifiers allows us not only to reduce the number of applicability checks during the execution of forward chaining, but also to reduce the search space for the remaining ones.

We define the graph of rules dependencies as a structure that encodes all necessary information to take advantage of the above-mentioned property in forward chaining. It allows us to compute a smaller number of rules application checks, and to compute these checks more efficiently. In this paper, however, we focus the structural properties of this graph leading to new decidability results in FREC.

F.e.s., f.u.s., and the graph of rule dependencies Definition 15 (GRD) Let R be a set of standard rules. The graph of rules dependencies of R, noted GRD(R) is a directed labeled graph whose vertices are the rules of R and whose arcs are the couples (R, R ) such that there is a unifier of the hypothesis of R with R.

Property 10 Let R be a set of standard rules such that GRD(R) contains no circuit. Then R is a both a finite expansion set and a finite unification set.

Proof: The f.e.s. part of that property has been proven in (Bag04). The f.u.s. is an immediate consequence of a property exposed in (BS06): if there is an unifier µ of R with Q = β(Q, R, µ) such that β(Q , R , µ ) is not a rewriting of Q according to R , then there is an unifier of the hypothesis of R with R . In other terms, to rewrite β(Q, R, µ), we only have to explore the predecessors of R in the GRD.

Note that a loop (a self-unifiable rule) in the GRD is considered as a circuit, and is sufficient to yield undecidability. Indeed, it has been shown in (Bag01) that a KB containing a single rule can encode a universal Turing machine.

Finite expansion sets and finite unification sets relied upon the structural properties of the rules themselves to ensure decidability. PROP. 10 relies upon the structure of possible interactions between all rules appearing in the KB. The next theorem presents a generalization of both approaches (and is proven in (Bag04) for the f.e.s. part, while the f.u.s. part is a similar extension of PROP. 10):

Theorem 4 Let K = (F, R) be a KB such that all strongly connected components of the graph GRD(R) are finite expansion sets (resp. finite unification sets). Then R is a finite expansion set (resp. finite unification set).

Note that a strongly connected component restricted to a single rule, and without loop, is both a f.e.s. and a f.u.s.

F.e.s and f.u.s respectively rely upon forward and backward chaining to achieve finite reasoning mechanisms. Let us now present a combined algorithm that is ensured to stop on more general subclasses of the deduction problem.

Property 11 Let R 1 and R 2 be two sets of standard rules such that there is no arc from a rule of R 2 to a rule of R 1 in GRD(R 1 ∪ R 2 ). Let F and Q be two standard facts. Then

F, R 1 , R 2 |= Q iff there is a standard fact F such that F, R 1 |= F and F , R 2 |= Q.
Definition 16 (Finitely combined sets) A partition (R 1 , R 2 ) of standard rules is said to be finitely combined if R 1 is a f.e.s., R 2 is a f.u.s., and there is no arc from a rule of R 2 to a rule of R 1 in GRD(R 1 ∪ R 2 ). A finitely combined set is a set of standard rules that admits a finitely combined partition.

Theorem 5 (FR combined scheme) Let (R 1 , R 2 ) be a finitely combined partition of standard rules, and F and Q be two standard facts. Then

F, R 1 , R 2 |= Q iff there is a ho- momorphism from Q to F , where F is a full R 1 -derivation of F and Q belongs to a full R 2 -rewriting set of Q.
As a consequence, FR-DEDUCTION? is decidable when standard rules are restricted to finitely combined sets.

Adding constraints and equalities

It follows from PROP. 3, that FRC-SATISFIABILITY? and FRC-DEDUCTION? are decidable when the problems are restricted to finitely combined sets of standard rules.

Let us now consider a mixed FC/BC scheme that takes equality rules into account in its forward chaining phase.

Theorem 6 (FRE combined scheme) Let (R 1 , R 2 ) be a finitely combined partition of standard rules, E be a set of equality rules such that for every equality rule (H, {t =t }) ∈ E, H only unifies with range restricted rules of R 1 , and F and Q be two standard facts. Then

F, R 1 , R 2 , E |= Q iff there is a homomorphism from Q to F , where F is a full R 1 ∪ E-derivation of F and Q belong to a full R 2 -rewriting set of Q.
In that case, FRE-DEDUCTION?

and FRE-SATISFIABILITY? are decidable, and it follows, thanks to PROP. 3, that FREC-SATISFIABLITY? and FREC-DEDUCTION? are also decidable.

Relationships to other formalisms

This section details the relationships between our rules and other notions in other formalisms. It indicates how our results extend known results and explains what the potential benefit of our results could be for these related formalisms.

Clauses and rules

A clause (without function symbols) is a logical formula of form ∀x 1 . . . ∀x k (N ∨ ∨ P ∨ ) where P ∨ is a disjunction of atoms, N ∨ is a disjunction of negated atoms, and x 1 , . . . , x k are the variables appearing in P ∨ and N ∨ . Such a formula is trivially equivalent to the formula: ∀n 1 . . . ∀n k (N ∧ → (∀p 1 . . . p q P ∨ )) where N ∧ is the conjunction of the atoms appearing in N ∨, the n i are the x q appearing in N ∨ and the p j are the x q appearing in P ∨ but not in N ∨ . This rewriting points out the difference between clauses and rules: they have the same "hypothesis", but the conclusion of our rules is an existentially quantified conjunction, while the "conclusion" of a clause is an universally quantified disjunction. Note that a formula F = ∀x 1 . . . ∀x q (H ∧ → C) is both a clause and a rule when C contains only 0 or 1 positive atoms, and all variables of C appear in H ∧ . The intersection of rules and clauses can thus be characterizes as "range restricted Horn clauses".

Another interesting subset of rules, that we name atomic conclusion rules, is restricted to rules having at most one atom in their conclusion. This subset has the same expressivity as the general rule fragment: any standard rule R = (H, C) can be encoded by an equivalent set of atomic conclusion rules {(H, A = {R(t 1 , . . . , t k )}), (A, {A q })} Aq∈C where the predicate R is associated to the rule R and the t i are the terms of C. An immediate question arises: why study these general rules, since unifiers with atomic conclusion rules are (i) well known, and (ii) much simpler. Our answer is that the GRD of these equivalent formulas contains more arcs, encoding "fake" unifications, and thus leads to more restricted decidable fragments, as shown by the following example. Consider the standard rule R = (H, {p(x, y), q(y, z)}) where (R) = {x} and the fact Q = {s(x, y), q(y, z)}. There is no unifier, according to our definition, of Q with R. Let us consider now the equivalent set of rules {R 1 , R 2 , R 3 } where R 1 = (H, {R(x, y, z)}), R 2 = ({R(x, y, z)}, {p(x, y)}) and R 3 = ({R(x, y, z)}, {q(y, z)}). In the GRD, there is an arc from R 1 to R 2 and R 3 , and there exists a unifier of Q with R 3 . Indeed, we have lost the information that R 2 and R 1 cannot be applied independently.

Tuple-Generating Dependencies in Databases

The rules studied in this paper correspond to the logical translation of generalized dependencies in databases, namely Tuple Generating Dependencies (TGDs) and Equality Generating Dependencies (EGDs), which provide of uniform way of expressing most of the database dependencies (AHV95). More precisely, the logical translation of a TGD is a standard rule, and the logical translation of an EGD is an equality rule. The only notable difference is that TGDs and EGDs have no constants.

A fundamental problem for these generalized dependencies is the implication problem. This problem takes a set of generalized dependencies S and a generalized dependency t as input, and asks if every database instance that satisfies S also satisfies t, i.e., in logical terms, if S |= t. It is processed by the so-called chase procedure, which was proven sound and complete with respect to semantics of dependencies in (BV84). This procedure can be identified with our forward chaining mechanism when t is a TGD. The backward chaining can be seen as an alternative to the chase (as proposed in (Cou03)). The rule dependency graph studied in this paper can be used to improve the chase. It would be interesting to study the properties of the dependency graph depending on the specific kinds of dependencies taken into account and compare the decidability results obtained to those already known.

  since the rewriting removes the non empty Q and adds a specialization of the unique atom in H). There is a bounded N number of facts (up to a variable renaming) of size ≤ |Q| built from the bounded number of constants and predicates appearing in the KB. Thus if R contains only a.h. rules, the number of R-rewritings of Q is bounded by N . Definition 14 (Domain restricted rules) A standard rule R = (H, C) is called a domain restricted (d.r.) rule if each atom of C contains all or none of the variables of H. Note that d.r. rules strictly generalize the class of disconnected rules, since d.r. rules with fr((H, C)) = vars(H) = ∅ are not disconnected.

Conceptual Graphs

Conceptual graphs have been presented in (Sow76) as a graphical interface for databases. Indeed, the formulas we have studied here admit a very intuitive graph encoding, where terms are labeled vertices of the graph and atoms are represented by labeled hyperarcs whose ends are the argument of the predicate. Semantic consequence between facts (called simple CGs) is computed by a graph homomorphism, hence the name of our elementary operation. We have developed most results presented in this paper under this graph paradigm, and the family of conceptual graphs languages presented in (BM02) is closely related to the family presented here. Indeed, the basic CG language SG encodes standard facts (without equality) and standard rules of form ({p(x 1 , . . . , x n }, {p (x 1 , . . . , x n }) that are used to encode hierarchies of types. The language SGC further adds constraints, that can be positive or negative. Negative constraints correspond to the constraints presented here, while the essentially non-monotonic positive constraints cannot be represented by rules. Finally, the language SRC also consider rules that are equivalent to the standard rules presented here. The rule fragment of logic FRC can thus be identified with the CG language SRC -restricted to negative constraints. Note that FREC can also be encoded in SRC -, a language that does not include the unique name assumption.

Finally, note that the main difference between these CG languages and the logic of rules is that CGs consider rules encoding type hierarchies (typing rules) as different objects, with a algorithmic specific role. By example, our definition of homomorphism becomes: "a substitution σ such that for every atom p(t 1 , . . . , t k ) ∈ Q, there is an atom p (t 1 , . . . , t k ) ∈ F with p ≤ p in the type hierarchy and ∀1 ≤ i ≤ k, σ(t i ) = t i ". This allows for a compilation of type hierarchies, optimizing the search for substitutions. Type hierarchies are integrated in the same way in unifiers, effectively removing from the GRD circuits formed of typing rules, that do not correspond to an increase of the complexity of the deduction problem. Similarly, forbidden types encode constraints of form ¬{p 1 (x), . . . , p k (x)}. They are used to reduce the number of unifiers of a fact with a rule.

Description logics

We intend to use our results in the rules fragment of FOL to study the deduction problem in logic-based knowledge representation languages. Our general approach can be stated as follows: consider a language L, such that there exists a transformation τ L from the expressions of L to standard facts and constraints, and a fixed set of standard and equality rules R L such that for all expressions L, L

Assuming we can obtain such an encoding of the language L, we can study the properties of that language by studying the properties of GRD(R L ). Sometimes such an encoding cannot be obtained, but a weaker form may still be found, when there exists a transformation τ L from the expressions of L to rules such that L 1 , . . . , L k |= L L iff τ L (L 1 ), . . . , τ L (L k ), |= τ L (L). In that case, the GRD does not provide us with properties of the language, but of the specific instance we have transformed. This latter method was recently applied in (BLMS08) to study particular subsets of description logics (BCM + 03), namely DL-Lites (CGL + 05; CGL + 07). In particular, the GRD obtained was sufficient to prove the FOL-reducibility of a specific DL-Lite. That FOL-reducibility property can be stated as follows: there exists a transformation ρ that maps each standard fact to a finite set of database conjunctive queries and a linear transformation δ that maps each KB to a relational database instance such that, for any KB K, for any standard fact Q, K |= Q if and only if δ(K) contains an answer to one of the queries in ρ(Q). Since homomorphisms in F are equivalent to the answering of positive, conjunctive queries in database, it follows that if the set of rules encoding the semantics of our problem is always a finite unification set (or, more generally, a finitely combined set whose f.e.s. subset of rule generates a full graph in linear time), then the deduction problem in the studied language is FOL-reducible. In order to study more expressive DL-Lites, equality rules were required: they will allow, by example, to encode functional roles by adding the rule ({R(x, y), R(x, z)}, {y =z}) for each functional rule R.