Tayeb Lemlouma
email: tayeb.lemlouma@irisa.fr

Julien Luciana
email: jluciana@centile.com

Bastien Oza
email: bastien.oza@logicielnet.com

Leandro Sierra
email: leandrosierra1@gmail.com

Mikaël Salun
email: mikael.salaun@univ-rennes1.fr

An Easy Cellular Gateway for Providing Shared Services and Data

Keywords: services sharing, data sharing, mobile terminal, cellular networks, wirless gateway I

In this paper, we present a new framework that links the two worlds of wired and cellular users sharing systems. The approach is to propose an easy gateway that enables the use of cellular networks based services by wireline users and applications. The idea is to use a mobile terminal or wireless equipment for sharing cellular services, available thanks to its cellular network, to other users that use the wireline Internet. The software application acts as a gateway between the cellular and the wired network; it is responsible for supporting the services provided by the wireless network and make them accessible and usable, in a standard and easy way, by anyone on the wireline network. The gateway software can be integrated easily on any complex architecture since it can interact with any cellular modem. The paper describes an implementation prototype where some examples of services, such as the ability of using messaging services and calls streaming, are experimented. The proposed platform combines different standards to guarantee the use of our gateway in heterogeneous environments.

INTRODUCTION

During last years, peer-to-peer (P2P) networks and sharing systems gained tremendous attention and popularity within both industry and academia. In wireline networks, content sharing environments enable Internet users to share any kind of content in a simple and free way. On the other hand, the use of small and mobile communications devices such as mobiles phones, smart phones and PDA's has gained momentum in our life. P2P computing and networking has been thoroughly studied in the literature either among classical users or mobile users (mobile P2P) [START_REF] Wang | Peer to Peer Overlay Networks: A Survey[END_REF][2][3][4] [START_REF] Bisignano | JMobiPeer: A Middleware for Mobile Peer-to-Peer Computing in MANETs[END_REF]. If sharing data has made successes in wireline networks and generates a traffic that has been dominating the Internet, implementing P2P within wireless environments still faced to many challenges: starting from the question about the real need of sharing content that is often self created and privately consumed [START_REF] Matuszewski | Understanding Attitudes Towards Mobile Peer-to-Peer Content Sharing Services[END_REF] and ending with the difficulties of implementing mobile P2P services. Such limitations are the complexity of cellular network architectures and the limitations of the bandwidth especially for uplink even within 3G networks. Moreover, even for wired or cellular networks, most of P2P applications are only single-service based where generally the only capability is the popular file sharing.

This paper describes a gateway framework for building mobile information sharing services. We propose an easy gateway based on cellular network services. The basic elements of the proposed architecture is composed of: 1) a wireless modem supporting 2G to 3G networks, 2) a set of exploitable services and 3) a software application that makes these services shared between the mobile terminal and users connected through the wireline network. The wireless modem can be used, e.g., by the mean of a simple mobile phone or a personal assistant device but also by the mean of professional equipment such as a cellular modem. One of the fixed requirements was that such gateway must be easy to integrate, do not need a high significant investment for the end user or application and could be used in heterogeneous environments. The objective of the implemented services, offered by the gateway, is to make them controlled and accessible for users whatever their locations. This enables users of the wired network to gain access to typically cellular services such as joining other mobile users using SMS/MMS messaging. Another use case of our gateway is to make a user's own data accessible from everywhere and anyhow even using a simple Internet connection. Data could be also shared between users exactly like in a classical P2P networks. Here, the particularity is that the data come from the mobile terminal and the wired (not the cellular) network is used for data sharing unlike mobile peer to peer approaches. Web services are used to make the gateway exploitable by any application in a standard way. Such applications could, for instance, offer online messaging services and calls with attractive costs.

The rest parts of this paper are organized as follows. Section II introduces the architecture overview. Section III presents our implementation of the proposed gateway; Section IV presents the implemented services. Finally, Section V presents our conclusion and perspectives.

II. ARCHITECTURE OVERVIEW

The objective of our implemented prototype is to provide a gateway based on cellular networks (up to the third generation) and that can be used by users connected over the wired network. An example of services that the gateway provides is the capability to handle messaging functionalities (such as short message service -SMS, multimedia messaging service -MMS) and calls. In order to implement these services in an easy way, the following components are required (Figure 1): the application gateway that can be used by a distant user or application through Web services, the terminal equipment (TE) equivalent to the Data Terminal Equipment-DTE, a terminal adaptor (TA), e.g., a GSM data card (equivalent to the Data Circuit terminating Equipment-DCE) and a mobile equipment (ME) such as a 3G mobile phone (equivalent to the Mobile Station-MS) with its Mobile Termination (MT) that performs radio and network functions (RT and NT respectively).

The proposed gateway can be set up on any server machine and remotely used by any authorized user after a required authentication 1 . During the experimentations of our prototype, a cellular modem is connected to the gateway server using a Bluetooth connection. The communication, between the gateway's application and the modem, is also supported using the physical COM port. In order to open the use of the provided services to a large community of users and applications, services are accessible using Web services technology. In addition to the basic services of sending and receiving SMS, MMS and managing calls originated by (or in destination to) the user, the prototype implements, using a set of dedicated modules, other functionalities such as memory data sharing, remote modem's monitoring and a particular application of video surveillance. The interfacing between the different modules that implements the services and the gateway is done using an implemented interface called Mobile Service Agent.

III. IMPLEMENTATION

In order to experiment our platform, we have implemented a set of services using some GSM/GPRS modems. The modular implementation of the exchange between the cellular modem and the application gateway makes easier to interact with any cellular modem since the modem's control is based on standard AT commands. So any other generations of cellular network such 3G+ or 4G could be easily exploited if we want to enrich the set of supported services. However, during our experimentations, we have noticed that some cellular modems do not recognize some standard commands which implied the use of additional manufacturer commands specific to the modem model. The use of non standard manufacturer commands could be used also for developing advanced services that can not be implemented with standard commands and to optimize some 1 Security issues are left out of the scope of this paper.

functionalities by new native commands such as supplying efficient and error free TCP/UDP transport mechanisms using the AT interface [START_REF]Using AT commands to control TCP/IP stack on GR47/GR48[END_REF].

A. Web Services

The prototype implements a SOAP server (using a set of Java Servlets) executed on a Tomcat web server and communicates over the underlying protocol. SOAP is a lightweight protocol, defined by the W3C, intended for exchanging structured information in a decentralized, distributed environment [START_REF]SOAP/1.1 and SOAP Version 1.2[END_REF]. The latest SOAP W3C recommendation includes, mainly, the definition of an extensible messaging construct that can be exchanged over many underlying protocols (specification's part 1 [START_REF]SOAP Version 1.2, Part 1: Messaging Framework (Second Edition)[END_REF]) and a set of adjuncts that may be used by the messaging framework (specification's part 2 [START_REF]SOAP Version 1.2, Part 2: Adjuncts[END_REF]). In our case, the binding or carrying SOAP messages with the underlying protocol is based on the HTTP binding in SOAP 1.2-part 2 [START_REF]SOAP Version 1.2, Part 2: Adjuncts[END_REF] with respect to the binding specification's discussed in Chapter 4 of [START_REF]SOAP Version 1.2, Part 1: Messaging Framework (Second Edition)[END_REF]. From the many existing implementations of the HTTP binding, we have tested -on the server side-the implementations presented in Table 1. Tests are based on the Sun Microsystems WSTest [START_REF]Web Services Performance Comparing Java 2 Enterprise Edition (J2EE platform) and .NET Framework[END_REF] and the guidelines of [START_REF] Davis | Latency Performance of SOAP Implementations[END_REF] to exclude: the TCP setup time, the time required for getting the response to a Servlet request of Tomcat/Microsoft IIS server, etc. For testing, we have used two hosts on the same switched 100 Mbps Ethernet LAN (only the two hosts are joined via a Cisco Switch): Desktop with a Pentium(R) 4 CPU 2.66 GHz processor and 256 MB RAM using Windows XP Professional, version 2002 -SP3 running as a client. A Laptop with an Intel(R) Core(TM) 2 Duo T7500 2.20 GHz processor and 2 GB RAM using Windows XP Professional 2002 -SP3 running as a server. We adopted the Web Services (Apache)-AXIS implementation [START_REF]Apache Project, Web Services -Axis[END_REF] within the Tomcat server for its stability, supported features and its easy integration within our prototype.

The interface and modules were implemented using Java APIs in order to perform the serial/Bluetooth communication between the gateway component's server and the cellular

Gateway

TA ME(+MT) TE

Commands Control

Responses Status Cellular Networks

Web Services

Users/Applications modem. Audio stream is handled in the Bluetooth session using the serial communication class. Our prototype includes data processing and session opening and managing. Moreover, the prototype is enriched by the capability to read and modify the data exchanged between the cellular modem and the application components and to handle the errors. Theses capabilities are available for all the implemented services supported by the gateway. Note that the use of a Bluetooth communication mode between the gateway application and the modem, requires supporting the driver which is specific to the Bluetooth material in order to initialize the virtual COM port used in the communication exchange from and to the cellular modem.

B. AT Commands

Except the initialization and the stream supervision of the communication within the cellular modem, modem operations are performed using a set of AT commands. The two characters "AT" comes from "ATtention"; this abbreviation prefixes all the commands line sent from terminal equipment (TE) to the terminal adaptor (TA). AT commands are used for carrying out several functions related to the mobile equipment capabilities and cellular network services [START_REF]Serial Asynchronous Automatic Dialling and Control[END_REF][16] [START_REF]Third Generation Partnership Project, AT Command Set for GSM Mobile Equipment (ME)[END_REF]. The control is achieved through the terminal adaptor. The network services may concerns any kind of services such as GSM/UMTS messaging, fax transmission, voice set-up and operations, wireless communications services, etc. Some of AT commands are defined such way that they can be easily applied to mobile termination of networks other than GSM/UMTS.

AT commands are standardized in the 3rd Generation Partnership Project (3GPP) specifications [START_REF]Third Generation Partnership Project, AT Command Set for User Equipment (UE), Technical Specification Group Core Network and Terminals[END_REF] [START_REF]Third Generation Partnership Project, AT Command Set for GSM Mobile Equipment (ME)[END_REF] produced by the CT1 working group [START_REF]Third Generation Partnership Project, Specification Groups[END_REF]. The ITU-T Recommendation V.250 [START_REF]Serial Asynchronous Automatic Dialling and Control[END_REF] includes AT codification and a definition of a format for orderly extension of the AT command set. In order to perform an operation, the prefix AT followed by a command string is sent through the physical/emulated serial port to the mobile's modem and is executed on receipt of carriage return CR. A result code is sent from the terminal equipment and indicates the response after the execution of the AT command. For example, the command AT+CREG? confirms whether the cellular modem is connected to the cellular network or not. The command AT+CSQ indicates the signal strength; it returns received signal strength indication (RSSI) and channel bit error rate (BER).

As said before, in our system, we have also used additional manufacturer specific commands (SSTK commands). The standard and specific used commands interrogate the cellular modem in order to exploit the cellular network possibilities (services) and achieve a specific action for a service proposed by the gateway. ASCII is the format of command content and each command can return a result code. For example the command +CHUP allows answering a call received by the modem and AT+CGMI allows retrieving the identifier of the mobile. For the service of managing the calls that a user of the wired network can use through our gateway component, an audio tunnel is used between the TE and our server gateway. This tunnel allows sending and receiving the audio stream from the TE and is transported using the RTP protocol. The gateway components allow the interaction with the cellular modem. For example, our gateway can initiate a call; send textual or multimedia messages using the selected cellular network. To discover and publish the available services available by the mobile terminal node, the gateway can publish available and personalized public services that are implemented. For compatibility reasons, the gateway component extracts all the possible options for a given cellular modem using a standard AT command that gives the list of supported operations of the modem. Available commands can be used in public services that are configured to be shared with other nodes of the network.

To implement a way in which the mobile can communicate with the gateway we were mainly based on the Java Communications API (also known as javax.comm) [START_REF]Sun Java Communications 3.0 API[END_REF] and Visual Basic API MSCOMM [START_REF]Visual Basic: MSComm Control[END_REF]. The first API, used in the major part of our prototype, facilitates developing platform-independent communications applications for technologies such as smart cards, embedded systems, modems, etc. It provides applications access to RS-232 hardware (serial ports) and limited access to IEEE-1284 (parallel ports) in the Standard Parallel Port (SPP). Similarly, MSCOMM handles serial communications for MS environments. The communication Java class handles the communication between the cellular modem and the other modules. It handles the different sessions: opening/closing and managing sessions, read/write methods and listening to a given port. The communication class can be used by any independent module in the prototype. An event listener is implemented in order to handle all the extern events that come from the cellular network. Such events could be textual/multimedia messages notifications, calls notifications or other notification regarding personalized services that use the cellular network. The listener implementation is based on the SerialPortEventListener interface.

IV. IMPLEMENTED SERVICES

Our prototype implements the following services:

A. Short Message Service (SMS)

Within a GSM/UMTS mobile terminal, there are three kinds of interface protocols for controlling the SMS functions using an asynchronous interface: Block mode, Text mode and PDU mode [START_REF]Third Generation Partnership Project, Use of Data Terminal Equipment -Data Circuit Terminating Equipment (DTE -DCE) Interface for Short Message Service (SMS) and Cell Broadcast Service (CBS)[END_REF]. In the Block mode, SMS functions are controlled using binary data in a synchronous way. Each message exchanged between the MT (of the ME) to the TE consists of a data block and block check sum (BCS). Using this mode implies that the control will remain within that mode until the procedure for exiting the mode is executed, after which control is returned to the asynchronous command state. This means that the mobile terminal will not be available for other functions such as voice or data calls until this mode is terminated. Due to theses disadvantages and to the induced complexity, the Block mode is rarely used in practice and is not supported in our implementation.

We have considered both the Text and the PDU mode which are based on AT commands. The Text mode operates in a character-based way: data and SMS parameters are transmitted directly as character strings without the need of additional coding. The PDU mode is based on the same AT commands as the Text mode. It uses the TPDU (Transport Protocol Data Unit) to encode each character in hexadecimal rather than a raw binary format used in the Block mode. In the PDU mode, a complete SMS Message including all header information (such as receiver's number, validity period, etc.) is passed as a binary string while in Text mode the headers are input separately.

Table II presents some AT commands used in the implementation of the short message service. The +CGMF command is used to set the input and the output format of the messages to be sent, listed, read or written. The mode parameter indicates the selected mode: Text (+CGMF=1) or PDU (+CGMF=0). The +CNMI command is used to set the used procedure when receiving new messages from the network. The different parameters of this command are used to control and buffer result codes. For instance, when the mt variable is set to 0, no SMS-DELIVER messages are routed to the TE. The execution command +CNMA confirms the correct reception of new messages using a SMS-DELIVER/SMS-STATUS-REPORT notification. Sending text messages to cellular numbers is translated from the gateway order into CMGS AT commands (SMS-SUBMIT). A message reference value us returned to the TE when the message is successfully sent, otherwise (if the delivery fails in the network or the ME), a +CMS ERROR is returned.

The text messages translation to AT commands is based on the extraction of the text from SOAP messages. The text content is divided into may short messages with a length of 106 characters. The implemented SMS validity range varies from one hour to a week and the SOAP message can select to save the message in the sending request. The reception of messages is implemented by listening to the COM port of the Mobile Service Agent and the TE link. When a message is received, the TE sends an AT notification to our application then the message is processed.

B. Multimedia Messaging Service (MMS)

The Multimedia Messaging Service involves several elements in the overall MMS architecture such as the MMS user agent, MMS Relay/Server, User Databases (that contain user related information such as subscription and profile), Value Added Services (VAS), etc. (see the MMS architecture in Section 4.2 of [START_REF]Third Generation Partnership Project, Multimedia Messaging Service (MMS), Functional Description, Stage 2 (Release 6), Technical Specification Group Core Network and Terminals[END_REF]).

A minimum set of supported formats was defined in the 3GPP standards [START_REF]Third Generation Partnership Project, Multimedia Messaging Service (MMS), Functional Description, Stage 2 (Release 6), Technical Specification Group Core Network and Terminals[END_REF] and [START_REF]Third Generation Partnership Project, Multimedia Messaging Service (MMS), Media Formats and Codecs, (Release 9)[END_REF]: plain text, speech, audio, video, etc. The MMS user agent is responsible of many complex operations such as the user profile management, storing of messages on the terminal, handling of MMSrelated information on the (U)SIM, etc. Many of these operations depend to the terminal and the user agent implementation and configuration as it was planned by the standards [START_REF]Third Generation Partnership Project, Multimedia Messaging Service (MMS), Functional Description, Stage 2 (Release 6), Technical Specification Group Core Network and Terminals[END_REF] [START_REF]Third Generation Partnership Project, Multimedia Messaging Service (MMS), Media Formats and Codecs, (Release 9)[END_REF]. For instance, regarding the MMS retrieval, messages may be displayed on the terminal with or without any pre-notice. The user could be not aware of the message's notification and storage on the device. These user agent-dependent operations are key functionalities for handling correctly the MMS service of our gateway which make it difficult to bypass the user agent in the case where an MMS capable mobile equipment is used. The same situation occurs if we use a cellular modem (independently to a mobile equipment), in this case we can not bypass the manufacturer toolkit for handling the MMS service. In this work, the interesting exchange is the one done between the MMS capable user equipment and the MMS environment (MMSE). This exchange is done between the MMS user agent and the MMS Relay/Server. In the MMS reference architecture [START_REF]Third Generation Partnership Project, Multimedia Messaging Service (MMS), Functional Description, Stage 2 (Release 6), Technical Specification Group Core Network and Terminals[END_REF], the concerned interface (reference point) is called MM1 as shown in Figure 2. The MMS functionalities that concern our gateway are the user agent local operations and the MM1 exchange: submission of MMS from the user agent, pulling MMS from the MMS Relay/Server, pushing MMS message from the MMS Relay/Server to the user agent (notification), delivery reports between the MMS Relay/Server and the user agent.

In the implementation of the MMS service non standard AT manufacturer commands are used. For instance, the commands AT*E2IPA and AT*E2IPS are used within the Sony Ericsson GR47 to activated IP session (based on the stored PDP context) and to receive data with respect to the transmission across TCP/UDP [START_REF]Using AT commands to control TCP/IP stack on GR47/GR48[END_REF]. These commands are combined with others particular commands (such as the AT+CKPD and AT*EKEY) to force the user agent to perform some needed actions. The considered messages, between the user agent and the MMS Relay/Server, follow a part of the OMA implementation (stage 3) of the MM1 interface [START_REF]Open Mobile Alliance, Multimedia Messaging Service Client Transactions[END_REF]. Figure 3 shows these messages in a general scenario. M-Send.req is used to send the MMS, the proxy provides a status code for the requested operation (M-Send.conf). The M-Delivery.ind is used to convey information about the status of a particular delivery -identified by a message-ID -that was performed. When a message is available, the UA is informed by a M-Notification.ind message which let the UA, thanks to the provided information (about location, class, expiration time, etc.), to retrieve the message. The M-NotifyResp.ind provides a message retrieval status code. The UA retrieves the message using a WSP/HTTP GET request. M-retrieve.conf, if successful, contains the message and may request an acknowledgement depending to the MMS Relay/Server needs, e.g., to provide a delivery notice back to the originator of the message or to be able to delete the message from its storage space.

Lower Layer A

MMS User Agent

MM1

C. Call Service and Data Sharing/Synchronization

Calls and data access are implemented to show the ability to link cellular services to wired users. This can be useful for online service providers or a simple user who aims to use its own mobile terminal to access its data or to take advantages of its mobile subscription offers from anywhere.

As for the SMS service, AT commands are used to perform making and receiving calls based on the cellular modem. The actual state of the work considers only the control of GSM/UMTS voice calls. Data and fax control could be found in the ITU-T recommendations [START_REF]Serial Asynchronous Automatic Dialling and Control[END_REF]. Some of the related AT commands, used by the gateway, are the +CSTA command to set the type of number for dialing commands and ITU-T V.250 dial command D [START_REF]Third Generation Partnership Project, AT Command Set for User Equipment (UE), Technical Specification Group Core Network and Terminals[END_REF] that lists a set of characters for making calls and controlling additional services. The support of additional services relative commands, such as the +CCFC and +CCWA for call forwarding and waiting, is not implemented. The destination number of a call is given as a parameter of the D command and can be selected from a memory entry. Also, the destination number can be selected from a phonebook entry using the +CPBR and +CPBS=? commands. To handle incoming calls events (among other events), we use the +CRC=1 command. When an incoming call occurs, an unsolicited result code +CRING: <type> is captured from the COM port. When the type is VOICE [,<priority> [,<subaddr>,<satype>]], this means that the incoming call is a normal voice so it can be processed by the gateway. The +CHUP allows to answer the current received call and the audio stream is exploited by the mean of an audio gateway between the application and the mobile equipment. Sending and receiving the audio stream is done using the audio gateway and streaming the audio between the end user and the gateway uses the Real-Time Transport Protocol (RTP) thanks to the Java class: javax.media.rtp [START_REF]Sun Java Communications 3.0 API[END_REF].

The user equipment (UE), or mobile station (MS), is considered as the composition of a mobile equipment (ME) and the Universal Subscriber Identity Module ((U)SIM). Data, that the gateway allows to be shared or synchronized, can be stored either at the (U)SIM or the ME level. When a user or a distant application sends an authenticated order to synchronize or share the UE data, this order is translated into a set of AT commands that access to the UE data. The related functionalities includes: accessing and backup its own data (of the UE's owner), sharing these data with other users (other authenticated users could access to the shared folder of the gateway), reading/modifying/finding/removing existing data and hence data synchronization with other external information. Data include the user contacts, mails, SMS, MMS messages, media files (ringtones, pictures, songs, etc.) and call lists. Some of the used commands are: +CPIN required before using the ME, +CSIM and +CRSM for (U)SIM access, +CPBS/CPBR/CPBF/CPBW for managing the phonebook storage.

D. Personalized Services: case of a video surveillance

In addition to basic services such as messaging and calls, the gateway platform is able to provide new personalized services based on the basic operations already implemented. The video surveillance service is an example of a simple service that was implemented within the gateway. It is based on an external movement detection package and a live video stream captured by a camera. When a movement is detected the package sends an order to the wireless gateway in order to send an SMS message to a mobile phone number selected initially. The wireless gateway makes the implementation of this service very easy; the video surveillance application could at any moment change the destination number and way to inform that destination number if a movement is detected. The current implementation of this service sends a simple SMS alert. However, this could be improved, e.g., by sending the captured movement or dangerous presence using the MMS messaging service.

V. CONCLUSION AND FUTURE WORK

In this paper we have presented a new framework of implementing an easy gateway between users of the wireline network and users of the cellular network. Our gateway has successfully enabled users of the wired network to gain access to a set of typically cellular services such as joining other mobile users using mobile messaging. Another demonstrated service was making mobile terminals data accessible from everywhere and anyhow even using a simple Internet connection. There is scope for lot of improvement depending on the requirements of the gateway's use for instance: the optimization of the QoS regarding the audio streaming, the support of several simultaneous accesses and composing new services based on the implemented modem control and operations. Another point which was not discussed is including some policies regarding the cost sharing, in respect to the cellular operator contract, when a cellular service is used by many users.

To force some particular user agent dependent actions, e.g., to access to its own configuration for the MMS service, we have used emulating commands such as AT+CKPD and the Sony Ericsson terminal command AT*EKEY. This implementation detail has implied the provision of some mobile terminal profiles to make the use of the MMS service universal and accessible by Web services. The actual profiles repository still small and one of the perspectives is to enrich it with many other models. Also, the SOAP's performance (overhead, execution time, complex message throughput) regarding the transport protocol could be improved. [START_REF] Phan | A benchmark on Soap's Transport Protocols Performance for Mobile Applications[END_REF] concluded that using UDP as the underlying transport is more suitable than TCP. For us, this can be adopted only for frequent short SOAP messages. In this context, the optimization using Message Transmission Optimization Mechanism (MTOM) and XML-binary Optimized Packaging (XOP) [START_REF]SOAP Version 1.2, Part 0: Primer[END_REF] will be explored.

Figure 1 .

 1 Figure 1.Architecture Overview.

Figure 2 .

 2 Figure 2.The MM1 Interface.

Figure 3 .

 3 Figure 3. Messages Exchange between the UA and the MMS Relay/Server.

TABLE I .

 I AVERAGE TIME OF ONE SOAP CALL

	Implementation	Average time of one SOAP Call (ms)
	Web Services (Apache) -AXIS (1.4 final)	10,10
	SOAP Lite (0.65 beta 3)	28,11
	Microsoft SOAP Toolkit 3.0	12,22
	CORBA (Java Client/Server)	1,02

TABLE II

 II

	.	AT COMMANDS FOR SMS
	AT Command	Function
	+CMGF=[<mode>]	Messages format and mode
	+CNMI=[<mode>[,<mt>
	[,<bm>[,<ds>[,<bfr>	Procedure of messages' reception
	]]]]]
	+CNMA	Reception confirmation
	+CMGS	Reception confirmation


Nitin Chiluka
email: nitin.chiluka@inria.fr

Anne-Marie Kermarrec
email: anne-marie.kermarrec@inria.fr

Javier Olivares
email: javier.olivares@inria.fr

Scaling KNN Computation over Large Graphs on a PC

Keywords: E.1 [Data]: Data Structures-Graphs and Networks; I.5.3 [Computing Methodologies]: Clustering-Algorithms, Similarity measures Algorithms, Design, Performance K-nearest neighbors, Dynamic Graphs

This paper proposes a novel approach to compute K-Nearest Neighbors (KNN) algorithm on a large set of users by leveraging disk and memory efficiently on a commodity PC. The system is designed to minimize random accesses to disk as well as the amount of data loaded/unloaded from/to disk so as to better utilize the computational power, thus improving the algorithmic efficiency.

INTRODUCTION

Frameworks such as GraphChi [START_REF] Kyrola | Graphchi: Large-scale graph computation on just a pc[END_REF] and X-Stream [START_REF] Roy | X-stream: edge-centric graph processing using streaming partitions[END_REF] are increasingly gaining attention for their ability to perform scalable computation on large graphs by leveraging disk and memory on a single commodity PC. These frameworks rely on the graph structure to remain the same for the entire period of computation of various algorithms such as PageRank and triangle counting. As a consequence, these frameworks are not applicable to algorithms that require the graph structure to change during their computation. In this work, we focus on one such algorithm -K-Nearest Neighbors (KNN) -which is widely used in recommender systems [START_REF] Dong | Efficient k-nearest neighbor graph construction for generic similarity measures[END_REF].

The KNN computation proceeds in iterations, as follows. At each iteration t, computing KNN of a user i requires a similarity comparison of its profile with each of the profiles of all its neighbors and neighbors' neighbors, and then the top-K most similar users from this neighborhood constitute the new KNN of user i for the next iteration t + 1.

We model the collection of KNN of each user by a directed graph G(t) where each (user) vertex has at most K-outdegree neighbors. KNN computation changes the graph from G(t) to G(t + 1), requiring the removal of edges to former neighbors and the addition of edges to new neighbors. Such features are not supported in either GraphChi or X-Stream. In addition to G(t), we have a set of user profiles P (t) at iteration t, which can also change over time to P (t + 1).

Our goal in this work is to design a system that can compute KNN of each user efficiently in a memory constrained machine, considering that user profiles change over time.

SYSTEM DESIGN

Given the system constraints of a commodity PC with limited memory, our system aims to scale KNN for a large number of users whose profiles change over time by leveraging memory and disk in an efficient manner. The main rationale of our approach is to minimize random accesses to disk as well as the amount of data loaded/unloaded from/to disk. We note that inefficient accesses of disk leads to poor utility in terms of computational power, thus affecting the algorithmic efficiency of KNN computation.

Our approach to computing KNN at each iteration t proceeds in five phases, as shown in Figure 1. Firstly, the KNN graph G(t) is partitioned in m partitions such that the disk and memory operations in the future phases are minimized. Secondly, we build a hash table to hold all the unique tuples (s, d) where s is a user and d is either a neighbor or a neighbor's neighbor of s. Thirdly, we create a partition interaction graph which helps in deciding the order in which partitions are loaded and unloaded so as to calculate the similarity between users in tuples generated in the previous phase efficiently. We develop some heuristics to minimize the number of operations performed to complete the process. Fourthly, we generate each user's top-K most similar neighbors from its set of neighbors and neighbors' neighbors, thus resulting overall in the new KNN graph G(t + 1). Finally, all the changes in the user profiles during this iteration t are lazily updated to P (t + 1) for the next iteration.

KNN Iteration

The first phase of our approach performs KNN graph partitioning such that only a few small pieces of the graph as well as related data structures can be stored in memory at any given point in time while the rest are stored on disk which can be accessed efficiently later. The input of this phase is a directed KNN graph G(t) at iteration t which could be at any stage in the computation: initial, intermediate, or near-convergence.

We divide G(t) into m partitions, each of which corresponds to a fixed number of users n m where n is the number

min m i=1 (N in i + N out i
). Such a partitioning mechanism enables a greater extent of data locality in the fourth phase.

For efficient access of neighbors' neighbors, we sort the inedges {(s, v) ∈ Ri} and the out-edges {(v, d) ∈ Ri}, where v ∈ Vi and vertices s and d belong to any of the m partitions, by the vertex id v in their respective lists. One can now read the files of in-edge and out-edge lists sequentially to generate tuples (s, d) which are essentially neighbors' neighbors, since the vertex v acts as a bridge between s and d.

The second phase of our approach is the creation and population of a hash table H. We use a hash table to avoid generating duplicate tuples which can occur due to cycles (e.g., vertices a, b and c have edges to each other) or paths with same start and end vertices but with a different bridge vertex (e.g., vertex a has out-edges to vertices b and c each of which in turn have out-edges to vertex d).

H is populated with unique tuples (s, d) representing neighbors' neighbors from the first phase as well as directed edges from the graph G(t). Once H has all the tuples, the system has to compare the profiles of all tuples {(s, d) ∈ H} to calculate the similarity values. Since each tuple's s and d could belong to different partitions, accessing their profiles from respective partitions in an arbitrary fashion can lead to poor performance due to various random accesses to disk as well as loading/unloading of partitions from/to disk.

The third phase is the creation and traversal of the partition interaction (PI) graph which helps in deciding the order in which all the tuples' similarity scores are computed. In the PI graph, each node represents a partition Ri from the first phase, and a directed edge (Ri, Rj) represents all the tuples {(s, d) ∈ H} such that s ∈ Ri and d ∈ Rj. In our memory constrained environment, we load the profiles of at most two partitions Ri and Rj at any point in order to compute the similarity scores of all the tuples {(a, b)} such that vertices a and b belong to either of Ri and Rj. We note that when all the edges in the PI graph are parsed, it means that the similarity scores of all the corresponding tuples in H have been computed.

We describe a few heuristics to decide the order in which the PI graph is parsed. The sequential heuristic loads the partition starting from number 1, processes all its edges in the PI graph, removes this partition from further consideration, and continues with next partition number 2, and so on until all edges and nodes are parsed. The degree-based heuristic has two versions depending on the order for the next edge executed. The first version starts processing vertices with the highest degree, choosing the next edge to be processed according to the degree of the destination vertex from highest to lowest degrees. The other version of this algorithm also starts processing vertices with the highest degree, but the next edge is selected on the criteria from lowest to highest degrees of the destination vertices. Table 1 presents a preliminary evaluation of these heuristics on various datasets. If the PI graph structure were to resemble these networks, we observe that our simple degreebased heuristics typically have 5-15% fewer partition load/unload operations than the sequential one, suggesting scope for improvement with better heuristics.

The fourth phase performs KNN computation using the PI graph and the profiles P (t) to generate G(t + 1) which is the new KNN graph for the next iteration. First, the PI graph is parsed in the order based on one of the above heuristics such that the profiles of at most two partitions Ri and Rj are loaded into memory at a time. Next, each tuple (s, d) where s ∈ Ri and d ∈ Rj is read sequentially, and then a similarity score sim(s, d) is computed based on their profiles. When the similarity scores for all tuples in each partition are computed, one can generate the K-most similar neighbors for each user, resulting in G(t + 1).

Finally, the fifth phase is responsible for updating user profiles from P (t) to P (t + 1). Throughout the iteration t, any changes in the profiles of the users are stored in a queue q but not incorporated into P (t). In this phase, the queue is read to update the profiles to P (t + 1). After completing this phase, the system returns to the first phase of the next iteration t + 1, while the queue is ready for new profile updates to store.

Future Work. We plan to evaluate our approach using different graph sizes, amounts of memory, HDD and SSD, and multiple threads by measuring execution times as well as throughput from the disk IO operations. Furthermore, we aim to develop more heuristics for the PI graph traversal which consider the amount of time consumed for both partition load/unload operations and the similarity computation for tuples given two partitions.

Figure 1 :

 1 Figure 1: 5 phases: input G(t), 1) KNN graph partitioning, 2)Hash Table, 3)PI graph, 4)KNN computation, 5)Updating profiles of users in G(t). A partition Ri is composed of a subset Vi of n m users, both the in-edges and out-edges of the users Vi, and the profiles of these users. The criteria for partitioning G(t) is that the total sum of the (unique) source vertices N in i of in-edges and the (unique) destination vertices N out i of out-edges in each partition i is minimized: min m i=1 (N in i + N out

Table 1 :

 1 # Load/unload operations using PI graph.

	Datasets	Nodes	Edges	Seq.	High-Low Low-High
	Wiki-Vote	7115	100762 211856	204706	202290
	Gen. Rel.	5241	14484	34506	32220	31256
	High Ener. 12006 118489 252754	242132	240872
	AstroPhy.	18771 198050 420442	400050	401770
	E-mail	36692 183831 399604	382928	379312
	Gnutella	26518	65369	157040	144072	132710

Acknowledgments. This work was partially funded by Conicyt/Beca Doctorado en el Extranjero Folio 72140173 and Google Focused Award Web Alter-Ego.


Hélène Fargier
email: fargier@irit.frmarquis

Pierre Marquis

Alexandre Niveau

Nicolas Schmidt
email: schmidt@cril.fralexandre.niveau@unicaen.fr

Carte de compilation des diagrammes de décision ordonnés à valeurs réelles *

Les diagrammes de décision valués (VDDs) sont des structures de données représentant des fonctions à valeurs réelles positives. Ces structures sont utiles pour la compilation de fonctions de coût ou d'utilité, ou encore de distributions de probabilités. Si la complexité de certaines requêtes (comme l'optimisation) et de certaines transformations (comme le conditionnement) sur de tels langages est bien connue, il reste de nombreuses requêtes et transformations importantes dont la complexité n'a pas encore été identifiée ; figurent parmi elles différents types de coupes, marginalisations, ou encore combinaisons. En établissant une carte de compilation des diagrammes de décision ordonnés à valeurs réelles, cet article contribue à combler ce manque. Nos résultats montrent que beaucoup de tâches difficiles à partir de CSPs valués sont traitables à partir de VDDs.

Introduction

Les diagrammes de décision valués sont des structures de données représentant des fonctions à variables multiples, et à valeur dans un ensemble V de « valuations » (généralement un sous-ensemble de R + ).

Ces fonctions correspondent souvent à des fonctions de coût ou d'utilité, ou à des distributions de probabilités, qui sont largement utilisés en IA. Parmi les différentes tâches importantes lorsque l'on utilise ce genre de fonctions, on retrouve la requête d'optimisation : trouver une affectation donnant la valuation optimale, ou la valeur d'une variable donnée pouvant conduire à une affectation optimale, etc. Une telle requête est particulièrement intéressante combinée avec la transformation de conditionnement, qui donne une représentation restreinte de la fonction, dans laquelle certaines variables ont été affectées. La combinaison de ces deux tâches permet par exemple de résoudre des problèmes comme la recherche du diagnostic le plus probable considérant un ensemble de symptômes, ou de la voiture la moins chère d'une gamme qui soit munie d'un klaxon cucaracha.

Plusieurs autres structures de données ont été définies pour représenter ce genre de fonctions à variables multiples, les plus connues étant les CSP valués [START_REF] Schiex | Valued constraint satisfaction problems: Hard and easy problems[END_REF], les GAI nets [START_REF] Bacchus | Graphical models for preference and utility[END_REF], et les réseaux bayésiens [START_REF] Pearl | Probabilistic reasoning in intelligent systems -networks of plausible inference[END_REF]. Cependant ces langages ne sont pas adaptés aux requêtes susmentionnées lorsque des garanties de temps de réponse sont imposées (comme c'est le cas dans les applications Web) : l'optimisation est en effet NP-difficile pour les CSPs, GAI-nets et réseaux bayésiens.

Les VDDs n'ayant pas cet inconvénient, plusieurs familles de VDDs ont été définies et étudiées durant ces vingt dernières années. On s'intéressera ici notamment au langage ADD (algebraic decision diagrams) [START_REF] Bahar | Algebraic decision diagrams and their applications[END_REF], au langage AADD (affine algebraic decision diagrams) [START_REF] Tafertshofer | Factored edge-valued binary decision diagrams[END_REF][START_REF] Sanner | Affine algebraic decision diagrams (AADDs) and their application to structured probabilistic inference[END_REF], et au langage SLDD (semiring-labeled decision diagrams) [START_REF] Wilson | Decision diagrams for the computation of semiring valuations[END_REF]. En réalité, SLDD est une famille de langages SLDD ⊗ , paramétrée par un opérateur ⊗. On retrouve en particulier SLDD + (équivalent au langage des EVBDDs [START_REF] Lai | Edge-valued binary decision diagrams for multi-level hierarchical verification[END_REF][START_REF] Lai | Formal verification using edge-valued binary decision diagrams[END_REF][START_REF] Amilhastre | Consistency restoration and explanations in dynamic CSPs: Application to configuration[END_REF]) lorsque ⊗ représente l'opérateur +, et SLDD × lorsque ⊗ représente l'opérateur ×.

Toutefois, de nombreuses requêtes et transformations ne découlent pas du conditionnement et de l'optimisation. Considérons par exemple la requête suivante : « lister toutes les voitures bon marché (par exemple en-dessous de 10 000 euros) de telle gamme, d'une capacité d'au moins 8 passagers ». Cela demande de se concentrer sur les voitures bon marché, ce qui ne relève ni de l'optimisation ni du conditionnement. De même, certaines transformations, telles la projection sur une variable, ou son complémentaire, l'élimination de variables, qui ont une grande importance théorique et pratique (par exemple pour résoudre le problème « posterior marginal » (PM) dans les réseaux bayésiens), ne peuvent pas être réduites à l'optimisation et au conditionnement. C'est également le cas pour les transformations de combinaison (aussi appelées opérations « apply »), qui consistent, étant donné des représentations de fonctions f et g, à calculer une représentation de la fonction f g, avec un opérateur associatif et commutatif sur V (par exemple l'addition ou la multiplication, lorsque V = R + ). Ces transformations sont très importantes, ne serait-ce que pour permettre la construction incrémentale de représentations par des algorithmes de type ascendant.

La carte de compilation [START_REF] Darwiche | A knowledge compilation map[END_REF] identifie la complexité des requêtes et transformations sur plusieurs langages propositionnels, ainsi que la compacité relative de ces langages. Cependant, elle ne concerne que le cas spécifique des fonctions booléennes ; et même si cette carte a été étendue dans de nombreuses directions, le cas des VDDs n'a pas encore été très développé. Il a été montré que le langage AADD est strictement plus compact que le langage ADD [START_REF] Sanner | Affine algebraic decision diagrams (AADDs) and their application to structured probabilistic inference[END_REF], les travaux sur la compacité ont ensuite été étendus [START_REF] Fargier | Semiring labelled decision diagrams, revisited: Canonicity and spatial efficiency issues[END_REF], montrant que le langage AADD est strictement plus compact que les langages SLDD + et SLDD × , eux-mêmes plus compacts que le langage ADD. Pour compléter cette carte, il reste à déterminer l'ensemble des requêtes et transformations d'intérêt que chacun de ces langages satisfait. En d'autres termes, pour chaque requête et transformation, et pour chacun des langages ADD, SLDD + , SLDD × et AADD, il s'agit de mettre en évidence un algorithme en temps polynomial effectuant cette opération, ou de prouver qu'un tel algorithme n'existe pas à moins que P = NP.

C'est le but principal de cet article, qui est orga-nisé comme suit La section suivante permet au lecteur de faire connaissance avec la famille des langages de VDDs, et la suivante présente les requêtes et transformations étudiées dans la carte de compilation. Nous exposons ensuite les résultats de complexité obtenus 1 , établissant pour chaque langage étudié et chaque requête et transformation, si le langage satisfait ou pas la requête ou la transformation. Ils constituent une première avancée dans la construction d'une carte de compilation pour les fonctions à valeurs non booléennes.

Diagrammes de decision valués

Préliminaires. Soit un ensemble fini de variables X = {x 1 , . . . , x n }, chaque x i prenant ses valeurs dans un domaine fini D xi , et soit un sous-ensemble X ⊆ X ; on note #-

x = { x i , d i | x i ∈ X, d i ∈ D xi }
une affectation des variables de X, et D X l'ensemble de toutes ces affectations (le produit cartésien des domaines des variables de X). La concaténation de deux affectations #x et #y de deux ensembles disjoints de variables X et

Y est une affectation de X ∪ Y notée #-x • #-y .
On considère des fonctions f portant sur des variables d'un sous-ensemble Scope(f ) ⊆ X , et prenant leurs valeurs dans V (dans cet article, on pren-

dra souvent V = R + ). Le domaine de f est noté D f = D Scope(f ) . Pour tout Z ⊆ Scope(f ), on note f #-z la restriction (ou conditionnement sémantique) de f par #-z , c'est-à-dire la fonction sur Scope(f ) \ Z telle que pour tout #-x ∈ D Scope(f )\Z , f #-z ( #-x ) = f ( #-z • #-x ).
Soit un opérateur binaire sur V, et deux fonctions f et g portant sur un même ensemble de variables ; f g est la fonction définie par f g

( #-x ) = f ( #-x ) g( #-x ). La -projection de f sur Z ⊆ Scope(f ) est définie par f ,Z ( #-x ) = #-y ∈D Scope(f )\Z f #-y ( #-x ).
En abusant quelque peu des notations, si X et Y sont deux ensembles de variables disjoints, Scope(f ) = X, et #x • #y est une affectation de X ∪ Y , alors on suppose que f ( #x • #y ) = f ( #x ). En pratique, on considère souvent des affectations complètes #x ∈ D X .

Soit une relation binaire réflexive et transitive sur V (c'est-à-dire un préordre), dont on note ∼ la partie symétrique et la partie asymétrique. On définit les ensembles de « coupes » suivants :

-CUT max (f ) = { #-x * | ∀ #-x , ¬(f ( #-x ) f ( #-x * )) } ; -CUT min (f ) = { #-x * | ∀ #-x , ¬(f ( #-x ) ≺ f ( #-x * )) } ; -CUT γ (f ) = { #-x | f ( #-x ) γ } ; -CUT γ (f ) = { #-x | f ( #-x ) γ } ; -CUT ∼γ (f ) = { #-x | f ( #-x ) ∼ γ } ;
1. Pour des raisons de place, les preuves ne sont pas développées ici ; une version complète (incluant les preuves) de l'article AAAI original peut être trouvée à l'adresse <url: https: //niveau.users.greyc.fr/pub/AAAI14 FMNS.pdf>.

Par exemple, si l'optimisation correspond à la minimisation, CUT min est l'ensemble des solutions optimales (les voitures les moins chères) ; CUT γ est l'ensemble des solutions satisfaisant la condition de la coupe (les voitures bon marché, celles dont le prix est inférieur à γ).

Un langage de représentation sur X à valeurs dans V est un ensemble de structures de données, équipé d'une fonction d'interprétation qui associe à chacune une fonction f : D X → V. Cette fonction est appelée l'interprétation de la structure de données, et la structure de données est la représentation de cette fonction.

Définition 2.1 (langage de représentation ; inspirée de [START_REF] Gogic | The comparative linguistics of knowledge representation[END_REF]). Etant donné un ensemble de valuations V, un langage de représentation L sur X à valeurs dans V est un quadruplet C L , Var L , f L , s L , où : -C L est un ensemble de structures de données (également appelées L-représentations ou simplement « formules »), -Var L : C L → 2 X est une fonction qui associe à chaque L-représentation le sous-ensemble de X dont elle dépend, -f L est une fonction d'interprétation associant à chaque L-représentation α une fonction f L α depuis l'ensemble de toutes les affectations de Var L (α) vers V, -s L est une fonction de taille, de C L dans N, qui donne la taille de chacune des L-représentations.

Diagrammes de décision valués. Dans la suite, nous considérons des langages de représentation basés sur des structures de données appelées diagrammes de décision valués. De tels diagrammes permettent de représenter des fonctions à valeurs dans V en autorisant les noeuds et les arcs à porter des valeurs, prises dans un ensemble E (généralement E = V, mais ce n'est pas toujours le cas, comme nous le verrons plus tard). Définition 2.2 (diagramme de décision valué). Un diagramme de décision valué (VDD) sur X et E est un multi-graphe acyclique orienté, fini, et comportant une racine unique, dans lequel chaque noeud N est étiqueté par une variable x ∈ X et possède un ensemble Out(N ) de |D x | arcs sortants, chaque arc a ∈ Out(N ) étant étiqueté par une valeur distincte v(a) ∈ D x . Les arcs comme les noeuds peuvent être étiquetés par des éléments de E ; on note ϕ(a) (resp. ϕ(N )) la valuation de l'arc a (resp. du noeud N ). La taille d'un diagramme de décision α, notée |α|, est la taille du graphe (son nombre de noeuds et d'arcs) plus la taille de l'ensemble des valuations portées par les arcs et les noeuds.

Nous supposons que tous les diagrammes de décision considérés sont ordonnés, i.e. que pour tout VDD, un ordre strict et total sur X est choisi, et quel que soit le chemin pris de la racine à un noeud terminal, les variables étiquetant les noeuds sont rencontrés dans l'ordre (chaque variable ne peut donc apparaître qu'une seule fois dans un même chemin). Un chemin de la racine à un noeud terminal représente une affectation (partielle) de X ; la structure des diagrammes de décision est déterministe, ce qui signifie qu'à une affectation donnée ne correspond au plus qu'un seul chemin dans α, noté p α ( #x ).

Un VDD α est considéré comme réduit s'il ne comporte aucun couple de noeuds isomorphes (distincts) 2 . Un système de cache peut être utilisé pour détecter et fusionner ces noeuds isomorphes à la volée, ce qui nous permet de considérer implicitement les diagrammes comme étant réduits. -si α est un noeud terminal, alors

f ADD α ( #-x ) = ϕ(α), -sinon, en notant N la racine de α, x ∈ X sa va- riable, d ∈ D x la valeur telle que x, d ∈ #-x , a = N, M l'arc tel que v(a) = d, et β la for- mule ADD ayant pour racine le noeud M de α, alors f ADD α ( #-x ) = f ADD β ( #-x ). Dans le cadre AADD de Sanner & McAllester [18],
le co-domaine de la fonction représentée est V = R + .

Un seul noeud terminal est autorisé, et chaque arc est étiqueté par un couple de valeurs de R + (c'est-à-dire que

E = R + × R + = V).
q 0 , f 0 dans R + × R + , appelé offset. L'inter- prétation d'un tel VDD α est, pour chaque affectation #-x , f AADD α ( #-x ) = q 0 + (f 0 × g AADD α ( #-x )), où g AADD α est définie comme suit : -si α est le noeud terminal, alors g AADD α ( #-x ) = 0, -sinon, en notant N la racine de α, x ∈ X sa va- riable, d ∈ D x la valeur telle que x, d ∈ #-x , a = N, M l'arc tel que v(a) = d, ϕ(a) = q a , f a , et β la formule prenant racine au noeud M de α, alors g AADD α ( #-x ) = q a + (f a × g AADD β ( #-x )).
Le langage AADD est muni d'une condition de normalisation qui rend toute AADD-représentation ordonnée (et réduite) canonique. La canonicité est importante car elle assure une représentation unique de chacune des sous-formules, ce qui est la clé pour efficacement reconnaître et fusionner les noeuds isomorphes.

Dans le cadre SLDD ⊗ [START_REF] Wilson | Decision diagrams for the computation of semiring valuations[END_REF] 3 , les arcs (mais pas les noeuds terminaux) sont étiquetés par des éléments de

E = V, et E, ⊗, 1 ⊗ est un monoïde commutatif : f SLDD⊗ α
( #x ) est l'agrégation par ⊗ des étiquettes des arcs le long du chemin p α ( #x ). Définition 2.5 (SLDD ⊗ ). Soit un monoïde commutatif E, ⊗, 1 ⊗ ; le langage SLDD ⊗ est le quadruplet C SLDD⊗ , 3. Notre définition de SLDD est un peu plus générale que l'originale, en ce que (i) nous ne considérons que des diagrammes ordonnés, et (ii) nous utilisons un monoïde commutatif au lieu d'un semi-anneau commutatif, le deuxième opérateur n'étant pas utilisé dans la définition de la structure de données [START_REF] Fargier | Semiring labelled decision diagrams, revisited: Canonicity and spatial efficiency issues[END_REF].

Var SLDD⊗ , f SLDD⊗ , s SLDD⊗ , avec C SLDD⊗ l'ensemble des VDDs ordonnés sur X ayant un unique noeud terminal N d'étiquette ϕ(N ) = 1 ⊗ , dont les arcs sont étiquetés avec des éléments de E = V, et dont la racine a un

offset ϕ 0 ∈ E. Pour chaque formule α et chaque affec- tation #-x , f SLDD⊗ α ( #-x ) = ϕ 0 ⊗ g SLDD⊗ α ( #-x ), où g SLDD⊗ α ( #-x ) est définie comme suit : -si α est le noeud terminal, alors g SLDD⊗ α ( #-x ) = 1 ⊗ , -sinon, en notant N la racine de α, x ∈ X sa va- riable, d ∈ D x la valeur telle que x, d ∈ #-x , a = N, M l'arc tel que v(a) = d, et β la formule prenant racine au noeud M de α, alors g SLDD⊗ α ( #-x ) = ϕ(a) ⊗ g SLDD⊗ β ( #-x ).
Deux monoïdes sont particulièrement intéressants : R + , +, 0 (le langage correspondant est noté SLDD + ) et R + , ×, 1 (le langage correspondant est noté SLDD × ). Les langages SLDD + et SLDD × ont tous deux des conditions de normalisation qui assurent leur canonicité. De plus, toute formule de l'un de ces deux langages peut être traduite en temps linéaire vers le langage AADD .

Il en va de même pour le langage ADD, dont chaque formule peut être traduite en temps linéaire en une formule de chacun des trois autres langages étudiés ici ; un exemple est donné en figure 2 (pour plus de détails sur les traductions de formules d'un langage vers un autre, voir Fargier et al. [START_REF] Fargier | Compacité pratique des diagrammes de décision valués : normalisation, heuristiques et expérimentations[END_REF]). Enfin, notons que si les variables sont booléennes, et V = {0, 1}, toute formule de chacun des quatre langages considérés peut être traduite en un OBDD en temps linéaire, la réciproque étant trivialement vraie. -L satisfait l'optimisation OPT max (resp.

OPT min ) si et seulement s'il existe un algorithme en temps polynomial associant à toute formule α de L la valeur max

#-x ∈D f f L α ( #-x ) (resp. min #-x ∈D f f L α ( #-x )).
-L satisfait l'équivalence EQ si et seulement s'il existe un algorithme en temps polynomial asso-ciant tout couple α, β de formules de L à 1 si f L α = f L β , et à 0 sinon. -L satisfait l'implication de formules SE si et seulement s'il existe un algorithme en temps polynomial associant tout couple α, β de formules de

L à 1 si ∀ #-x , f L α ( #-x ) f L β ( #-x ), et à 0 sinon. -L satisfait la cohérence partielle supérieure (resp.
inférieure, resp. égale) CO γ (resp CO γ , resp. CO ∼γ ) si et seulement s'il existe un algorithme en temps polynomial associant tout γ ∈ V et toute formule

α de L à 1 si ∃ #-x , f L α ( #-x ) γ (resp. f L α ( #-x ) γ, resp. f L α ( #-x ) ∼ γ),
∈ V et toute formule α de L à 1 si ∀ #-x , f L α ( #-x ) γ (resp. f L α ( #-x ) γ, resp. f L α ( #-x ) ∼ γ),
(f L α ), CUT γ (f L α ), CUT γ (f L α ) et CUT ∼γ (f L α ) à la place de CUT max (f L α )
. Les familles de requêtes MX et ME sont cruciales pour le raisonnement bayésien et la configuration interactive. Elles capturent, par exemple, la demande d'une explication parmi les plus probables (MX max ), ou d'une des configurations les moins chères (MX min ). Dans ces applications, le comptage est également utile, comme pour caractériser le nombre de voitures « bon marché » (CT γ ) ou le nombre de maladies suffisamment probables pour être considérées (CT γ ). Les autres requêtes, telles la cohérence, la validité, l'équivalence ou l'implication, sont utiles à de nombreux problèmes de raisonnement, notamment car elles étendent aux bases de connaissances pondérées les requêtes analogues définies sur les formules booléennes en NNF. -L satisfait la -marginalisation de variable Marg si et seulement s'il existe un algorithme en temps polynomial associant à toute formule α de L et toute variable x ∈ X une L-représentation de #-z ∈D X \{x} f L α, #z . -L satisfait la γ-coupe haute CUT γ , suivant un préordre sur V, si et seulement s'il existe un algorithme en temps polynomial associant à toute formule α de L et toutes valeurs γ, a, b ∈ V vérifiant a b, une L-représentation de la fonction g définie par g(

#-x ) = a si #-x ∈ CUT γ (f L α ), et g( #-x ) = b sinon.
Les transformations CUT γ , CUT ∼γ , CUT max et CUT min sont définies de la même façon, en utilisant respectivement les ensembles

CUT γ (f L α ), CUT ∼γ (f L α ), CUT max (f L α ) et CUT min (f L α ).
La transformation classique d'« oubli » de variables (forgetting) correspond à leur max-élimination. La marginalisation sur une variable est équivalente à l'élimination de toutes les variables, sauf une ; la +-marginalisation est typiquement importante dans le cadre des réseaux bayésiens, pour effectuer la posterior marginal request (voir par exemple Darwiche [START_REF] Darwiche | Modeling and Reasoning with Bayesian Networks[END_REF]), et dans les problèmes de configuration, la min-marginalisation dans un VDD représentant une fonction de prix revient à calculer le prix minimal associé à toute valeur possible de la variable en question (qui représente par exemple une option pour une voiture, voir Astesana et al. [START_REF] Astesana | Constraint-based vehicle configuration: A case study[END_REF]). On trouve un autre exemple d'utilisation en planification stochastique, où l'algorithme d'itération de la valeur peut être a été implémenté par une suite de +-éliminations et de ×combinaisons sur des formules ADD [START_REF] Hoey | SPUDD: Stochastic planning using decision diagrams[END_REF].

Pour finir, la famille des opérations de coupe représente la restriction d'une fonction aux affectations optimales (les voitures les moins chères, les explications les plus probables. . .) ou proches de l'optimum (les voitures à moins de γ euros, les maladies ayant une probabilité > γ). Pour qu'elle reste aussi générale que possible, nous avons défini cette famille d'opérations comme des transformations au sein d'un même langage, mais il est important de noter qu'en prenant -ADD, SLDD + , SLDD × et AADD satisfont EQ et CD.

-ADD, SLDD + et SLDD × satisfont SE.
Pour structurer les autres résultats, nous distinguons trois catégories d'opérations : celles liées à l'optimisation, qui sont traitables sur les VDDs ; celles liées à la coupe suivant un seuil γ, qui peuvent devenir difficiles ; et les transformations de combinaison et d'élimination de variables. Les résultats obtenus pour les deux premières catégories sont résumés dans la table 1, et ceux obtenus pour la troisième le sont dans la table 2.

Opérations liées à l'optimisation. Comme évoqué précédemment, OPT max et OPT min sont traitables pour les formules AADD [START_REF] Sanner | Affine algebraic decision diagrams (AADDs) and their application to structured probabilistic inference[END_REF] comme pour les formules SLDD [START_REF] Wilson | Decision diagrams for the computation of semiring valuations[END_REF], et leur satisfaction par ADD est évidente. Tous les résultats positifs de la table 1 sont liés aux faits que (i) les VDDs sont des graphes sans circuit, et (ii) l'agrégation des valuations ϕ est monotone sur les classes considérées. Dans de tels diagrammes, les chemins de valeur minimale (resp. maximale) peuvent être obtenus en temps polynomial, grâce à un algorithme de recherche de plus court (resp. plus long) chemin. En s'appuyant sur cette idée, on peut écrire une procédure en temps polynomial construisant une formule MDD qui représente les affectations optimales -ce qui implique la satisfaction de CUT max et CUT min , dont on peut déduire celle des requêtes portant sur ces coupes. Opérations liées aux γ-coupes. Les requêtes et transformations liées à l'optimisation pure sont donc faciles ; cependant, pour de nombreuses applications, l'optimisation seule ne suffit pas. Ainsi, un client voulant acheter une voiture ne cherche pas forcément la moins chère, mais un véhicule qui satisfait ses desiderata tout en étant relativement bon marché, c'està-dire, d'un coût inférieur à un certain seuil -d'où l'importance des γ-coupes.

Un résultat positif est qu'il suffit de comparer la valeur maximale (resp. minimale) de f L α (qui peut s'ob-

tenir en temps polynomial) à γ ∈ R + pour décider s'il existe un #-x tel que f L α ( #-x ) ≥ γ (resp. ≤ γ).
De même, décider de la γ-validité d'une formule α nécessite seulement de comparer γ à la valeur maximale (resp. minimale) de f L α .

Proposition 4.3. ADD, SLDD + , SLDD × et AADD satis- font CO γ , VA γ , CO γ , VA γ et VA ∼γ .
Bien qu'il soit possible de vérifier en temps polynomial s'il existe une affectation conduisant à une valeur supérieure ou égale à γ, déterminer s'il existe une affectation conduisant exactement à γ est difficile sur SLDD + , SLDD × et AADD. La preuve s'appuie sur une réduction polynomiale depuis le problème de décision subset sum [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF] L'idée de la preuve du premier point est que depuis tout noeud d'une formule AADD normalisée, il existe un chemin vers le noeud terminal qui correspond à la valeur 1, et un autre qui correspond à la valeur 0. Un chemin de la racine à ce noeud lui fournit un offset (notons-le p, q ), calculé à partir de ses arcs. Il est ainsi possible de répondre à ME γ (resp. ME γ ) en énumérant tous les chemins, sans explorer les noeuds pour lesquels p + q < γ (resp. p > γ).

La preuve du point suivant s'appuie sur le fait que si CT γ était satisfaite, il serait possible de compter les affectations #x vérifiant f α ( #x ) ≥ γ, et également celles vérifiant f α ( #x ) > γ ; CT ∼γ serait donc satisfaite, or nous avons montré qu'elle est difficile (même principe pour CT γ ).

Les transformations CUT γ et CUT γ ne sont pas satisfaites, et ce inconditionnellement (même si P = NP). Pour le cas de CUT γ sur SLDD + , la preuve utilise le fait que la fonction

f ( #-y • #-z ) = n i=1 y i • √ √ √ √ • CO∼γ √ • • • • CO γ / CO γ √ √ √ √ • ME∼γ √ • • • • ME γ / ME γ √ √ √ √ • MX∼γ √ • • • • MX γ / MX γ √ √ √ √ • CUT∼γ √ • • • ? CUT γ / CUT γ √ • • • ? CT∼γ √ • • • • CT γ / CT γ √ • • • •
2 n-i + n i=1 z i • 2 n-i a une SLDD + -représentation com- portant seulement 2n + 1 noeuds, en utilisant l'ordre y 1 • • • y n z 1 • • • z n sur
les variables, alors qu'il n'existe aucune formule en OBDD de taille polynomiale représentant la fonction qui vaut 1 quand f ( #y • #z ) ≥ 2 n et 0 sinon. Les autres preuves sont similaires, en adaptant la fonction f .

Ces résultats sur AADD et SLDD contrastent avec le cas du langage ADD, qui satisfait toutes les transformations CUT (les γ-coupes s'obtiennent par une procédure simple de fusion de noeuds terminaux), et donc également toutes les requêtes MX, ME, CT et CO.

Combinaison, élimination de variables, marginalisation. Aucun des langages considérés ne satisfait les transformations de combinaison ou d'élimination de variables dans leur version non bornée ; ce n'est pas surprenant si l'on observe que (i) la combinaison disjonctive non bornée (∨C) et l'oubli (FO) ne sont pas satisfaits par OBDD ; (ii) toute formule d'OBDD peut être vue comme une formule d'ADD, et donc être traduite en temps polynomial en SLDD + (resp. SLDD × , AADD) ; et (iii) la disjonction de plusieurs formules en OBDD revient à couper leur somme (leur combinaison par +) à la valeur minimale (par construction, les contre-modèles de la disjonction sont les #x tels que ϕ( #x ) = 0, la formule résultante peut donc être vue comme une formule en OBDD dont la négation est équivalente à la disjonction de la formule de départ) or tous les langages considérés satisfont CUT min . Les autres preuves s'appuient sur des arguments similaires. Il est [START_REF] Sanner | Affine algebraic decision diagrams (AADDs) and their application to structured probabilistic inference[END_REF] ont proposé une extension de l'algorithme « apply » de Bryant [START_REF] Bryant | Graph-based algorithms for Boolean function manipulation[END_REF], lequel est en temps polynomial sur OBDD pour les opérations AND et OR, pour combiner deux formules en AADD (par +, ×, max ou min) ; cet algorithme est directement adaptable aux autres langages de la famille des VDDs considérés dans cet article. Cependant, la complexité de cette procédure « apply » n'avait pas été identifiée formellement ; un des principaux résultats de cet article est que les combinaisons bornées sont difficiles sur AADD, ce qui implique que l'algorithme en question n'est pas en temps polynomial. Proposition 4.9.

Transformation ADD SLDD+ SLDD× AADD maxBC / minBC √ • • • +BC √ √ • • ×BC √ • √ • maxC / minC • • • • +C / ×C • • • • maxElim / minElim • • • • +Elim / ×Elim • • • • SmaxElim / SminElim • • • • S+Elim / S×Elim • • • • SBmaxElim / SBminElim √ • • • SB+Elim √ √ • • SB×Elim √ • √ • maxMarg / minMarg √ √ √ √ +Marg √ √ √ √ ×Marg √ ? √ ?
-SLDD + , SLDD × et AADD ne satisfont pas maxBC, minBC, SBmaxElim ou SBminElim.

-SLDD × et AADD ne satisfont pas +BC, et donc pas SB+Elim.

-SLDD + et AADD ne satisfont pas ×BC, et donc pas SB×Elim.

La difficulté de maxBC et de minBC vient directement de celle de CUT γ et CUT γ . Celle de ×BC se prouve en considérant les deux fonctions suivantes, qui portent sur des variables booléennes : f ( #x ) = n-1 i=0 x i •2 i (représentation d'un entier par un vecteur de bits) et g( #x ) = 2 n+1 -f ( #x ). Chacune a une SLDD + -représentation (pour l'ordre x 0 x 1 • • • x n-1 ) comportant n + 1 noeuds et 2n arcs ; or il est possible de montrer que la SLDD + -représentation de f × g (pour le même ordre) contient un nombre exponentiel d'arcs au dernier niveau, même après normalisation. Cela montre que toute SLDD + -représentation de f × g est de taille exponentielle. Les autres preuves procèdent de la même manière, avec des fonctions f et g adaptées.

Il y a en fait deux cas dans lesquels la combinaison bornée n'est pas difficile : lorsque le langage considéré est ADD, et lorsque l'opérateur de combinaison est aussi celui servant à agréger les valeurs des arcs dans le langage considéré (l'addition pour SLDD + et le produit pour SLDD × ). Dans ces deux cas, éliminer une variable de domaine borné est également réalisable en temps polynomial -par définition de l'élimination de variable.

Proposition 4.10.

-SLDD + satisfait +BC et SB+Elim.

-SLDD × satisfait ×BC et SB×Elim.

-ADD satisfait BC et SB Elim pour toute opération ∈ {×, +, min, max}.

Pour finir, nous avons prouvé que tous les langages considérés satisfont la marginalisation suivant tous les opérateurs, à l'exception de la ×-marginalisation sur AADD et SLDD + , dont la satisfaction reste à déterminer. -ADD, SLDD + , SLDD × et AADD satisfont Marg, pour toute opération ∈ {+, min, max}.

-ADD et SLDD × satisfont ×Marg.

Conclusion

Cet article a présenté une analyse de la complexité des langages de la famille des VDDs à valeurs réelles pour un ensemble de requêtes et de transformations utiles. Les requêtes liées à l'optimisation se révèlent faisables pour tous les langages considérés, et c'est également le cas de la marginalisation additive et de certaines requêtes liées aux coupes ; ces dernières sont généralement difficiles lorsque l'on cherche à atteindre exactement une valeur γ, et cette difficulté s'étend aux transformations liées. Un des principaux résultats est que les combinaisons, même bornées, sont difficiles sur les VDDs, ce qui implique qu'aucun algorithme « apply » ne peut être en temps polynomial sur les formules en AADD dans le cas général, même pour les opérations simples et « booléennes » que sont min et max. Lorsqu'il est nécessaire de pouvoir effectuer des combinaisons bornées par + (resp. par ×) efficacement, le meilleur compromis temps/espace est offert par SLDD + (resp. SLDD × ). Enfin, il s'avère que la complexité de diverses opérations liées à l'optimisation est meilleure pour les langages de la famille des VDDs que pour d'autres langages dédiés à la représentation de fonctions non booléennes comme VCSP + ; des résultats proches sont à attendre pour les GAI-nets ou les réseaux bayésiens, pour lesquels l'optimisation est également difficile.

  Langages de la famille des VDDs. On s'intéresse à plusieurs langages de la famille des VDDs, à savoir ADD, SLDD et AADD. Chacun d'entre eux impose des restrictions sur les diagrammes admissibles (par exemple, dans le langage ADD seuls les noeuds terminaux portent des valuations ϕ), et définit comment ils sont interprétés. De ce fait, les langages ADD, SLDD et AADD diffèrent à la fois syntaxiquement (par la façon dont les arcs et les noeuds sont étiquetés) et sémantiquement (par la façon dont les formules sont interprétées). La figure 1 présente des représentations d'une même fonction dans chacun de ces langages, dont nous allons maintenant rappeler la définition. Définition 2.3 (ADD). Le langage ADD est le quadruplet C ADD , Var ADD , f ADD , s ADD , avec C ADD l'ensemble des VDDs ordonnés sur X dont chaque noeud terminal est étiqueté par un élément de E = V (en général, E = V = R + ) et dont les arcs ne sont pas étiquetés, et f ADD définie comme suit, pour chaque formule α et chaque affectation #x :

Figure 1 -

 1 Figure 1 -Exemple de VDDs dans trois langages différents, ADD (a), SLDD + (b), et AADD (c), tous trois représentant la même fonction sur les variables {x 1 , x 2 , x 3 } avec D x1 = D x3 = {0, 1} et D x2 = {0, 1, 2}.

  Définition 2.4 (AADD). Le langage AADD est le quadruplet C AADD , Var AADD , f AADD , s AADD , avec C AADD l'ensemble des VDDs ordonnés sur X ayant un unique noeud terminal, et dont les arcs sont étiquetés par un couple q, f dans R + × R + . A des fins de normalisation, la racine de α est également étiquetée par un couple

Figure 2 -

 2 Figure 2 -Exemple de traduction d'une formule du langage ADD vers le langage SLDD + : (a) formule ADD de départ, (b) les poids sont remontés sur les arcs, (c) les noeuds x 2 puis x 1 sont normalisés, et (d) les noeuds isomorphes sont fusionnés.

Définition 3 . 2

 32 (transformations). Soit L un langage de représentation sur X à valeurs dans V, et un opérateur binaire associatif et commutatif sur V.-L satisfait le conditionnement CD si et seulement s'il existe un algorithme en temps polynomial associant à toute formule α de L, toutX ⊆ X , et tout #x ∈ D X , une L-représentation de f L α, #x . -L satisfaitla -combinaison bornée BC si et seulement s'il existe un algorithme en temps polynomial associant à tout couple α, β de formules de L, une L-représentation de f L α f L β . -L satisfait la -combinaison C si et seulement s'il existe un algorithme en temps polynomial associant à tout ensemble {α 1 , . . . , α n } de formules de L, une L-représentation de n i=1 f L αi . -L satisfait la -élimination de variables Elim (resp. d'une seule variable, S Elim) si et seulement s'il existe un algorithme en temps polynomial associant à toute formule α de L et tout ensemble de variables X ⊆ X (resp. tout singleton X ⊆ X ) une L-représentation de #-x ∈D X f L α, #x . -L satisfait la -élimination d'une variable bornée SB Elim si et seulement s'il existe un polynôme p et un algorithme associant à toute formule α de L et toute variable x ∈ X , une L-représentation de #-x ∈Dx f L α, #x en temps p(|α| |Dx| ).

a = 1

 1 et b = 0 quand V = R + , la coupe d'un VDD est en fait une formule du langage MDD[START_REF] Srinivasan | Algorithms for discrete function manipulation[END_REF], une extension directe d'OBDD aux variables non booléennes, qui satisfait à peu près les mêmes requêtes et transformations, comme CO, CD, SE, etc.[START_REF] Amilhastre | Compiling CSPs: A complexity map of (non-deterministic) multivalued decision diagrams[END_REF].4 Carte de compilation des VDDs ordonnés à valeurs dans R + Nous pouvons à présent établir une carte de compilation des VDDs représentant des fonctions à valeur réelle ; on se focalise donc dans la suite de l'article sur le cas V = R + , avec l'ordre habituel ≥ sur R + , et ∈ {max, min, +, ×}. Les langages considérés sont ADD, SLDD × , SLDD + et AADD ; nous laissons de côté SLDD max et SLDD min , ces langages ayant été prouvés équivalents à ADD modulo une transformation polynomiale[START_REF] Fargier | Semiring labelled decision diagrams, revisited: Canonicity and spatial efficiency issues[END_REF].Commençons par les requêtes de base. Chacun des quatre langages examinés satisfait CD : conditionner une formule α par une affectation #x peut être effectué en temps linéaire grâce à un algorithme adapté du cas OBDD. De plus, comme la représentation de toute fonction en une formule réduite (resp. réduite et normalisée) de ADD (resp. AADD, SLDD × , SLDD + ) est unique, et comme les procédures de réduction et normalisation sur chacun des quatre langages sont polynomiales, ils satisfont tous EQ. Enfin, SE est satisfaite par ADD, SLDD + et SLDD × , grâce à une combinaison de coupes, d'inversion des valuations sur les arcs et de traduction vers MDD. Décider si AADD satisfait SE reste en revanche un problème ouvert. Proposition 4.1.

Proposition 4 . 2 .

 42 ADD, SLDD + , SLDD × et AADD satisfont OPT max , OPT min , CUT max , CUT min , ME max , ME min , MX max , MX min , CT max et CT min .

  et à 0 sinon. -L satisfait la validité partielle supérieure (resp. inférieure, resp. égale) VA γ (resp VA γ , resp. VA ∼γ ) si et seulement s'il existe un algorithme en temps polynomial associant tout γ

  et à 0 sinon. -L satisfait l'énumération de max-modèles ME max si et seulement s'il existe un polynôme p et un algorithme associant à toute formule α de L l'ensemble des éléments de CUT max (f L α ) en temps p(|α|, |CUT max (f L Les requêtes ME min , ME γ , ME γ et ME ∼γ (resp. MX min , MX γ , MX γ et MX ∼γ ; resp. CT min , CT γ , CT γ et CT ∼γ ) sont définies de la même façon que ME max (resp. MX max ; resp. CT max ), en utilisant respectivement les ensembles CUT min

α )|).

-L satisfait l'extraction de max-modèle MX max si et seulement s'il existe un algorithme en temps polynomial associant à toute formule α de L un élément de CUT max (f L α ). -L satisfait le comptage de max-modèles CT max si et seulement s'il existe un algorithme en temps polynomial associant à toute formule α de L le nombre d'éléments de CUT max (f L α ).

.

  Proposition 4.4. SLDD + , SLDD × et AADD ne satisfont pas CO ∼γ , sauf si P = NP. Il est clair que la satisfaction de MX ∼γ ou CT ∼γ est une condition suffisante à celle de CO ∼γ ; cela est vrai en toute généralité, et pas seulement sur nos quatre langages à valeurs dans R + . De façon similaire, on peut montrer que ME ∼γ est également une condition suffisante à CO ∼γ , et que CUT ∼γ implique MX ∼γ si l'une des requêtes MX est satisfaite. Proposition 4.5. Soit L un langage de représentation sur X à valeurs dans un ensemble V totalement ordonné par une relation . -Si L satisfait CUT ∼γ et l'une des requêtes MX, alors il satisfait MX ∼γ . -Si L satisfait MX ∼γ , CT ∼γ ou ME ∼γ , alors il satisfait CO ∼γ . Corollaire 4.6. SLDD + , SLDD × et AADD ne satisfont pas MX ∼γ , CUT ∼γ , CT ∼γ ou ME ∼γ , sauf si P = NP. Proposition 4.7. Soit L ∈ {SLDD + , SLDD × , AADD}. -L satisfait ME γ , ME γ , MX γ et MX γ . -L ne satisfait ni CT γ ni CT γ , sauf si P = NP. -L ne satisfait ni CUT γ ni CUT γ .

	Ainsi, excepté VA ∼γ , les requêtes visant la coupe
	exacte d'une fonction représentée par un VDD à un
	seul noeud terminal sont difficiles. La situation est plus
	nuancée lorsque l'on s'intéresse aux coupes inférieure
	et supérieure.

Table 1 -

 1 Résultats sur les requêtes de base, l'optimisation et les γ-coupes ; √ signifie « satisfait », • signifie « ne satisfait pas », et • signifie « ne satisfait pas, sauf si P = NP ». Les résultats pour les problèmes de satisfaction de contraintes valuées additives (VCSP + ) sont données à titre de comparaison.

Table 2 -

 2 Résultats sur les transformations (voir légende des symboles en table 1). ; √ signifie « satisfait », • signifie « ne satisfait pas », et • signifie « ne satisfait pas, sauf si P = NP ». à noter que contrairement au cas d'OBDD, même laélimination d'une seule variable est difficile (l'idée est que la -combinaison des deux formules peut s'obtenir en -éliminant une variable supplémentaire). 4.8. ADD, SLDD + , SLDD × et AADD ne satisfont pas C, Elim ou S Elim, quelle que soit l'opération ∈ {max, min, +, ×}.

	Proposition La question de la combinaison bornée est plus dé-
	licate. Sanner & McAllester

Des noeuds N et M sont dits isomorphes s'ils sont étiquetés par la même variable x, portent (le cas échéant) le même ϕ-label, et qu'il existe une bijection B de Out(N ) dans Out(M ) telle que ∀a ∈ Out(N ), a et B(a) ont le même noeud terminal, partagent la même valeur de Dx, et ϕ(a) = ϕ(B(a)).

Remerciements

Ces travaux ont été en partie soutenus par le projet BR4CP ANR-11-BS02-008 de l'Agence Nationale de la Recherche.