Jean-Marc Capron
email: jean-marc.capron@junia.com

Junia

Verhoeven Arne
email: arne.verhoeven@kuleuven.be

Troch Mathieu
email: mathieu.troch@kuleuven.be

Knockaert Jos
email: jos.knockaert@ugent.be

De Schuyter Dimitri

Saey Philippe
email: philippe.saey@kuleuven.be

Standalone low-cost versatile FPGA-based fault generator for PROFIBUS DP

Keywords:

This paper presents the design, the validation steps and the measurement results of a fault generator device able to disturb the operation of a PROFIBUS DP network, under userdefined conditions. It allows to test the robustness of an industrial network, to test and compare diagnostic tools, and to investigate off-line more complex faults encountered in industry. The core of the design is an FPGA, which results in a very low latency time. It generates trigger signals and imposes faults on the RS485 level up to the maximum bit rate of 12 Mbps. The design choices for fault duration, number of successive faults and skipped triggers, waiting time, etc. allow for the emulation of a wide range of network faults.

INTRODUCTION

Training and more advanced teaching of PROFIBUS DP network technology [1] [START_REF]The New Rapid Way to Profibus DP[END_REF] requires in-depth hands-on exercises, with a variety of realistic and challenging network faults. For training relevant for industry, a lot of attention should be on diagnostics and on troubleshooting network faults [START_REF] Depuydt | PROFIBUS: Theory & Practice, Engineering & Troubleshooting[END_REF]. Also for research, for example to compare the diagnosis reported by different diagnostic tools, to reproduce more complex faults from industry cases during later off-line analysis with similar components, for stress testing of devices [START_REF]CAN-PROFIBUS interface for communication between MV1000 drive and PLC[END_REF] etc., a performant fault generator device would be very useful.

Typical "classic" faults such as short circuit, open circuit, impedance mismatches, power failure of or removing the connector of a slave, removing a module from a slave, etc. are easy to simulate during lab exercises and tests. However, these faults are -relative to the network cycle time -of very long duration and cannot produce short faults impacting only 1 or 2 telegrams, let alone on the same one -originating from the same faulty network device -in consecutive PROFIBUS DP cycles.

Nevertheless, many researchers apply these long "uncontrolled" short and open circuits and impedance mismatches using simple switches [START_REF] Drahos | The PROFIBUS Protocol Observation[END_REF] [6] [START_REF] Mossin | Automatic Diagnosis for Profibus Networks[END_REF]. Also the commercial Procentec fault generator [START_REF]Procentec fault generator[END_REF] uses this approach. The "DP training device" [9] is more advanced, but produces only a limited amount of fault types.

Some researchers [START_REF]Assessment of PROFIBUS networks using a fault injection framework[END_REF] [START_REF] Tran | An Open Implementation of Profibus DP[END_REF] use software implementations of PROFIBUS masters and slaves on microcontrollers (and not industrial devices) at lower bit rates (9.6 up to 500 kbps) than the typical 1.5 Mbps or higher used in industry, for analysis and fault implementation. This method is however flexible compared to the ones mentioned in the previous paragraph and serves its specific research goals.

From a practical view point, removing connectors or modules, switching terminating resistors on/off, … all put a heavy wear on the equipment and should be avoided as much as possible for fault simulation.

Therefore, a low-cost, versatile, standalone, compact device that 1) produces trigger signals 2) imposes a fault (destroy bits, bytes and telegrams, add e.g. an impedance mismatch) has been developed. The trigger events can be used by an oscilloscope to record other signals (shield current, motor torque, etc.) or signals at multiple different network locations. The faults are either imposed by RS485 drivers (specific characters and telegrams, highly dynamic) or by reed relays (e.g. add impedance or inject current in the shield, long duration).

The core of the presented design is an FPGA, that introduces only a very short latency time to detect the trigger conditions, which can be combinations of multiple telegram properties. These trigger conditions can be configured with high flexibility using a simple Human Machine Interface (HMI), and must be editable on-the-go, with instant effect. Finally, the timing and sequence of the output activity (trigger output, fault output) is also configurable: duration, skipped triggers, delay, number of repeats. This paper describes the development and some use cases of a low-cost, compact, versatile and standalone PROFIBUS DP (PB DP) fault generator based on FPGAs. It addresses all standard bit rates from 9.6 kbps up to 12 Mbps, and removes a number of limitations of an older microprocessor based implementation by the authors [START_REF] Saey | Design of an Arduino based low-cost error generator for PROFIBUS DP[END_REF]. The FPGA in Fig. 1 is used for the processing of the incoming information, to decode on-going messages, search for a specific condition and generate output signals (bus disturbance and external digital outputs). This enables real-time analysis and quasi instantaneous reaction time. The configuration of trigger conditions and output characteristics can be modified on-thefly with an LCD display with keyboard switches as HMI, managed by a microcontroller.

The remainder of this paper is organized as follows: PROFIBUS DP is briefly described and design specifications are inferred in Section 2. Section 3 presents the fault generator design: use of FPGAs, serial receiver, trigger analysis, actual fault generation, duration and sequence, etc. Section 4 discusses the validation by simulation. Validation in live networks is discussed in Section 5, which covers the base-line healthy network, the fault appearance over the length of the bus line, 2 use cases, and the overall reaction time.

II. PROFIBUS DP -DESIGN SPECIFICATIONS

A. Network overview and UART character

Detailed descriptions of PROFIBUS DP (PB DP) can be found in e.g. [START_REF]The New Rapid Way to Profibus DP[END_REF], [START_REF] Depuydt | PROFIBUS: Theory & Practice, Engineering & Troubleshooting[END_REF] and [START_REF] Felser | PROFIBUS Manual[END_REF]; the website of PI International can be used for a first exploration [1]. In these paragraphs, some elements that are of interest for the fault generator design are described briefly.

PB DP is most often implemented using RS485 for the Physical Layer (PHY). Fig. 2 shows the typical layout: it features half duplex communication over two lines designated A and B, is actively terminated on both ends of the network (segment). There are up to a typical maximum of 8 segments with each maximum 32 stations in a network. Fig. 3 shows the non-return-to-zero UART (Universal Asynchronous Receiver Transmitter) character. It has one start and stop bit, 8 data bits and a (even) parity bit. Bit rates vary from 9600 bps up to 12 Mbps; typically 1.5 Mbps or higher is used in industry.

B. Telegram formats -Networks used for testing

Fig. 4 shows as example the standard data exchange telegram SD2 (top). The meaning of the telegram parts and the different PB telegram types -SD types -are explained in the middle and bottom table. The tables are based on [START_REF] Felser | PROFIBUS Manual[END_REF], and form the basis of all state machines explained in Section III. For measurements, two basic networks are used in this study: a single master (DPM1, DP Master Class 1) network with 3 slaves (Fig. 5, top), and a network including 3 DPM1 combined with 3 slaves, with token passing between the masters (Fig. 5, bottom). The station addresses are indicated in the bottom right corner.

C. Design specifications and choices

In general, the fault generator should be compact and operate standalone. It is designed for all PROFIBUS DP bit rates up to 12 Mbps. Two ways to inject faults are implemented: destruction of a number of bits or characters via RS485 drivers, and switch e.g. impedances, current sources, etc. via reed relays. The reed relays are in this version -given their relatively slow timing compared to PB DP telegrams and cycle times -controlled manually via the display. The focus in this paper is on fault injection via RS485 drivers and more complex network fault situations, including multiple trigger and sequencing options.

The reaction time should be short compared to the character length, as the fault generator waits to inject a fault until it has checked that the last character that fulfils the trigger condition(s) is actually a valid character. The shortest character length at 12 Mbps is 11 x 83 ns = 917 ns; as reminder, telegrams are composed of several characters.

The trigger conditions are (the content of) each of the bytes in Fig. 4 (top and middle), and can be combined (AND and OR).

The fault duration itself can be expressed in bit times or character (11 bit) times, and ranges from 1 to 999 resp. 1 to 510. The waiting time between applied faults can be up to 17 minutes (units in ms or s (both 1-999) or minutes (1-17)). Skipped triggers can vary between 0 and 9999; the number of successive faults is between 1 and 31. Also these properties can be combined.

D. Coverage of different fault types

Referring to Fig. 7 [14] that provides one of the few detailed overviews of typical faults in industrial networks, the bit destruction part of the fault generator typically emulates "software & devices" (9 %), "other" (20 %) and "EMC" (17 %). The "connectors" part -if intermittent -can also be covered.

"Excessive cable length" and "cable" problems are typically permanently present and not really relevant for the bit destruction part. Some of these could be applied with the reed relays by adding impedances: wrong cable type, too many terminating networks, high transition resistance, etc. [START_REF] Drahos | The PROFIBUS Protocol Observation[END_REF]. An overview of the typical properties of EMI (ElectroMagnetic Interference) phenomena that are at the basis of EMC problems, and the coverage by the developed fault generator, can be found in Fig. 8. With the fault generator, we emulate the effect of the EMI phenomena on the bus communication or on the temporary malfunctioning of a network device (and consequently the "silence" on the bus), by disrupting all communication of the device(s) for the appropriate duration and periodicity. Some industrial examples and their link to EMI phenomena are briefly presented in this paragraph. The combination of PWM (Pulse Width Modulation) used in the output stage of a motor inverter and reflections on the motor cable gives a damped oscillation typically in the range of 500 kHz up to 10 MHz, and relates to the "continuous wave" phenomenon. The PWM waveform itself has a rise time of some tens of ns and can be related to the burst test. Arc welding generates strong magnetic fields in the same lower MHz frequency range; spot welding typically generates low frequency magnetic fields (Hz up to kHz) that are of relatively short duration. Touching metallic parts (a button, a connector) can generate electrostatic discharges; a belt transmission is an example of an "isolated transmission" causing ESD.

In conclusion, the design choices of this fault generator make it well suited for the 48 % "interesting" (short, nondeterministic, complex, single event, etc.) faults, and can be used for a number of other ones, making it a versatile design. Also refer to [START_REF] Depuydt | PROFIBUS: Theory & Practice, Engineering & Troubleshooting[END_REF] and [START_REF]PROFIBUS troubleshooting a.d.h.v permanente logging met COMbricks in ArcelorMittal Gent[END_REF] for a number of industrial fault use cases. (Remark: both RS485 (PROFIBUS) and Ethernet (PROFINET) based networks are in the Indu-Sol statistics. We assume a similar relative spreading, so percentages are order of magnitude.)

III. FAULT GENERATOR DESIGN

A. Using FPGAs

An FPGA (Field Programmable Gate Array) combines on the same die flip-flops, combinatorial logic, and configurable routing. The FPGA hardware approach allows for parallel processing, contrary to a microprocessor's sequential operation. In this application, it enables the fault generator to decode the incoming PROFIBUS bits, and analyse in realtime characters and telegrams for several concurrent criteria, with a reaction delay in the ns range.

In this design the FPGA is used for:

• PROFIBUS serial signal reception • real-time message analysis, with multiple concurrent trigger criteria • flexible fault generation, with configurable duration, repetition rate and fault skipping.

Most real-time message decoding and checking for (combinations of) the user-selectable trigger conditions is done in state machines (SMs), which by nature require a lot of combinatorial functions. As the latter are prone to glitch and delay introduction, attention was paid during FPGA design to keep the signal path between two clock cycles as short as possible, to increase the throughput and keep the operation frequency as high as possible. This requires intensive use of registers, but allows correct operation at maximum bit rate [START_REF]Methodology for FPGA-based system design[END_REF].

B. Serial receiver

To enable optimal operation in noisy environments, the FPGA acquires 16 samples per bit (Fig. 3 shows the individual bits in a PB DP UART character), and 3 samples in the middle of the bit time are kept. The majority of the high/low levels of these 3 is retained, which results in a low sensitivity for noise, glitches, etc. This sample rate defines the main clock frequency in the FPGA: as the maximum bit rate is 12 Mbps, a value of 192 MHz (16 × 12 MHz) is chosen, resulting in a (approximately) 5 ns main clock period.

C. Telegram analysis

PROFIBUS telegrams have different formats (Fig. 4). As trigger conditions must be compatible with any SD-type, the position of each byte (e.g. Source Address SA) is messagetype dependent and thus changes; refer to Fig. 9, reproduced after [START_REF] Felser | PROFIBUS Manual[END_REF].

As example of a small state machine, Fig. 9 (top) shows the different locations (3 rd or 6 th position) of the SA, and the corresponding state machine. As every hardware state machine is independent from the other ones, they all work concurrently and the number of activated trigger conditions has no impact on the reaction time.

D. Fault generation a) Fault implementation

Destroying (a series of) bits, bytes or complete telegrams is either achieved by RS485 transceivers -by far most the versatile and dynamic method -or by reed relays. Two independent PROFIBUS RS485 transceivers (SN65HVD1176) force constant levels on the two bus lines (A and B) of the differential pair of the bus. These are individually controlled by different FPGA outputs for maximum flexibility (Fig. 10). The type of fault -any combination of A and B high or low -can be configured by the user. The transceiver at the input is an ISO1176 (Fig. 1).

Besides triggered "fast" destruction of parts of network telegrams, an "impedance mismatch", a current source to produce a shield current, etc. can be applied to the network using reed relays. The HMI allows the control of 2 normally open reed relays, with a closing time of max. 500 µs (including bouncing) and an opening time of max. 100 µs.

b) Duration -Sequence

The duration of a single fault can be set: its value can be expressed as a number of bit times or character times, and can vary in a very wide range. The minimum duration is one bit time at maximum bit rate, 83 ns at 12 Mbps; maximum 999 bit times can be selected. The maximum duration is chosen at 510 character times (2 maximum-length telegrams); at 9600 bps it is 0.58 s. The maximum duration at the more industrially relevant 1.5 Mbps bit rate is 3.74 ms of "character times" (no time between telegrams). Realistic length telegrams -as slaves typically do not transfer a lot of information -are far shorter than the maximum length; 510 characters is order of magnitude 15-20 telegrams (for one single fault).

The final trigger sequence is fully configurable: • The waiting time ("delay") between successive fault triggers is expressed in ms and can have any value between 1 ms and 17 minutes. • 0 up to 9999 trigger conditions can be skipped ("holdoff") in order to apply faults only after a certain number of triggers. • The number of applied successive faults ("repetition") can also be set to any value between 1 and 31.

By combining these optional functionalities, almost any sequence of fault generation can be defined. Fig. 11 depicts the situation when the number of skipped faults and the number of successive faults are respectively set to 3 and 2, with a non-zero waiting time. c) The FPGA and custom PCB The final system is an assembly of two boards, stacked together. The Terasic DE0-Nano development board (Fig. 12, top) holds the FPGA: a Cyclone IVE Intel® FPGA with 22.320 Logic Elements (LEs) and 154 General Purpose Inputs Outputs (GPIOs). The current application uses 4 % of the available LEs and 14 % of the available GPIOs.

The second one (Fig. 12,bottom) is a custom board with a 8-bit Microchip® microcontroller used for the Human Machine Interface (HMI), and interfaces with the FPGA via SPI (Serial Peripheral Interface). The HMI (4×16 LCD display and keyboard switches) allows for on-the-fly modifications that are instantly applied. Fig 1 depicts 4 trigger signal outputs from the FPGA: these can be used e.g. to trigger an oscilloscope measuring other than bus signals.

The reaction time of the FPGA is limited to 4 clock pulses (of 5 ns each) by using a pipelined design. The check on the trigger conditions itself starts at the end of each character, to be certain that calculations are performed on a valid character.

IV. VALIDATION BY SIMULATION

The 1 st phase of the system validation was done by gatelevel simulation, after "Place & Route" in the FPGA, and taking into account the real propagation delays introduced by the configurable connections and the logic cells. All simulations were done with ModelSim [17].

To be even closer to real behaviour, an input signal was extracted from a live measurement in a 1.5 Mbps PB DP network. A VHDL testbench was written to read analogue values from the measurement ascii file obtained with an oscilloscope, to convert these to digital values, and finally use these as simulation inputs. It was thus possible to check that the expected functionality was reached both with "real" data but also with simulated data for rather random situations. Fig. 13 shows a simulation result in the case of a Start Delimiter detection. The system was configured to generate a 10 µs output pulse whenever a Start Delimiter was found. Simulation also proved useful to quickly and efficiently validate the system's ability to introduce a waiting time between successive actions, to skip some triggers, and to apply a predefined number of faults. These sequences and combinations can be checked in a flexible way in the simulation phase, but are tedious to check in a live network.

V. VALIDATION IN LIVE PROFIBUS DP NETWORKS

A. Fault injection

Fig. 14 shows both differential voltage and absolute voltages on lines A & B during a fault injection at 1.5 Mbps. Line B is forced low and line A is forced high on a cable of 100 m length.

B. Networks and measuring equipment for the use cases

The baseline networks were presented in Chapter II (Fig. 5).

A UART decoding oscilloscope Tektronix DPO 4054B with isolating probes [18] was used for measurements on up to 4 points in the network (Fig. 15, top). Besides UART decoding by the oscilloscope, a MATLAB script was developed for further analysis. The trigger outputs of the fault generator can be used by extra oscilloscopes to determine the behavior of other network components (e.g. digital outputs of slave stations, analog torque or speed signals of drive systems, etc.).

Fig. 15 (bottom) shows a number of diagnostic tools that are connected to analyze what is actually reported on each fault: two ProfiCores with ProfiTrace software, a COMbricks (all Procentec), a diagnostic repeater (Siemens), and a PROFIBUS Inspektor (Indu-Sol). A short discussion on the reporting of these diagnostic devices -also depending on their location -is presented in the use cases. However, a detailed analysis of their diagnosis is beyond the scope of this paper.

C. Use case 1: destroying 2 consecutive telegrams to a slave

The following set-up is configured in the fault generator settings: 2 consecutive SD2 telegrams from DPM1 (address 74) to the slave with address 34 are destroyed every 10 s. Line B is forced high and line A low so that B-A is positive; the network bit rate is 1.5 Mbps and the fault duration is 3 characters. In Fig. 17 a ProfiTrace recording (at the side of the master) is shown. As the slave doesn't receive a request from the DPM1 twice in a row, and consequently does not respond, the master's repeat limit is exceeded. "Repeat (lost)" is indicated the second time. The master waits for the next cycle to set parameters (indicated with "Sync"). When the slave is ready, it will (later) again get in the communication sequence.

Although a detailed analysis of what the different diagnostic tools report is not within the scope of this paper, we can briefly indicate the possibilities for analysis and comparison. All diagnostic tools detect this fault. It is seen either as a restart or a sync of slave 34. Some tools installed close to the source also detect repeats, some also detect illegals (close to the destination). D. Use case 2: destroying token passes between masters Some measurements and short analysis of the stability behavior of the token ring between DP masters have been described in e.g. [START_REF]Assessment of PROFIBUS networks using a fault injection framework[END_REF]. These are limited to 500 Kbps (not a typical PROFIBUS DP bit rate for industrial applications); e.g. [START_REF] Tran | An Open Implementation of Profibus DP[END_REF] even goes as low as 19200 bps in particular tests. In contrast to these severe limitations, the developed fault generator destroys token passes in a freely configurated sequence, to industrial DPM1 stations, and at a high bit rate (in a 1.5 Mbps network, a 6 Mbps one for the reaction time measurement) until the token ring is reconfigured (Fig. 5).

The following set-up is configured in the fault generator settings: 3 consecutive SD4 Token Pass telegrams to DPM1 with address 2 are destroyed every 10 s. Line B is forced high and line A low, so that B-A is positive; the network bit rate is 1.5 Mbps. The fault duration is 3 characters, in this case lasting longer than the remainder of the telegram: the trigger is reached at the end of the 2 nd character in the SD4 telegram. In Fig. 19 a ProfiTrace recording (at the side of the master) is shown. The Master on address 1 notices no communication from any master within the slot time, and repeats the token pass to Master station 2 two times. Station 2 is removed from the LAS (List of Active Stations), and the token is passed from 1 to 3. The latter doesn't expect it from 1, so it is repeated before station 3 accepts the token.

Brief analysis: all diagnostic tools detect this fault, either as a repeat (close to the source) or as an illegal (close to the destination). The COMbricks -in this case a Head Station Type 1C (HW V1.9; SW V1.303), with as Repeater a Type 1 (HW V1.4; SW V1.14) -does not indicate repeats for token passes.

E. Overall reaction time

The reaction time of the FPGA is 4 x 5 ns (Section III). The typical remaining time delays for the generation of the fault trigger are measured in Fig 20, that shows a SD4 token passing telegram in a 6 Mbps network. Channel 4 on the oscilloscope now shows the trigger signal. Channel 2 (light blue) is at the fault generator, trigger condition is fulfilled at the end of the last telegram character "01", so that there is a clear view on the destruction (line B is H, line A is L). From the end of "01" (which is correctly indicated by the decoding, at the end of 2 "H" bits of 167 ns each) to the start of the trigger pulse is about 70 ns. The input delay of the optocoupler is max. 55 ns, the FPGA reaction time is 20 ns, and the output optocoupler introduces typically 31 ns of delay time; the components are listed in Section III D. The 70 ns in the measurement is thus within the specifications.

From "trigger condition fulfilled" to start of destruction is 80.4 ns (cursor measurement in Fig. 20, insert); at 6 Mbps it means that the character after the one that fulfils the trigger condition is destroyed (11 x 167 ns = 1.84 µs). Also at 12 Mbps, it is the 1 st character after the one that fulfils the trigger condition that is destroyed (one character takes 11 x 83 = 913 ns), which means that for all bit rates the character after fulfilling the trigger conditions is destroyed.

VI. CONCLUSIONS AND FUTURE WORK

A low-cost, versatile and configurable trigger and fault generator for PROFIBUS DP has been developed. It proves very useful for training purposes, analysis of the behavior of diagnostic tools and for in-depth testing of more complex industrial problems. It covers all PROFIBUS DP bit rates up to 12 Mbps, and it covers 48 % of the "interesting, highly dynamic" faults.

The reaction time of the FPGA -to calculate if the trigger conditions are fulfilled -is limited to 4 clock cycles of 5 ns. The trigger condition itself is checked at the end of the character that fulfils the trigger condition. The trigger signal is typically available 70 ns after the end of the character that fulfils the trigger condition. Total reaction time to the fault impact on the bus itself is about 80 ns.

Total cost is less than € 200 (using vendors providing quick delivery of components, so a further decrease of the price is possible), without a mounting box.

As future application, it is planned to use the fault generator in research concerning "big data" analysis of bus phenomena in real-time for early detection of bus failures. Finally, the idea of a fault generator for Ethernet based industrial networks remains to be explored.

Fig. 1 .

 1 Fig. 1. Main components of the PROFIBUS DP fault generator.

Fig. 2 .

 2 Fig. 2. Layout of the PROFIBUS DP RS485 Physical Layer.

Fig. 3 .

 3 Fig. 3. UART character of PB DP: non-return-to-zero, 8 databits, 1 start and 1 stop bit, even parity.

Fig. 4 .

 4 Fig. 4. Standard data exchange telegram SD2 (top), meaning of the telegram bytes (middle) and different PB DP telegram types.

Fig. 5 .

 5 Fig. 5. Networks used for verification of the fault generator.

Fig. 6

 6 Fig. 6 shows the healthy single master network with measuring equipment as in Fig. 15. The bottom figure provides a detailed view at the beginning of the middle telegram, for 4 locations on the cable. Given the cable length and the extra connectors -acting as small extra impedancesthe bit signals are slightly degraded, but fine and at good voltage levels. Channel 4 -after the diagnostic repeatershows "restored" signals with extra delay caused by the diagnostic repeater. One can observe the run time of the signal over the cable.

Fig. 6 .

 6 Fig. 6. Healthy network signals at 1.5 Mbps.

Fig. 7 .

 7 Fig. 7. Overview of typical network interventions of Indu-Sol. The figure combines the data provided in the 2019 and 2020 Vortex reports.

Fig. 8 .

 8 Fig. 8. Overview of EMI phenomena, indicating typical duration and coverage by the fault generator.

Fig. 9 .

 9 Fig. 9. (Top) Source Address position in PB DP telegram. (Bottom) State machine for Source Address trigger.

Fig. 10 .

 10 Fig. 10. Forcing the fault on the RS-485 network.

Fig. 11 .

 11 Fig. 11. Example of a sequence with waiting time ≠ 0, skipped faults = 3 and successive faults = 2.

Fig. 12 .

 12 Fig. 12. The final assembly: FPGA board (top) and custom board (bottom).

Fig. 13 .

 13 Fig. 13. Gate-level simulation result: Start Delimiter detection.

Fig. 14 .

 14 Fig. 14. Oscilloscope measurement of fault injection at 1.5 Mbps, showing both differential voltage and absolute voltages on lines A & B.

Fig. 15 .

 15 Fig. 15. Measuring equipment used for the validation in live networks.

Fig 16 (

 16 Fig 16 (left) shows healthy data exchange telegrams left from the middle of the trace. The telegram in the middle of the oscilloscope image is destroyed, as well as the repeated telegram in the right part. Fig. 16 (right) shows in detail the 3 destroyed characters: these are only mildly shifted in voltage level at the master side (source of the telegram, and quite far away from the imposed fault levels), and on all the other locations a complete destruction can be observed.

Fig. 16 .

 16 Fig. 16. Use case 1 oscilloscope recording. Left figure: the telegram to station 34 is destroyed, and the repeat (towards the right) also. Right figure: detail of the destroyed telegram.

Fig. 17 .

 17 Fig. 17. ProfiTrace recording of Use case 1.

Fig 18 (

 18 Fig 18 (left) shows 3 destroyed SD4 telegrams to station 2, the first one under the orange "T" mark on top. The right figure shows a detail of a destroyed SD4 telegram on 4 locations. Again, these are only mildly shifted in voltage level at the master side and still correct (source of the telegram, and quite far away from the imposed fault levels), and on all the other locations a complete destruction can be observed.

Fig. 18 .

 18 Fig. 18. Use case 2 oscilloscope recording. Left figure: 3 SD4 telegrams to station 2 are destroyed, the first one under the orange "T" dot on top. Right figure: detail of a destroyed SD4 telegram.

Fig. 19 .

 19 Fig. 19. ProfiTrace recording of Use case 2.

ACKNOWLEDGMENT Bram Vanseveren (UGent), Annemarie Kokosy and Bruno Stefanelli (both Junia-ISEN), Jos De Brabanter (KU Leuven) and Frederic Depuydt (now ArcelorMittal Gent, formerly at KU Leuven) for advice and support. Engineering staff of ArcelorMittal Gent for inspiration and advice. This work was funded by the Interreg Va 2 Seas project 2S01-049 INCASE.


Olivier Pivert
email: pivert@enssat.fr

Henri Prade
email: prade@irit.fr

Handling Uncertainty in Relational Databases with Possibility Theory -A Survey of Different Modelings

Keywords: Possibility theory, Relational databases, Uncertainty Inconsistency, Data cleaning _

Mainstream approaches to uncertainty modeling in relational databases are probabilistic. Still some researchers persist in proposing representations based on possibility theory. They are motivated by the ability of this latter setting for modeling epistemic uncertainty and by its qualitative nature. Interestingly enough, several possibilistic models have been proposed over time, and have been motivated by different application needs ranging from database querying, to database design and to data cleaning. Thus, one may distinguish between four different frameworks ordered here according to an increasing representation power: databases with (i) layered tuples; (ii) certainty-qualified attribute values; (iii) attribute values restricted by general possibility distributions; (iv) possibilistic c-tables. In each case, we discuss the role of the possibility-necessity duality, the limitations and the benefit of the representation settings, and their suitability with respect to different tasks.

Introduction

Many authors have made proposals to model and handle relational databases involving uncertain data. In particular, the last two decades have witnessed a blossoming of researches on this topic (cf. [START_REF] Suciu | Probabilistic Databases. Synthesis Lectures on Data Management[END_REF] for a survey of probabilistic approaches). Even though most of the literature about uncertain databases uses probability theory as the underlying uncertainty model, some approaches rather rest on possibility theory [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF]. The initial idea of applying possibility theory to this issue goes back to the early 1980's [START_REF] Prade | Lipski's approach to incomplete information databases restated and generalized in the setting of Zadeh's possibility theory[END_REF][START_REF] Prade | Generalizing database relational algebra for the treatment of incompleteuncertain information and vague queries[END_REF]. This was short after the introduction of the idea of a "fuzzy database", for which various proposals were made, ranging from fuzzy relations (thus having weighted tuples) to ordinary relations with tuples of fuzzy values (represented by fuzzy sets), or more simply with tuples of weighted values. These different views developed by several authors were not necessarily referring to possibility theory; see [START_REF] Bosc | An introduction to the fuzzy set and possibility theory-based treatment of flexible queries and uncertain or imprecise databases[END_REF] for references. Since this time, several possibilistic representations have been introduced, and it is useful to clarify their respective roles.

As we will discuss in Sect. 3, the possibilistic framework constitutes an interesting alternative to the probabilistic one, notably because of its qualitative nature. In this paper, we provide a survey of different modelings of uncertain data with possibility theory. The remainder is structured as follows. In Sect. 2, we recall some notions about uncertain databases and their interpretation in terms of possible worlds. Section 3 is devoted to a presentation of four possibilistic database models, with different levels of expressiveness. Section 4 discusses a specific topic where uncertain data management can play a role, namely data cleaning. Section 4.2 points out a sample of issues deserving further investigations. Finally, Sect. 5 concludes the paper and outlines some short-term research perspectives.

About Uncertain Databases and Possible Worlds

In the context of uncertain databases, two kinds of uncertainty are considered: tuple-level uncertainty (where the existence of some tuples in a relation is uncertain, i.e., is more or less probable/possible) and attribute-level uncertainty (where some attribute values in some tuples may be ill-known or uncertainly known). The latter case can be seen as more general than the former, since a tuple involving uncertain attribute values may be translated into a set of mutually exclusive uncertain tuples (involving only ordinary attribute values). An attribute value represented as a disjunctive weighted set can be interpreted as a probability distribution or a possibility distribution depending on the underlying uncertainty model considered. From a semantic point of view, an uncertain database D can be interpreted as a set of usual databases, called possible worlds W 1 , ..., W p , and the set of all interpretations of D is denoted by rep(D) = {W 1 , ..., W p }. Any world W i is obtained by choosing a value in each disjunctive set appearing in D. One of these (regular) databases is supposed to correspond to the actual state of the universe modeled. The assumption of independence between the sets of candidates is usually made and then any world W i corresponds to a conjunction of independent choices, thus the probability, or possibility, degree associated with a world is computed using a conjunction operator, namely, the product, or "min", respectively.

When processing a query, a naive way of doing would be to make explicit all the interpretations of D in order to query each of them. Such an approach is intractable in practice and it is of prime importance to find a more realistic alternative. To this end, the notion of a representation system was introduced by Imielinski and Lipski [START_REF] Imielinski | Incomplete information in relational databases[END_REF]. The basic idea is to represent both initial tables and those resulting from queries in such a way that the representation of the result of a query q against any database D denoted by q(D), is equivalent (in terms of worlds) to the set of results obtained by applying q to every interpretation of D, i.e.: rep(q(D)) = q(rep(D)) where q(rep(D)) = {q(W ) | W ∈ rep(D)}. If this property holds for a representation system ρ and a subset σ of the relational algebra, ρ is called a strong representation system for σ. From a querying point of view, this property enables a direct (or compact) calculus of a query q, which then applies to D itself without making the worlds explicit.

Possibilistic Uncertainty

We first recall some distinctive features of possibility theory before reviewing the different possibilistic representations.

Possibility Theory

Possibility theory departs from probability theory in several respects. Possibility theory involves two dual set functions: the possibility Π and the necessity N such that N (A) = 1 -Π( Ā), while probability is self-dual, namely P (A) = 1-P ( Ā). This provides room for modeling epistemic uncertainty, including total ignorance. Indeed, Π(A) = 1 does not prevent to have also Π( Ā) = 1 in case of complete ignorance about A (while Π(A) = P ( Ā)(= 1/2) does not distinguish situations of genuine equiprobability from situations where, due to ignorance, one applies the Insufficient Reason Principle). Π (and N ) are associated with a possibility distribution π, defined from a universe U to a scale such as scale [0, 1], where ∀A ⊆ U, Π(A) = max u∈A π(u). Due to the use of max and min operations, possibility and necessity functions are more "qualitative" than the probabilistic models involving sum and product.

Still, possibility theory may be quantitative or qualitative [START_REF] Dubois | Possibility theory: qualitative and quantitative aspects[END_REF]. In the first case, the whole scale [0, 1] is used, and possibility and necessity may be thought as upper and lower bounds of an unknown probability (then conditioning is based on product rather than "min"). However, possibility theory does not require the use of the scale [0, 1], but can be defined with any linearly ordered chain (e.g., a finite subset [0, 1] including 0 and 1), or more generally any lattice, and is then qualitative. Moreover, possibility theory has a logical counterpart, namely possibilistic logic [START_REF] Dubois | Automated reasoning using possibilistic logic: semantics, belief revision, and variable certainty weights[END_REF] (which involves only lower bounds of necessity degrees, which can be viewed as certainty levels), and generalized possibilistic logic [START_REF] Dubois | Generalized possibilistic logic: foundations and applications to qualitative reasoning about uncertainty[END_REF] (which involves both set functions). Besides, two other set functions are of interest in possibility theory, namely the guaranteed possibility, ∆(A) = min u∈A δ(u), and the dual set function, where δ is a possibility distribution. In bipolar representations [START_REF] Dubois | An overview of the asymmetric bipolar representation of positive and negative information in possibility theory[END_REF], one uses a pair of possibility distributions (δ, π) for distinguishing between values u such as π(u) = 0 that are excluded, from values u ′ such as δ(u ′ ) > 0 that are guaranteed to be possible to some extent (since, e.g., they were observed), assuming the consistency condition δ ≤ π (expressing that what is guaranteed to be possible cannot be excluded).

Possibilitistic Representations

There is not a unique possibilistic data model. The existing models serve different purposes. From the least to the most expressive, we can distinguish four possibilistic models for uncertain data which have been actually proposed:

-databases with layered tuples; -tuples involving certainty-qualified attribute values; -tuples involving attribute values restricted by possibility distributions; -possibilistic c-tables.

Layered Tuples. The idea, here, is just to provide a complete ordering of the tuples in the database according to the more or less strong confidence we have in their truth. This can be easily encoded by associating a possibility level with each tuple. This results in a layered database: all the tuples having the same degree are in the same layer (and only them). Those tuples having a possibility level equal to 1 may also be associated with a certainty level equal to 1, while the others with a possibility level strictly less than 1 are not certain at all; this means that any possible world database contains all the tuples at level 1, while the other tuples may or may not be present in a particular possible world; see [START_REF] Link | Possibilistic functional dependencies and their relationship to possibility theory[END_REF] for details. This modeling is not very expressive since it provides no indication on what attribute values in the tuple are particularly uncertain. In that respect, it may be considered as a modeling that is too poor from a querying perspective. Still, it has been shown useful for design purposes by providing a setting for attaching certainty levels to functional dependencies (FDs) (through a duality relation with the possibility levels of the tuples that are violating the FDs). Then, this enables the generalization of Armstrong's axioms by attaching certainty levels, and the extension of Boyce-Codd/3rd Normal Forms approaches to database design in the presence of uncertain tuples, by taking advantage of the levels [START_REF] Link | Relational database schema design for uncertain data[END_REF]. Such a possibilistic model is also useful for handling keys [START_REF] Koehler | Logical foundations of possibilistic keys[END_REF] and cardinality constraints [START_REF] Hall | Cardinality constraints on qualitatively uncertain data[END_REF][START_REF] Roblot | Possibilistic cardinality constraints and functional dependencies[END_REF] in presence of uncertain data.

Certainty-Qualified Attribute Values. In this model [START_REF] Pivert | A certainty-based model for uncertain databases[END_REF], attribute values (or disjunctions thereof) are associated with a certainty level (which is the lower bound of the value of a necessity function). This amounts to associating each attribute value with a simplified type of possibility distribution restricting it 1 . Different attributes in a tuple may have different certainty levels associated with their respective values. Then a tuple may be associated with a certainty level, which is the minimum of the certainty levels associated with the attribute values of the tuple, in agreement with the minitivity of necessity functions. Still this global certainty level should not be confused with the possibility level of the previous approach. In terms of possible worlds, a tuple associated with such a certainty level correspond to several tuples with a possibility level. Indeed consider the simple example of a tuple made of two attribute values a, and b, associated respectively with certainty α and β: this yields as possible worlds a, b with possibility 1, a ′ , b with possibility 1 -α, a, b ′ with possibility 1 -β, a ′ , b ′ with possibility min(1 -α, 1 -β), where a ′ (resp. b ′ ) is any value distinct from a (resp. b) in the attribute domain to which a (resp. b) belongs.

This model has some advantages with respect to querying: (i) it constitutes a strong representation system for the whole relational algebra (up to some minor restrictions); (ii) it does not require the use of any lineage mechanism and the query complexity is close to the classical case; (iii) the approach seems more robust with respect to small changes in the value of degrees than a probabilistic handling of uncertainty (see the last section of [START_REF] Pivert | A certainty-based model for uncertain databases[END_REF]). Moreover, there exists a simplified version of this model, see [START_REF] Pivert | Database querying in the presence of suspect values[END_REF], that uses a scale with only three certainty levels ("completely certain","somewhat certain", "not at all certain"). This makes the assessment of certainty particularly easy. Besides, another approach with the same formal type of modeling, but where certainty is evaluated in terms of subsets of sources (together with their reliability level) makes it possible to rank-order the answers to a query also on such a basis [START_REF] Pivert | Querying uncertain multiple sources[END_REF].

Attribute Values Restricted by General Possibility Distributions. In this "full possibilistic model" [START_REF] Bosc | About projection-selection-join queries addressed to possibilistic relational databases[END_REF], any attribute value can be represented by any possibility distribution. Moreover, representing the result of some relational operations (in particular the join) in this model requires the expression of dependencies between candidate values of different attributes in the same tuple, which leads to the use of nested relations. In [START_REF] Bosc | About projection-selection-join queries addressed to possibilistic relational databases[END_REF], it is shown that this model is a strong representation system for selection, projection and foreign-key join only. The handling of the other relational operations requires the use of a lineage mechanism as in the probabilistic approaches. This model makes it possible to compute not only the more or less certain answers to a query (as in the previous model), but also the answers which are only possible to some extent.

Possibilistic c-tables. This model is outlined in [START_REF] Pivert | Possibilistic conditional tables[END_REF]. The possibilistic extension of c-tables preserves all the advantages of classical c-tables (for expressing constraints linking attribute values) while the attribute values are restricted by any kind of possibility distribution. This model generalizes the two previous ones. In fact, possibilistic c-tables, as probabilistic c-tables, can be encompassed in the general setting of the semiring framework proposed by Val Tannen et al.

Data Cleaning

This section first provides a brief overview of two approaches that respectively (i) allow you to query inconsistent databases, and (ii) take advantage of a possibilistic modeling for cleaning the data, before suggesting new lines of research.

Some Existing Approaches

In the presence of inconsistent data, two points of view may be taken. The first one consists in cleaning the database so as to make it consistent, either by means of an automated process [START_REF] Ilyas | Trends in cleaning relational data: consistency and deduplication[END_REF], or by an interactive approach. The second one, such as Consistent Query Answering (CQA) approaches [START_REF] Bertossi | Database Repairing and Consistent Query Answering[END_REF], takes into account the inconsistencies at query processing time.

An approach corresponding to this second line of thought is described in [START_REF] Pivert | Detecting suspect answers in the presence of inconsistent information[END_REF]. It aims at warning the user about the presence of suspect answers in a selection query result, in the context of a classical database (that may include data inconsistent with some functional dependencies). Roughly speaking, the idea is that such elements can be identified inasmuch as they can also be found in the result of negative associated queries. The notion of a suspect answer can be refined by introducing some gradedness in terms of cardinality (number of functional dependency violations in which the tuple is involved) or similarity (by relaxing the equality constraint of a functional dependency into an approximate equality). However, this approach, for the moment, does not involve any uncertainty degree associated with attribute values or tuples. In other words, it handles only inconsistency but not uncertainty.

A possibilistic approach to data cleaning has been recently proposed in [START_REF] Köhler | Qualitative cleaning of uncertain data[END_REF]. This approach belongs to the research trend aimed at restoring a form of consistency in the database. Still, the approach identifies tuples that are suspect or even fraudulous. This is done independently from any particular query. This relies on a model closely related to the layered-tuple-based model reviewed above. However, it is used in the reverse way, since it starts with certainty-valued constraints (called business rules) from which one computes the confidence levels associated with the tuples (on a qualitative scale: "normal"/"suspect"/"fraud"), by solving a minimal possibilistic vertex cover (taking into account the number of violations in which the tuples are involved). Here these are the possibility levels of the tuples that are revised in order to restore the (graded) consistency.

Some Issues Deserving Further Investigations

A first extension we may think of is to introduce certainty degrees in the first of the two approaches reviewed in the preceding section (reference [START_REF] Pivert | Detecting suspect answers in the presence of inconsistent information[END_REF]). This means extending the querying method keeping the data as they are and indicating which answers are suspect, to the setting of the certainty-based model described in Sect. 3. In the original model, an answer is suspect as soon as there exists a repair (w.r.t. a functional dependency) of the query result to which it does not belong. In the extended context, the notion of repair becomes naturally graded2 , as well as the concept of suspiciousness (now appreciated both in terms of the certainty degrees attached to the values of the concerned tuples and in terms of the number of functional dependencies violated by the tuples).

Another interesting issue is to unify the above view with the possibilistic approach to data cleaning reviewed in the previous section (reference [START_REF] Köhler | Qualitative cleaning of uncertain data[END_REF]). We can observe that, although the outputs of the two approaches are quite similar (tuples assigned with a certainty degree expressing different levels of suspiciousness), the inputs are completely different: in one case, constraints with certainty levels, in the other case, attribute values with certainty levels. However, it seems clear that the approach [START_REF] Pivert | Detecting suspect answers in the presence of inconsistent information[END_REF] can also be extended by introducing functional dependencies with certainty levels and keeping all of the attribute values completely certain (rather than the opposite as suggested in the paragraph above). Then, this will make the two approaches easier to compare.

Conclusion

In this brief survey, we have tried to make clear that there exist different possibilistic models, with different levels of expressiveness, but also dedicated to different database tasks (design, data cleaning, querying). Other worth mentioning issues are the modeling of null values [START_REF] Arrazola | Extrapolation of fuzzy values from incomplete data bases[END_REF] and the extrapolation of missing data [START_REF] De Tré | Null values in fuzzy databases[END_REF]. Two kinds of tasks, in our opinion, are particularly worth investigating: (i) a practical comparison of the certainty-based model (which offers a rather good simplicity/expressivity compromise) with probabilistic approaches; (ii) the comparison and the cooperation between different possibilistic data cleaning tools and probabilistic ones. Another line of thought which, we think, might be of interest, is to consider causality issues for evaluating the responsibility in inconsistencies, for which AI probabilistic models have been considered in a database perspective [START_REF] Meliou | Causality and explanations in databases[END_REF], while there also exist possibilistic counterparts to these AI models [START_REF] Dubois | A glance at causality theories for artificial intelligence[END_REF].

Then the attribute value, or more generally the disjunction of possible values is/are considered as fully possible, while any other value in the attribute domain is all the less possible as the certainty level is higher. In case of full certainty these other values are all impossible. This is a particular case of the certainty qualification of a fuzzy set, here reduced to a singleton, or in any case to a classical subset. There are other basic qualifications of a fuzzy set in possibility theory, for instance in terms of guaranteed possibility (rather than in terms of necessity as in certainty qualification), or which lead to enlarge the core, or to reduce the support of the fuzzy set, see[START_REF] Dubois | What are fuzzy rules and how to use them[END_REF] for the four canonic transformations; see also[START_REF] González | Qualification of fuzzy statements under fuzzy certainty[END_REF] for hybrid transformations combining enlargement with uncertainty.

For example, assume Peter has two ages, each with a certainty level, the levels being denoted by α and β respectively. Then the FD name → age is violated with a certainty degree that is equal to min(α, β).


Jean Lieber
email: jean.lieber@loria.fr

Emmanuel Nauer

Henri Prade

Gilles Richard

Making the Best of Cases by Approximation, Interpolation and Extrapolation

Keywords: Analogy, Analogical proportion, Approximation Interpolation, Extrapolation _

Case-based reasoning usually exploits source cases (consisting of a source problem and its solution) individually, on the basis of the similarity between the target problem and a particular source problem. This corresponds to approximation. Then the solution of the source case has to be adapted to the target. We advocate in this paper that it is also worthwhile to consider source cases by two, or by three. Handling cases by two allows for a form of interpolation, when the target problem is between two similar source problems. When cases come by three, it offers a basis for extrapolation. Namely the solution of the target problem is obtained, when possible, as the fourth term of an analogical proportion linking the three source cases with the target, where the analogical proportion handles both similarity and dissimilarity between cases. Experiments show that interpolation and extrapolation techniques are of interest for reusing cases, either in an independent or in a combined way.

Introduction

Case-based reasoning (CBR) [START_REF] Richter | Case-Based Reasoning: A Textbook[END_REF] aims at solving a new problem-the target problem-thanks to a set of cases (the case base), where a case is a pair consisting of a problem and a solution of this problem. A source case is a case from the case base, consisting of a source problem and one of its solutions. The classical approach to CBR consists in (i) selecting source cases similar to the target problem and (ii) adapting them to solve it. In such a view, the target and the source are compared in terms of similarity, which is a (two-valued or gradual) binary relation, while information about the way they differ is not really considered in general.

In this paper, in addition to the binary relation of similarity (which is the basis of approximation), two other relations are considered: the betweenness and the analogical proportion, which in a way or another leave room to dissimilarity.

Betweenness is a ternary relation stating that an object is "between" two other objects. It is used as an interpolation principle: if the target problem is between two source problems then it is plausible that a solution of it is between the solutions of these source problems. In a graded setting, this suggests that if the target problem is closer to one of two source problems, its solution should be closer as well to the solution to the corresponding source problem. In the Boolean setting, betweenness view may lead to several potential solutions, except if the solutions of the two source problems coincide.

Analogical proportion is a quaternary relation: four objects a, b, c and d are in analogical proportion if "a is to b as c is to d". A logical modeling of it [START_REF] Miclet | Handling analogical proportions in classical logic and fuzzy logics settings[END_REF][START_REF] Prade | From analogical proportion to logical proportions[END_REF] has pointed out that it expresses that "a differs from b as c differs from d (and vice-versa)", and that"what a and c have in common, b and d have it also". Thus, analogical proportion is a matter of both dissimilarity and similarity. The fact that we are no longer considering similarity only, enables us to escape the strict vicinity of known cases, and to perform a form of adaptation for free. More precisely, in a CBR perspective, we use it as an extrapolation principle: if the target problem and three source problems are in analogical proportion, the solutions of these four problems are (likely to be) in analogical proportion as well. Such an analogical jump enables us to extrapolate the solution of the target problem from the solutions of three distinct source problems. An illustration of this is given in [START_REF] Billingsley | Towards analogy-based decision -a proposal[END_REF] where in three distinct situations the recommended actions are respectively to (i) serve tea without milk without sugar, (ii) serve tea with milk without sugar, (iii) serve tea without milk with sugar, while in a fourth situation that makes an analogical proportion with the three others, the action to do would be (iv) "serve tea with milk with sugar".

The approach described in this paper combines the use of closeness, betweenness and analogical proportion for a knowledge-light approach to CBR. In fact, the only source of knowledge used in the inference lies in the case base: there is no domain knowledge nor adaptation knowledge and the similarity is based on some distance function.

Section 2 introduces the notions and notations used throughout the paper and the assumptions it is based on. Section 3 describes the approach for applying approximation, interpolation and extrapolation to CBR. Section 4 provides an evaluation in a Boolean setting. Section 5 presents a discussion and a comparison with related work, while Sect. 6 points out lines for future research.

Definitions, Notations and Assumptions

In this section, definitions are presented in a Boolean setting (objects are tuples of Boolean values). Let p be a positive integer. In the examples, an element of B p is noted without parentheses and commas: (0, 1, 0, 0, 1) is simply noted by 01001. The Hamming distance H on B p is defined by H(a, b) = p i=1 |b i -a i |. For example, with p = 5, H(01001, 11011) = 2.

Boolean Setting

Let

CBR

CBR aims at solving the target problem with the help of the case base. It consists most of the time (1) in selecting relevant source cases (retrieval), [START_REF] Billingsley | Towards analogy-based decision -a proposal[END_REF] in reusing these source cases in order to solve the target problem (adaptation). The other classical steps of CBR are not considered in this paper: they concern the validation-repair of the newly formed case and its potential adding to the case base.

Let P and S be two sets called the universe of problems and the universe of solutions: a problem x (resp., a solution y) is by definition an element of P (resp., of S). Here, P = B m , where m ≥ 1 is a constant. Similarly, S = B n , n ≥ 1. A binary relation on P × S denoted by and read "has for solution" is assumed to exist. Thus, "y solves x" is denoted by x y. A case is a pair (x, y) ∈ P × S such that x y. The case base CB is a finite set of cases. A source case is an element of CB. The target problem is the problem to be solved. Note that is usually not completely known to the CBR system: such a system provides plausible solutions to problems, on the basis of what is known of from the case base.

In some situations, it is assumed that is functional. This assumption means that there exists a function f : P → S such that x y iff y = f(x), for any x ∈ P and y ∈ S.

Betweenness

Let U be a set whose elements are represented by numerical features (including Boolean features). Let a, b, c ∈ U; a is between b and c, denoted by b---a---c, if for every feature i, 5 , Between(01001, 11011) = {01001, 11001, 01011, 11011}. For a logical view on betweenness, we refer to [START_REF] Schockaert | Completing symbolic rule bases using betweenness and analogical proportion[END_REF].

((b i ≤ a i ≤ c i ) or (c i ≤ a i ≤ b i )). 1 Let Between(b, c) = {a ∈ U | b---a---c}, for b, c ∈ U. For example, in U = B

Analogical Proportion

Let U be a set. An analogical proportion on U is a quaternary relation between four elements a, b, c and d of U, read "a is to b as c is to d" and denoted by a:b::c:d, having the following properties (see, e.g. [START_REF] Prade | From analogical proportion to logical proportions[END_REF]), for any a, b, c, d ∈ U:

Reusing Cases by Approximation, Interpolation and Extrapolation

This section describes the three mentioned approaches: approximation, interpolation and extrapolation. For an integer k ≥ 1, case retrieval can be done by considering ordered sets of k source cases. This principle is detailed in Sect. 3.2 and applied in Sects. 3.3, 3.4 and 3.5 respectively for k = 1, 2, and 3. The combination of these three approaches is discussed in Sect. 3.6. Let us start with an example.

A Basic Example

In order to support the intuition, we consider the following example where a suitable dish type (described via 3 two-valued attributes, i.e., S = B 3 ) has to be suggested to an individual (described via 8 two-valued attributes, i.e., P = B 8 ). The 8 attributes representing an individual x have the following semantics: x 1 : x suffers from gout, x 2 : x has diabetes, x 3 : x is allergic to nuts, x 4 : x does not eat mammal meat (beef, pork, etc.), x 5 : x needs to have a regular calcium supplement, x 6 : x needs to have a regular iron supplement, x 7 : x likes vegetables, and x 8 : x does not like dairy products. A dish type y is represented via 3 attributes: y 1 : y is a dish with sauce, y 2 : y is based on starchy food (e.g., a pasta dish), y 3 : y is a dish with fish. x y can be read as: y is a suitable dish type for x. For a healthy individual 00010010 (with no specific requirement), all dishes are suitable. Therefore, is not functional in this application, as several types of dishes might be suitable for the same individual. The 3 approaches of case reuse developed in this paper can be applied to this application as follows (where y j is a suitable class of dish for x j ):

Approximation: If an individual x tgt is not far from x 1 , it is plausible that a suitable dish for x tgt will not be far from a suitable dish y 1 for x 1 . Interpolation: If an individual x tgt is between x 1 and x 2 ; it is plausible that a suitable dish for x tgt will be between a suitable dish y 1 for x 1 and a suitable dish y 2 for x 2 . Extrapolation: If an individual x tgt is as similar to x 3 as x 2 is similar to x 1 , it is plausible that a suitable dish for x tgt will be as similar to y 3 as y 2 is similar to y 1 .

General Principle

Let k ∈ {1, 2, 3}: the approach presented here covers approximation (k = 1), interpolation (k = 2) and extrapolation (k = 3). Two (k + 1)-ary relations are considered: Rel P on P and Rel S on S. Ideally, it would be assumed that these relations have the following properties, for (x 1 , . . . , x k , x k+1 ) ∈ P k+1 and (y 1 , . . . , y k , y k+1 ) ∈ S k+1 , with the hypothesis that ∀j ∈ [1; k + 1], x j y j :

if Rel P x 1 , . . . , x k , x k+1 then Rel S y 1 , . . . , y k , y k+1
However, this assumption is usually too strong: since the relation is only partially known to the CBR system, it seems odd to have such a certain relationship about given by the pair (Rel P , Rel S ). So, only the following relaxed form of this property is assumed:

if Rel P x 1 , . . . , x k , x k+1 and x j y j for j ∈ [1; k + 1]
then it is plausible that Rel S y 1 , . . . , y k , y k+1

This property (1) can be used for CBR. Let x tgt be the target problem. A candidate is an ordered set of k cases ((x 1 , y 1 ), . . . , (x k , y k )) ∈ CB k such that Rel P (x 1 , . . . , x k , x tgt ). Based on this notion, the following CBR steps can be specified: retrieval: The set of candidates is computed. adaptation: For a candidate ((x 1 , y 1 ), . . . , (x k , y k )), it is plausible that the solution y tgt of x tgt satisfies Rel S (y 1 , . . . , y k , y tgt ).

Let Candidates be the set of candidates. When Candidates = ∅, the approach fails. Let potentialSols be the multiset of y ∈ S such that (x, y) ∈ Candidates. When there are several distinct solutions in this multiset, there is a need for a function to integrate these solutions into one. Let integrate : potentialSols → y ∈ S be such a function. The nature of this function can be different, depending on the solution space. When S = B (or, more generally, a set of low cardinality) then integrate can be a simple vote. When S = B n , the integration could be a component by component vote, for example: integrate({{001, 001, 010, 111, 111}}) = 011 (with an arbitrary choice in case of ties).

Reusing Cases by Singletons: Approximation

When k = 1, candidates are singletons and source cases are considered individually in relation to the target problem. Usually Rel P and Rel S binary relations are related to the notion of similarity and denoted x 1 ≃ x 2 and y 1 ≃ y 2 . When a distance dist is available on the universe, ≃ is defined as a ≃ b iff dist(a, b) ≤ τ dist where τ dist > 0 is a fixed threshold. Applying the general principle (1) leads to: if x 1 ≃ x 2 and x j y j for j ∈ {1, 2} then it is plausible that y 1 ≃ y 2 i.e., similar problems have similar solutions, a principle often emphasized in CBR (see e.g., [START_REF] Dubois | Flexible control of case-based prediction in the framework of possibility theory[END_REF]). Back to our initial example, let us consider 2 individuals with close profiles (in terms of Hamming distance), e.g., x 1 = 00010010 and x 2 = 00010011. In that example, H(x 1 , x 2 ) = 1 (x 2 does not like dairy product), and a dish type y 2 = 011 without sauce, at distance 1 of y 1 = 111 (a dish type suitable for x 1 ) will be suitable for x 2 .

Figure 1 summarizes the approximation method with an algorithm.

Reusing Cases by Pairs: Interpolation

When k = 2, candidates are pairs, relations Rel P and Rel S are betweenness on P and on S. The general principle (1) applied here leads to: if x 1 ---x 3 ---x 2 and x j y j for j ∈ {1, 2, 3} then it is plausible that y 1 ---y 3 ---y 2

Applied to CBR, a retrieved pair {(x 1 , y 1 ), (x 2 , y 2 )} ∈ Candidates is such that x 1 ---x tgt ---x 2 and then adaptation takes advantage of the inferred information y 1 ---y tgt ---y 2 . A way to get a unique solution is to have y 1 = y 2 , which entails y tgt = y 1 as a candidate solution for x tgt . If Candidates = ∅, the equality y 1 = y 2 can be relaxed in dist(y 1 , y 2 ) ≤ τ dist (where dist is here a distance function on S). In that case, uniqueness of y tgt is not guaranteed anymore. By contrast, if Candidates is considered to be too large, it can be restricted by allowing only the pairs {(x 1 , y 1 ), (x 2 , y 2 )} such that dist(x 1 , x 2 ) ≤ τ between , where τ between > 0 is a given threshold.

Fig. 2. The interpolation method (for the situation in which the solutions of the retrieved cases are equal). Back to our initial example, let x tgt = 11010010, (x 1 , y 1 ) = (01110010, 001), and (x 2 , y 2 ) = (10010010, 001) (i.e. H(x 1 , x 2 ) = 3): x tgt , x 1 and x 2 differ only in the fact that the chosen individuals have/do not have gout/diabetes/allergy to nuts. y 1 = y 2 = 001 is the solution "dish without sauce, not based on starchy food, with fish". Since x 1 ---x tgt ---x 2 , a solution is y tgt ∈ Between(y 1 , y 2 ) = {y 1 }, i.e., y tgt = y 1 = y 2 .

Figure 2 summarizes the interpolation method in an algorithm.

Reusing Cases by Triples: Extrapolation

When k = 3, candidates are triples. Rel P and Rel S are analogical proportions on P and on S. The property (1) applied here leads to: if x 1 :x 2 ::x 3 :x 4 and x j y j for j ∈ {1, 2, 3, 4} then it is plausible that y 1 :y 2 ::y 3 :y 4 Applied to CBR, an element of Candidates is a triple ((x 1 , y 1 ), (x 2 , y 2 ), (x 3 , y 3 )) of source cases such that (i) x 1 :x 2 ::x 3 :x tgt and (ii) the equation y 1 :y 2 ::y 3 :y has a solution. Such a solution, unique in the Boolean setting, is considered as a plausible solution of x tgt . Back to our example where we are searching for a suitable dish type y tgt for an individual x tgt :

x 1 = 00001011 y 1 = 010 x 2 = 00100010 y 2 = 110 x 3 = 10001011 y 3 = 001

x tgt = 10100010 y tgt = ???

The relation x 1 :x 2 ::x 3 :x tgt holds, and the equation y 1 :y 2 ::y 3 :y has a unique solution y tgt = 101. Our principle tells us that y tgt = 101 is a suitable option for x tgt . If we consider the intended meaning of the parameters, x tgt has gout, no diabetes, is allergic to nut, is not refractory to meat, has no need for calcium nor iron supplement, likes vegs and dairy. The dish type y tgt = 101 describing fish with sauce and no starchy food is suitable for this type of individual.

Figure 3(a) summarizes the extrapolation method in an algorithm and Fig. 3(b) presents a more efficient method described further.

Combining These Approaches

Now, we have three methods, approximation, interpolation and extrapolation, to solve a problem. These methods are plausible and incomplete: for a target problem x tgt , each of them may fail either by providing an incorrect solution or by not providing any solution at all. A complete discussion of the options for combining these methods is out of the scope of this paper and constitutes a future work. However, this section discusses some ideas about the design of a good combination method. A simple way to combine these methods is to use a preference relation between them: if the preferred method provides a solution, this is the solution returned, else the second preferred method is tried, and so on (this simple combination method is summarized in Fig. 4). This makes sense since a method may provide results unfrequently but with high plausibility and should be tried before a method providing frequent results with lower plausibility. Now, given the three methods, how can such a preference relation be chosen? For this purpose, an analysis of the case base may help. In particular, for the extrapolation method, it has been shown that the functions f such that x 1 :x2 ::x 3 :x 4 entails f(x 1 ):f(x 2 )::f(x 3 ):f(x 4 ) for each (x 1 , x 2 , x 3 , x 4 ) ∈ P 4 are the affine functions [START_REF] Couceiro | Analogy-preserving functions: a way to extend Boolean samples[END_REF]. 2 Thus, if is functional ( = f) and f is affine, then the extrapolation method never gives an incorrect solution. If f is closed to an affine function, then this method gives good results (and should be highly ranked in the preference relation). A measure of closeness to affinity is the BLR test [3] that can be run on the case base.

Another approach to method combination consists in having a preference between methods depending on the target problem. For this purpose, an idea is to associate to the output of each method a score that is relative to the confidence of the method wrt its output: the preferred method is the one with the higher score. For example, the approximation method would have a high confidence if many source cases support the returned solution and few ones go against it. A similar principle can be applied for interpolation and extrapolation.

Evaluation

The objective of the evaluation is to study the behaviour of the three approaches, on various types of Boolean functions, in order to determinate which approach is the best and in which circumstancies. First experimental results are presented and a combination method based on the preference relation is proposed according to these results.

Experiment Setting

In the experiment, P = B 8 and S = B 3 , as in the running example. is assumed to be functional: = f. The function f is randomly generated using the following generators that are based on the three main normal forms, with the purpose of having various types of functions:

CNF f is generated in a conjunctive normal form, i.e., f(x) is a conjunction of n conj disjunctions of literals, for example f(x) = (x 1 ∨ ¬x 7 ) ∧ (¬x 3 ∨ x 7 ∨ x 8 ) ∧ x 4 .
The value of n conj is randomly chosen uniformly in {3, 4, 5}. Each disjunction is generated on the basis of two parameters, p + > 0 and p -> 0, with p + + p -< 1: each variable x i occurs in the disjunct in a positive (resp. negative) literal with a probability p + (resp., p -). In the experiment, the values p + = p -= 0.1 were chosen.

DNF f is generated in a disjunctive normal form, i.e., it has the same form as for CNF except that the connectors ∧ and ∨ are exchanged. The parameters n disj , p + and p -are set in the same way. Pol is the same as DNF, except that the disjunctions (∨) are replaced with exclusive or's (⊕), thus giving a polynomial normal form. The only different parameter is p -= 0 (only positive literals occur in the polynomial normal form).

The case base CB is generated randomly, with the values for its size: |CB| ∈ {16, 32, 64, 96, 128}, i.e. |CB| is between 1 16 and 1 2 of |P| = 2 8 = 256. Each source case (x, y) is generated as follows: x is randomly chosen in P with a uniform distribution and y = f(x).

Each method may lead to several solutions. Let Y be the multiset of these solutions. The function integrate introduced at the end of Sect. 3.2 aims at associating to Y a unique element y ∈ S. Here, integrate consists in making a vote on each component:

y i = argmax y i ∈Y i multiplicity(y i , Y i )
, where Y i is the multiset of the y i for y ∈ Y.

Let ntp be the number of target problems posed to the system, na be the number of (correct or incorrect) answers (ntpna is the number of target problems for which the system fails to propose a solution), and sscapa be the sum of the similarities between the correct answer (according to the generated function f) and the predicted answer, where the similarity between two solutions y 1 and y 2 is computed by 1 -H(y 1 , y 2 )/n (with n = 3 since S = B n = B 3 ). For each method, the following scores are computed:

The precision prec is the average of the ratios sscapa na .

The correct answer rate car is the average of the ratios sscapa ntp .

The average is computed on 1 million problem solving for each function generator, requiring the generation of 1060 f for each of them. The average computing time of a CBR session (retrieval and adaptation for solving one problem) is about 0.8 ms (for k = 1), 19 ms (for k = 2) and 2 ms (for k = 3) on an current standard laptob.

The parameters for each method has been chosen as follows, after preliminary tests based on precision: approximation: τ dist = 1 on P; interpolation: τ dist = 0 on S (i.e., y 1 = y 2 ), τ between = 2; extrapolation: All the triples in analogy with x tgt are considered. combination: The chosen preference method is: interpolation preferred to approximation preferred to extrapolation for CNF and DNF, and extrapolation preferred to interpolation preferred to approximation for Pol.

For the sake of reproducibility, the code for this experiment is available at https://tinyurl.com/CBRTests, with the detailed results (generated functions and details of the evaluation).

A Note About Implementation. A naive algorithm for implementing each k ∈ {1, 2, 3} method is in O(|CB| k ) (cf. Figs. 1, 2 and 3(a)). However, this complexity can be reduced for interpolation to search Candidates by iterating only on pairs of cases ((x 1 , y 1 ), (x 2 , y 2 )) ∈ CB 2 such that H(x 1 , x 2 ) ≤ τ dist . For extrapolation, the complexity can be separated in an offline and on online part (cf. Fig. 3(b)). The offline part is in O(|CB| 2 ) and generates a hashtable structure over keys representing the differences between x 1 and x 2 (considered as vectors in R m ). For example, key(01001, 11010) = (-1, 0, 0, -1, 0). The online part is in O(|CB| 2 ) in the worst case (and frequently closer to O(|CB|))3 and searches all the (x, y) ∈ CB such that key(x, x tgt ) = key(x 1 , x 2 ), which is equivalent to x 1 :x 2 ::x:x tgt .

Results

Figure 5 pictures the detailed results given in Table 1. The result precisions shows that, for CNF and DNF, interpolation gives better results than approximation and extrapolation, and also that approximation gives better results than extrapolation. However, when examining the results wrt the correct answer rate, interpolation has a low performance, especially when the case base is small (|CB| ∈ {16, 32}), due to the difficulty to find two candidates for the betweenness relations.

The results are different for Pol, for which, extrapolation provides better results. This result can be explained by the functions that have been generated which are close to affine functions, affine functions for which extrapolation always returns a correct answer [START_REF] Couceiro | Analogy-preserving functions: a way to extend Boolean samples[END_REF]. For DNF, the second best approach wrt precision is approximation. One more time, the weakness of the two best methods (extrapolation and interpolation) is their low correct answer rates, and it must be noted that, in all situations, approximation provides a better car, especially when the case base is small. Finally, combining the three approaches by preference ordering (interpolation, then approximation and then extrapolation for DNF and CNF, and extrapolation, then approximation and then interpolation for Pol) improves the results provided using only approximation, as expected.

The elaboration of a better combination method constitutes a future work. However, some elements relative to this issue are discussed here. A simple yet promising approach would be to estimate the average precision-and hence, the preference relation-on the basis of the case base, using a leave-one out approach: for each case (x, y) ∈ CB, the three methods are run with the target problem x tgt = x and the case base CB \ {(x, y)}, and the results given by the three methods are compared with the known solution y tgt = y, which enables us to compute the average precision for each method.

Another issue to be studied carefully is whether it is worth searching for a good combination method. Indeed, if all the methods are strongly correlated, their combination would not give much improvement. For this purpose, a preliminary test has been carried out that computes the covariance of the events "incorrect answer for method k" and "incorrect answer for method ℓ", with k, ℓ ∈ {1, 2, 3} and k = ℓ: cov kℓ = P kℓ -P k P ℓ where P kℓ estimates the probability that the methods k and ℓ provide an incorrect answer, given that they both provide an answer, P k estimates the probability that the method k provides incorrect answers, given that it provides an answer, and P ℓ is defined similarly. The results on the generated data are: cov 12 = cov 21 ≃ 0.90, cov 23 = cov 32 ≃ 0.41, and cov 13 = cov 31 ≃ 0.27. This can be interpreted as follows. The high correlation between approximation and interpolation is mainly due to the tight bounds used in the experiments for interpolation. By contrast, extrapolation is much less correlated with the other methods. This suggests the complementarity of extrapolation, hence the worthiness of studying with more depth the combination issue.

Discussion and Related Work

An important issue raised in this paper is that the reuse of multiple cases (k ≥ 2) does not necessarily rely on similarity (or not only): in the general situation, it relies on two (k + 1)-ary relations on P and S, that may be non reducible to binary similarity relations. These relations structure the problem and solution spaces. Similar issues are addressed in other works of the CBR literature. For example, (simple or multiple) reuse may have profit of adaptation hierarchies on P and S [START_REF] Bergmann | Building and refining abstract planning cases by change of representation language[END_REF][START_REF] Branting | Stratified case-based reasoning: reusing hierarchical problem solving episodes[END_REF][START_REF] Smyth | Case-based design[END_REF]. Another example of relation used for multiple case retrieval and adaptation is the use of diversity: the retrieved cases should be diverse in order to better contribute to the solving of the target problem [START_REF] Mcsherry | Diversity-conscious retrieval[END_REF]. The main originality of this work is the use for CBR of betweenness and analogical proportion, two domain-independent relations that can be implemented in many formalisms (though it has been considered only in the Boolean setting here), e.g. on strings [START_REF] Lepage | Purest ever example-based machine translation: detailed presentation and assessment[END_REF], and that enables to apply to CBR the principles of interpolation and extrapolation, in addition to the already frequently used principle of approximation.

The extrapolation approach based on analogical reasoning can be connected to the work of adaptation knowledge learning (AKL) in CBR, as explained hereafter. Most approaches to AKL consist in learning adaptation rules using as training set a set of source case pairs ((x i , y i ), (x j , y j )) [START_REF] Craw | Learning adaptation knowledge to improve case-based reasoning[END_REF][START_REF] D'aquin | Case base mining for adaptation knowledge acquisition[END_REF][START_REF] Hanney | Learning adaptation rules from a case-base[END_REF]. A similar idea consists in considering one of pairs as an adaptation case [START_REF] Jarmulak | Using case-base data to learn adaptation knowledge for design[END_REF][START_REF] Minor | Case-based adaptation of workflows[END_REF]. With (x 1 , y 1 ) a retrieved case, it can be adapted to solve x tgt if the difference from x 1 to x tgt equals the difference from x i to x j , which can be formalized using analogical proportion by x i :x j ::x 1 :x tgt . Then, the adaptation consists in applying on y 1 the difference from y i to y j , which amounts to solving the equation y i :y j ::y 1 :y. Therefore, one contribution of this work is the formalization of casebased adaptation in terms of analogical proportions on the problem and solution spaces.

The idea of applying analogical inference based on analogical proportions in CBR has been first advocated and outlined recently [START_REF] Prade | Analogical proportions and analogical reasoning -an introduction[END_REF], based on the fact that such an approach has given good quality results in classification [START_REF] Bounhas | Analogy-based classifiers for nominal or numerical data[END_REF] in machine learning on real datasets. Interestingly enough, analogical proportions can be always found in such datasets, and the results obtained can be favorably compared to those yielded by nearest neighbor methods. The ideas of interpolative and extrapolative reasoning can be found in the setting of conceptual spaces furnished with qualitative knowledge [START_REF] Schockaert | Interpolative and extrapolative reasoning in propositional theories using qualitative knowledge about conceptual spaces[END_REF] with an illustration in [START_REF] Schockaert | Interpolation and extrapolation in conceptual spaces: a case study in the music domain[END_REF]. Similar ideas have been applied to the completion of bases made of if-then rules in relation with the idea of analogical proportion [START_REF] Schockaert | Completing symbolic rule bases using betweenness and analogical proportion[END_REF] and to the interpolation between default rules [START_REF] Schockaert | Interpolative reasoning with default rules[END_REF]. However, none of these papers mentions a CBR perspective.

Classical CBR exploits each known case individually, on the basis of its similarity with the target problem. In this paper, we have proposed to extend this paradigm by taking advantage of betweenness and analogical proportion relations for linking the current situation to pairs and triples of known cases. By doing that, we are no longer just proposing the known solution of a case problem as an approximate solution to the current problem, but we are also taking advantage of interpolation and extrapolation ideas that are respectively embedded in betweenness and analogical proportion relations.

We have also provided a first experimental study that shows the precision and the correct answer rate of the approximation, interpolation, extrapolation approaches on various types of functions. Each approach has its own merits. Approximation is simple and is often very efficient. Interpolation provides the most precise results, but may fail to give an answer. Extrapolation is superior to the two other methods when the underlying function is affine or close to be, i.e., exhibits a form of simplicity. Moreover, the results of extrapolation are not much correlated with the results of the two other methods. Experiments also show that combining the approaches may be beneficial. Clearly, one should investigate less straightforward ways for combining the approaches. More experiments would be also of interest for varying more the parameters and for dealing with non functional dependencies between problems and solutions. Experiments have been made on a variety of artificial datasets, showing that the present implementation of extrapolation is especially of interest for datasets close to obey to an affine Boolean function, studying if another form of extrapolation would do better, or if such datasets are often encountered in practice, is a matter of further work.

There are still two other perspectives worth of consideration. First, it would be of interest to see how incorporating domain/retrieval/adaptation knowledge in the process. Lastly, relations Rel P and Rel S have been defined here on B p , but allowing for gradual relations and for nominal and numerical features in the description of problems and solutions would be an important improvement. Such a latter development should be feasible since extensions of analogical proportions have been satisfactorily experienced in classification for handling nominal and numerical features [START_REF] Bounhas | Analogy-based classifiers for nominal or numerical data[END_REF], and the idea of betweenness seems as well to be susceptible of natural extensions to these situations.

  B = {0, 1} be the set of Boolean values. The Boolean operators are denoted by the connector symbols of propositional logic: for a, b ∈ B, ¬a = 1a, a ∧ b = min(a, b), a ∨ b = max(a, b), a ⊕ b = |b -a| (⊕ is the exclusive or) and a ≡ b = ¬(a ⊕ b).

  reflexivity a:b::a:b, symmetry if a:b::c:d then c:d::a:b, central permutation if a:b::c:d then a:c::b:d. In the Boolean setting, the analogical proportion considered is defined on B by a:b::c:d if (a ∧ ¬b ≡ c ∧ ¬d) ∧ (¬a ∧ b ≡ ¬c ∧ d) = 1 that can be read "a differs from b as c differs from d" and "b differs from a as d differs from c". This can also be rewritten ba = dc, but mind that these differences belong to {-1, 0, 1} (-is not an operation that is closed in B). Thus, the patterns abcd such that a:b::c:d are 0000, 1111, 0011, 1100, 0101 and 1010. This analogical proportion can be extended on U = B p by a:b::c:d if a i :b i ::c i :d i for each i ∈ [1, p] Given a, b, c ∈ U, solving the analogical equation a:b::c:y aims at finding the y ∈ U satisfying this relation. It may have no solution, e.g., when a = 0, b = 1 and c = 1. The equation a:b::c:y in B has a solution iff (a ≡ b) ∨ (a ≡ c) = 1 and, when this is the case, the solution is unique: y = c ≡ (a ≡ b).

Fig. 1 .

 1 Fig. 1. The approximation method.

Fig. 3 .

 3 Fig. 3. The extrapolation method (in 2 versions: a simple one (a) and a more efficient one (b)).

Fig. 4 .

 4 Fig. 4. The combination method based on a preference relation on the set of methods {approximation, interpolation, extrapolation}.

Fig. 5 .

 5 Fig.5. Precision and correct answer rate function of the case base size for the three generators, for each method (k = 1, k = 2, k = 3 and "combine", i.e. combination of the three other methods).

Table 1 .

 1 prec and car for k ∈ {1, 2, 3} and combine (c.) for the different generators. CNF prec .87 .97 .80 .84 .88 .97 .81 .85 .90 .96 .84 .89 .93 .96 .86 .92 .95 .96 .88 .94 car .36 .04 .31 .49 .58 .15 .63 .75 .81 .42 .81 .88 .90 .67 .86 .92 .94 .83 .88 .94 DNF prec .87 .97 .80 .84 .88 .97 .81 .85 .90 .96 .84 .89 .93 .96 .87 .92 .95 .96 .88 .94 car .36 .04 .31 .49 .58 .15 .63 .75 .81 .43 .81 .88 .90 .67 .86 .92 .94 .83 .88 .94 POL prec .61 .72 .75 .67 .62 .72 .75 .70 .63 .71 .77 .75 .66 .71 .79 .78 .68 .70 .81 .80 car .25 .01 .18 .34 .41 .04 .44 .57 .57 .14 .66 .73 .64 .27 .75 .78 .68 .40 .79 .80

	|CB| = 16	|CB| = 32	|CB| = 64	|CB| = 96	|CB| = 128
	k = 1 2	3	c. 1 2	3	c. 1 2	3	c. 1 2	3	c. 1	2	3	c.

When these values are Boolean, this can also be written(b i ∧ c i ⇒ a i ) ∧ (a i ⇒ b i ∨ c i ) = 1.

An affine function f : B m → B has the form f(x) = x i 1 ⊕ . . . ⊕ x i q ⊕ c where {i 1 , . . . , i q } is a subset of[1, m] and c ∈ {0, 1}. An affine function f : B m → B n is of the form f(x) = (f 1 (x), . . . , f n (x)) where f j : B m → B is an affine function.

The number of iterations in the for loop is |CB| -1. In each iteration, the set access(key, key table) contains at most (|CB| -1) elements, though in practice, this set contains in general a much smaller number of elements. So, the number of O(1) operations of this online procedure in the worst case is not more than (|CB| -1) × (|CB| -1), hence a complexity in O(|CB| 2 ).