Sorin Stratulat
email: sorin.stratulat@univ-lorraine.fr

E-CYCLIST: Implementation of an Efficient Validation of FOL ID Cyclic Induction Reasoning

Checking the soundness of cyclic induction reasoning for first-order logic with inductive definitions (FOL ID ) is decidable but the standard checking method is based on an exponential complement operation for Büchi automata. Recently, we introduced a polynomial checking method whose most expensive steps recall the comparisons done with multiset path orderings. We describe the implementation of our method in the CYCLIST prover. Referred to as E-CYCLIST, it successfully checked all the proofs included in the original distribution of CYCLIST. Heuristics have been devised to automatically define, from the analysis of the proof derivations, the trace-based ordering measures that guarantee the soundness property.

Introduction. Cyclic pre-proofs for the classical first-order logic with inductive predicates (FOL ID ) have been extensively studied in [START_REF] Brotherston | Cyclic Proofs for First-Order Logic with Inductive Definitions[END_REF][START_REF] Brotherston | Sequent Calculus Proof Systems for Inductive Definitions[END_REF][START_REF] Brotherston | Sequent calculi for induction and infinite descent[END_REF]. They are finite sequent-based derivations where some terminal nodes, called buds, are labelled with sequents already occurring in the derivation, called companions. Bud-companion (BC) relations, graphically represented as back-links, are described by an induction function attached to the derivation, such that only one companion is assigned to each bud, but a node can be the companion of one or several buds. The pre-proofs can be viewed as digraphs whose cycles, if any, are introduced by the BC-relations.

It is easy to build unsound pre-proofs, for example by creating a BC-relation between the nodes labelled by the sequents from a stuttering step. The classical soundness criterion is the global trace condition. Firstly, the paths are annotated by traces built from inductive atoms occurring on the lhs of the sequents in the path, referred to as inductive antecedent atoms (IAAs). Then, it is shown that, for every infinite path p in the cyclic derivation of a false sequent, there is some trace following p such that all successive steps starting from some point are decreasing and certain steps occurring infinitely often are strictly decreasing w.r.t. some semantic ordering. We say that a progress point occurs in the trace when a step is strictly decreasing. A proof is a pre-proof if every infinite path has an infinitely progressing trace starting from some point.

The standard checking method [START_REF] Brotherston | Sequent Calculus Proof Systems for Inductive Definitions[END_REF] of the global trace condition is decidable but based on an exponential complement operation for Büchi automata [START_REF] Michel | Complementation is more difficult with automata on infinite words[END_REF]. It has been implemented in the CYCLIST prover [START_REF] Brotherston | A Generic Cyclic Theorem Prover[END_REF] and experiments showed that the soundness checking can take up to 44% of the proof time. On the other hand, we presented in [START_REF] Stratulat | Cyclic Proofs with Ordering Constraints[END_REF][START_REF] Stratulat | Validating Back-links of FOL ID Cyclic Pre-proofs[END_REF] a less costly, polynomial-time, checking method. The pre-proof to be checked is firstly normalized into a digraph P consisting of a set of derivation trees to which is attached an extended induction function. The resulting digraph counts the companions among its roots, as well as the root of the pre-proof to be checked. Also, all infinite paths in the pre-proof, starting from some point, can be reconstructed by concatenating root-bud paths (rb-paths) in P. Finally, a sufficient condition for ensuring the global trace condition is to show that every rb-path from the strongly connected components (SCCs) of P has a trace that satisfies some trace-based ordering constraints. Therefore, in theory, if the soundness of some pre-proof can be validated with the new method, it can also be validated with the standard one. Implementation. Our method has been integrated in the CYCLIST release labelled as CSL-LICS14, by replacing the standard checking method. The result was called E-CYCLIST. CYCLIST builds the pre-proofs using a depth-first search strategy that aims at closing open nodes as quickly as possible. Whenever a new cycle is built, model-checking techniques provided by an external model checker are called to validate it. If the validation result is negative, the prover backtracks by trying to find another way to build new cycles. Hence, the model checker may be called several times during the construction of a pre-proof.

Here is how our method works. Firstly, the pre-proof is normalized to a digraph P. To each root r from P, the method attaches a measure M (r) consisting of a multiset of IAAs of the sequent labelling r, denoted by S(r). One of the challenges is to find the good measure values that satisfy the trace-based ordering constraints. A procedure for computing these values is given by Algorithm 1.

Algorithm 1 GenOrd(P): to each root r of P is attached a measure M (r) for all root r do M (r) := / 0 end for for all rb-path r → b from a non-singleton SCC do if there is a trace between an IAA A of S(b) and an IAA A of S(r) then add A to M (rc) and A to M (r), where rc is the companion of b end if end for At the beginning, the value attached to each root is the empty set. Then, for each rb-path from a cycle, denoted by r → b, and for every trace along r → b, leading some IAA of S(r) to another IAA of S(b), we add the corresponding IAAs to the values of r and the companion of b, respectively. Since the number of rb-paths is finite, Algorithm 1 terminates.

Algorithm 1 may compute values that do not pass the comparison test for some non-singleton SCCs that are validated by the model checker. For this case, we considered an improvement consisting of the incremental addition of IAAs from a root sequent that are not yet in the value of the corresponding root r. Since the validating orderings are trace-based variants of multiset extension orderings, such an addition does not affect the comparison value along the rb-paths starting from r. On the other hand, it may affect the comparison tests for the rb-paths ending in the companions of r. This may duplicate some IAAs from the values of the roots from the rb-paths leading to these companions. The duplicated IAAs have to be processed as any incrementally added IAA, and so on, until no changes are performed.

Table 1 illustrates some statistics about the proofs of the conjectures considered in Table 1 from [START_REF] Brotherston | A Generic Cyclic Theorem Prover[END_REF], using inductive predicates as N, E, O, and Add, referring to the naturals, even and odd numbers, as well as the addition on naturals. All inductive predicates but p are defined in [START_REF] Brotherston | A Generic Cyclic Theorem Prover[END_REF]. The proofs have been checked with the standard as well as our method. The IAAs are indexed in CYCLIST to facilitate the construction of traces; the way they are indexed influences how the pre-proofs are built. Different indexations for a same conjecture may lead to different proofs (see the statistics for the second and third conjectures). The column labelled 'Time-E' presents the proof time measured in milliseconds by using our method. Similarly, the 'Time' column displays the proof time when using the standard method, while 'SC%' shows the percentage of time taken to check the soundness by the model checker. 'Depth' shows the depth of the proof, 'Nodes' the number of nodes in the proof, and 'Bckl.' the number of back-links in the proof. The last column gives the number of calls for pre-proof validations. The proof runs have been performed on a MacBook Pro featuring a 2,7 GHz Intel Core i7 processor and 16 GB of RAM. It can be noticed that, by using our method, the execution time is reduced by a factor going from 1.43 to 5.

Theorem

Time-E Time SC% Depth Nodes Bckl. Queries The last conjecture was not tested in [START_REF] Brotherston | A Generic Cyclic Theorem Prover[END_REF] and refers to the 2-Hydra example [START_REF] Berardi | Classical System of Martin-Lof's Inductive Definitions is not Equivalent to Cyclic Proofs[END_REF]. A pre-proof of it, reproduced in Figure 1, can also be generated by CYCLIST, as shown in Figure 4. Unfortunately, CYCLIST was not able to validate it using the standard method, the missing figures being denoted by ?. It also may occur that the proposed measure values, as shown in Figure 5 for a non-optimised proof of 2-Hydra, may not pass some comparison tests that succeed with the standard method, even when using the improved version of Algorithm 1. Indeed, this happened while proving N 1 x ∧ N 2 y R(x, y). Luckily, the prover backtracked and finally found the same pre-proof as that originally built with CYCLIST. 1We detail now how our method has been applied for validating the 2-Hydra pre-proof from Figure 4.

O 1 x N 2 x 2 7 61 2 9 1 3 E 1 x ∨ O 2 x N 3 x 4 11 63 3 19 2 6 E 1 x ∨ O 1 x N 3 x 2 9 77 2 13 2 6 N 1 x O 2 x ∨ E 3 x 3 7 52 2 8 1 4 N 1 x ∧ N 2 y Q 1 (x, y) 297 425 40 4 19 3 665 N 1 x Add 1 (x, 0, x) 1 5 76 1 7 1 4 N 1 x ∧ N 2 y ∧ Add 3 (x, y, z) N 1 z 8
The 2-Hydra case. The 2-Hydra problem is a particular case showing the termination of the battle between Hercules and Hydra [START_REF] Dershowitz | The Hydra Battle Revisited[END_REF] when Hydra has at most two heads that hang on the top of necks of different lengths. Hercules prevails if either Hydra has i) no heads at all, or ii) the length of the first neck is 1 unit and it has lost the second head (i.e., the length of the neck is 0), or iii) the length of the second neck is 1 unit, as in Figure 2. Hercules can cut the Hydra's necks according to the following rules. If both necks have strictly positive lengths, then Hercules can cut them such that the first neck is shorter by 1 unit and the second by 2 units (see the case iv in Figure 3). If Hydra has already lost one of the heads and the neck of the other head has a length l of at least 2 units, the first head will have a neck of length l -1 units and the second head a neck of length l -2 units (see the cases v and vi in Figure 3). Next, we introduce the notations, the specification of the inductive predicates, the inference rules, then explain the pre-proof from Figure 4. Contrary to the pre-proof from Figure 1, the CYCLIST preproof is horizontally indented by the level of nodes. The nodes are numbered and labelled by sequents where the comma (,) is replaced on the lhs of the sequents by the conjunction connector (/\).

The axioms defining the inductive predicates N and p are:

⇒ N(0) N(x) ⇒ N(s(x)) ⇒ p(0, 0) ⇒ p(s(0), 0) ⇒ p(x, s(0)) p(x, y) ⇒ p(s(x), s(s(y)))
p(s(y), y) ⇒ p(0, s(s(y))) p(s(x), x) ⇒ p(s(s(x)), 0)

The applied inference rule for each sequent is pointed out at the end of the sequent.

(N L.Unf) [n 1 , n 2 ] generates the nodes n 1 and n 2 by choosing an IAA of the form N(t). If t is a variable, t will be replaced by 0 and s(z), where z is a fresh variable. For the second instantiation, the IAA is replaced by N(z). This represents a progres point. If t is of the form s(t ), the original sequent is reduced to another sequent by replacing the chosen IAA N(s(t )) with N(t ).

(p R.Unf) [n] produces the node n resulting from the replacement of the consequent atom from the sequent labelling n with the condition of some axiom defining p and whose conclusion matches the atom.

(Id) and (Ex Falso) delete trivial conjectures. (Weaken) (resp., (Subst)) [n] is the LK's weakening (resp., substitution) rule [START_REF] Gentzen | Untersuchungen über das logische Schließen[END_REF] whose premise labels n. Finally, (Backl) [n] shows that the current node is a bud for the companion n. The pre-proof from Figure 4 is already normalized and has one non-singleton SCC with three rbpaths.

Our validity method is based on properties to be satisfied locally, at the level of rb-paths. An rbpath r → b is valid if b is "smaller" than r w.r.t. a trace-based multiset extension relation. This relation guarantees the existence of traces following each infinite path p, built from the concatenation of the traces defined for the rb-paths along p. The definitions for the standard and trace-based multiset extension are:

• (standard multiset extension) B < mul A if there are two finite multisets X and Y such that B = (A -X) Y , X = / 0 and ∀y ∈ Y , ∃x ∈ X, y < x holds.

• (trace-based multiset extension) b is "smaller" than r if, after pairwisely deleting the IAAs linked by a non-progressing trace along r → b (the result is X and Y as above), X = / 0 and ∀y ∈ Y , ∃x ∈ X such that there is a progressing trace along r → b between x and y.

In Figure 5, we summarize the result of the application of the improved version of Algorithm 1 to a non-optimized version of the pre-proof from Figure 4, for which the node 27 was denoted as 28. The found measure of the root is the multiset of its IAAs indexed by 2 and 1, i.e., {N 2 (x), N 1 (y)}. In Figure 5, for each rb-path, i -> j denotes that there is a trace linking the root IAA indexed by j to the bud IAA indexed by i, [true ] means that the trace is progressing, and '===> true' informs that the rb-path is valid, as follows:

1. 0 to 28 (27 in Figure 4); the possible traces following this path are: All the above traces are progressing, where the underlined IAAs correspond to progress points. By definition, these rb-paths are valid and conclude that the 2-Hydra pre-proof is a proof, by using arguments as in [START_REF] Stratulat | Cyclic Proofs with Ordering Constraints[END_REF][START_REF] Stratulat | Validating Back-links of FOL ID Cyclic Pre-proofs[END_REF].

[N 1 (x), N 1 (x), N 1 (y), N 1 (y), N 1 (y), N 1 (y), N 1 (x)] and [N 2 (y), N 2 (z), N 2 (z), N 2 (w), N 2 (w), N 2 (w), N 2 (y)], 2
Conclusions and future work. We have implemented in CYCLIST a more effective technique for validating FOL ID cyclic pre-proofs which allows to speed up the proof runs by 5. Besides its polynomial time complexity, an important factor for its efficiency is the lack of the overhead time required to communicate with external tools. In practice, our method can validate pre-proofs that cannot be validated by the CSL-LICS14 release of CYCLIST. Even if we do not have yet a clear evidence, we strongly believe that this also holds for the other way around, as this might have happened for the N 1 x ∧ N 2 y R(x, y) example.

The considered pre-proof examples are rather small. We intend to test our method more extensively and on cyclic pre-proofs from domains other than FOL ID , e.g., separation logic.

  Nx, Ny pxy Nx , Nu px u Nsu, Nx , Nu psx ssu Nx Nsu, Nx, Nu pxssu Nx, Ny pxsy Ny (a)Nx, Ny pxy

Figure 1 :

 1 Figure 1: The Berardi and Tatsuta's cyclic pre-proof of the 2-Hydra example.

Figure 2 :

 2 Figure 2: The cases when Hercules wins.

Figure 3 :

 3 Figure 3: The cases when Hercules cuts the necks of Hydra.

Figure 4 :

 4 Figure 4: The screenshot of the 2-Hydra pre-proof generated by CYCLIST.

Figure 5 :

 5 Figure 5: The E-CYCLIST validation of the 2-Hydra pre-proof from Figure 4.

  . 0 to 21; the possible traces are: [N 2 (y), N 2 (z), N 2 (z), N 2 (y), N 2 (y), N 2 (y), N 2 (y)] and [N 2 (y), N 2 (z), N 2 (z), N 5 (s(y)), N 5 (s(y)), N 1 (s(y)), N 1 (x)], and 3. 0 to 13; the possible traces are: [N 1 (x), N 1 (x), N 1 (y), N 1 (y), N 1 (s(z)), N 1 (s(z)), N 1 (s(z)), N 1 (x)] and [N 1 (x), N 1 (x), N 4 (s(y)), N 4 (y), N 4 (z), N 4 (z), N 4 (z), N 2 (y)].

Table 1 :

 1 Statistics for proofs checked with the standard and our method.

	14	38	2	8	1	16

The source code of the implementation and the examples can be downloaded at https://members.loria.fr/ SStratulat/files/e-cyclist.zip


Laurent Bramerie
email: laurent.bramerie@enssat.fr

Sébastien Lobo

Mathilde Gay

DAC-less and DSP-free 20 Gb/s PAM-4 transmission based on a dual modulation scheme using DML and external modulation

The generation of DAC-less 20 Gb/s PAM-4 using a DML and an external modulator is demonstrated. This dual modulation scheme has been transmitted up to 75-km SSMF with similar performance to PAM-4 DAC transmitter.

Introduction

Network capacities and latencies are two key issues for today's access and data center environments linked to constant traffic growth. To this aim, transmitter requirements are driving significant efforts in finding compact, lowcost and energy efficient solutions. A popular solution proposed to respond to these requirements is to use externally modulated laser (EML) largely used for 10G-class on-off keying transmission. EML presents the advantages of low chirp, compactness, low cost, low driving voltage and high stability [START_REF] Takeuchi | Very High Speed Light-Source Module up to 40 Gb/s Containing an MQW Electroabsorption Modulator-Integrated with DFB Laser[END_REF], [START_REF] Kanazawa | Flip-Chip Interconnection Lumped-Electrode EADFB Laser for 100-Gb/s/λ Transmitter[END_REF], which makes this solution an ideal candidate for such optical communication system especially over 40-80 km fiber in 100 and 400 Gbit/s ER-4 systems [START_REF] Wu | High-speed In 0[END_REF]. To target 100Gclass transmission, 4-level pulse amplitude modulation (PAM-4) using direct modulation (DM) and direct detection (DD) is preferred because of its high spectral efficiency and cost-effectiveness. PAM-4 modulation of EML allowed to reach 112 Gb/s transmission [START_REF] Mestre | Compact InP-Based DFB-EAM Enabling PAM-4 112 Gb/s Transmission Over 2 km[END_REF] using digital-to-analog converter (DAC) to generate PAM-4 and complex digital signal processing (DSP) at the receiver side. To guarantee energy efficiency and low latency in network, DAC-less and DSP-free transmission will be preferred. Dual modulation schemes using external modulators in series (resonators in [START_REF] Dubé-Demers | Low-power DAC-less PAM-4 transmitter using a cascaded microring modulator[END_REF]) or parallel structures (Mach-Zehnder in [START_REF] Lu | DAC-less PAM4 Transmitter using Electro-optic Polymer Dual-drive Mach-Zehnder Modulator with Imbalanced Binary Driving Electronics[END_REF] or electro-absorption modulator (EAM) in [START_REF] Lambrecht | 53 GBd PAM-4 DAC-less low-power (1.5 pJ/b) silicon integrated transmitter[END_REF]) have been demonstrated. However, natively, the EML structure is not directly adapted to DAC-less PAM-4 generation as dual modulation is not possible on this device. Recently, laser modulated EML (LM-EML) with dual modulation on electro-absorption section and on laser section has been used: modulation of the laser section was used as phase modulation to curb chromatic dispersion in a 20 Gb/s single-sideband PAM-4 experiment in [START_REF] Chaibi | Dispersion-uncompensated transmission of NRZ and PAM-4 single-sideband signals using D-EML[END_REF]; whereas it allowed extinction ratio improvement in a 25 Gb/s NRZ transmission in [START_REF] Cano | 25-Gb/s Laser Modulated EML With High Output Power[END_REF]. In this paper, we demonstrate a proof of concept of a new dual modulation scheme allowing PAM-4 modulation without DAC, using direct laser modulation and external modulation. Combined with an optical filter, a 20 Gb/s dispersion-uncompensated transmission up to 75-km SSMF is demonstrated and compared to performance of classical PAM-4 obtained by DAC and direct modulation of an external modulator.

Principle of DAC-less PAM-4 transmitter and experimental set-up

To generate DAC-less PAM-4, we propose simply to use a LM-EML with direct modulation of the laser section (DML) to print the least significant bits (LSB) and to print the most significant bits (MSB) on the electro-absorption modulator section (EAM) as schematized in Fig. 1 a). This solution would fulfill main transmitter requirements described above. The main issue of this technic is the trade-off between the PAM-4 extinction ratio (defined as ratio of outer levels) and the level separation mismatching. Indeed on the contrary to parallel dual modulation schemes which sum the two modulated signals, here the signal is modulated twice in each device in series. We studied numerically this compromise in Fig. 1 b). The metric known as level separation mismatch ratio (RLM) [START_REF] Echeverri-Chacón | Transmitter and dispersion eye closure quaternary (TDECQ) and its sensitivity to impairments in PAM4 waveforms[END_REF], which quantifies the effect of level compression, is represented versus PAM-4 extinction ratio. The PAM-4 transmitter can be considered perfectly linear when RLM = 1. In this study, the EAM extinction ratio varies between 1 and 10 dB and the DML extinction ratio is adjusted in order to vary the ratio of extinction ratio between DML and EAM sections (ERDML/EAM) between 1/3 and 2/3. First observation, whatever ERDML/EAM, RLM is closer to 1 for poor PAM extinction ratio (< 2 dB). Secondly, the RLM drops strongly when PAM extinction ratio increases. On Fig. 2 a), two eye diagrams are represented for RLM of 0.9 and 0.7 respectively. The PAM-4 extinction ratio is clearly more favorable for a RLM of 0.7. Therefore, the dual modulation scheme requires trade-off between PAM-4 extinction ratio and levels compression to guarantee sufficient performance on receiver. An extinction ratio of 5 dB seems a good compromise leading to a maximum RLM of 0.7 when the modulation ratio between DML and EAM is equal to 2/3. In this work, as no LM-EML was available for the experiment, we demonstrate experimentally the proof of concept using two discrete components knowing a directly modulated laser (DML) followed by an external modulator. Fig. 2 b) shows the experimental setup. Two pulse pattern generators (PPG1 and PPG2) are used to generate two 10 Gb/s electrical signal with delayed patterns of pseudorandom binary sequence of length 2 15 -1. The LM-EML is emulated by a DML with an E/O bandwidth of 15 GHz [START_REF] Anet-Neto | Beyond 25 Gbit/s directly modulated, directly detected OFDM using channel flattening by a Fabry-Perot filter[END_REF] followed by a LiNbO3 Mach-Zehnder modulator (MZM). A Fabry-Pérot filter with a slope of 1 dB/GHz is used to improve the DML extinction ratio and dispersion tolerance as proposed in [START_REF] Anet-Neto | Beyond 25 Gbit/s directly modulated, directly detected OFDM using channel flattening by a Fabry-Perot filter[END_REF]. An erbium-doped fiber amplifier (EDFA) was placed after the filter to preamplify before transmission through a standard single-mode fiber (SSMF). An optical attenuator and optical power monitoring allows to adjust the power received by the 28 GHz PIN photodiode electrically amplified with a gain of 12 dB. A clock and data recovery (CDR) is used to carry out PAM-4 demodulation thanks to decision adjustable threshold and to feed the error counter of a bit-error-rate tester (BERT). No DSP is applied in this study.

Results and discussion

As explained in previous section, dual modulation scheme allows to generate PAM-4 signal thanks to a first NRZ modulation on DML and a second NRZ modulation on MZM. Fig 3 presents the different eye diagrams at each modulation stage. In the case of LM-DML, the modulation of laser section presents a lower intensity modulation efficiency than EAM section. So, in our case, MZM modulation would then act as the most significant bit (MSB) and DML modulation as the least significant bit (LSB). As seen on Fig 2 a), the operating point has been chosen from the simulation results allowing a trade-off between an extinction ratio of 5 dB and RLM of 0.7 thanks to a rate modulation ratio of 2/3 between DML and MZM. For a quantitative assessment, the bit-error-rate (BER) is measured and compared to the reference of a standard PAM-4 obtained with a 3 bit DAC to generate the electrical PAM-4 signal feeding the MZM modulator. In this case, the DML is driven continuously and an extinction ratio better than 10 dB is obtained on PAM-4 signal.

In the reference case, the back to back (B2B) curve shows an error floor around 1×10 -8 (Fig. 7) owing from a lack of sensitivity of our photodiode coupled to the CDR. Using the dual modulation the error floor jumps to 8×10 -5 because of a reduction of the extinction ratio in this case (5 dB compared to 10 dB for the reference). After 50-km propagation, the dual modulation and PAM-4 reference are very close with an error floor of 8.5×10 -4 and 2×10 -4 respectively. The BER in the dual modulation case decreases by one decade after 50 km while PAM-4 reference losses four decades. After 75-km, it was impossible to have pattern lock for the reference curve. In the case of dual modulation, an error floor of 1.7×10 -3 is measured thus demonstrating a better robustness to chromatic dispersion. We can see on Fig. 8, the eye diagrams associated to dual modulation and PAM-4 reference after 25, 50 and 75-km.

In the reference case after 75-km we observe a time skew on the eye diagram which is linked to chromatic dispersion effect also explaining the impossibility to measure any BER. In the case of dual modulation, the time skew is less present thanks to the combination of laser chirp and shifted optical filter as observed in previous work [START_REF] Anet-Neto | Beyond 25 Gbit/s directly modulated, directly detected OFDM using channel flattening by a Fabry-Perot filter[END_REF].

Conclusions

We demonstrate experimentally the use of a dual modulation scheme, using direct laser modulation and external modulation, to generated a DAC-less, DSP-free, 20 Gb/s PAM 4 signal. The transmitter assisted by optical filtering allowed transmission over 75 km SSMF with an error floor of 1.7×10 -3 . The BER performance measured after 50 km SSMF are near to classical PAM-4 scheme using DAC and external modulator. Considering previous works on integrated LM-DML [START_REF] Chaibi | Dispersion-uncompensated transmission of NRZ and PAM-4 single-sideband signals using D-EML[END_REF], we are confident on the success of the method using an integrated LM-DML as DACless PAM-4 transmitter.

Fig. 1 :

 1 Fig. 1: a) Principle of DAC-less PAM-4 generation using LM-EML and b) level separation mismatch ratio (RLM) vs. PAM-4 extinction ratio for different ER on DML and EAM

Fig. 2 :

 2 Fig. 2: a) Simulated eye diagrams at the output of the LM-EML for two operating points and b) experimental setup.

Fig. 3 :

 3 Fig. 3: Experimental eye diagrams.

Fig. 4 a

 4 Fig. 4 a) BER vs. received optical power for 10Gbaud PAM-4 and b) Eye diagram after transmission for DAC-less PAM-4 generation using dual modulation and PAM-4 generation using DAC with MZM After 25 km propagation, the BER performance for dual modulation and standard PAM-4 reference are very close to B2B results. In both cases, a shifted optical filter was used. Even for PAM-4 reference, the optical filter indeed allows a better dispersion tolerance provided essentially by a slight side-band filtering. To avoid an overload of the article, only cases including filter are reported.After 50-km propagation, the dual modulation and PAM-4 reference are very close with an error floor of 8.5×10 -4 and 2×10 -4 respectively. The BER in the dual modulation case decreases by one decade after 50 km while PAM-4 reference losses four decades. After 75-km, it was impossible to have pattern lock for the reference curve. In the case of dual modulation, an error floor of 1.7×10 -3 is measured thus demonstrating a better robustness to chromatic dispersion. We can see on Fig.8, the eye diagrams associated to dual modulation and PAM-4 reference after 25, 50 and 75-km.In the reference case after 75-km we observe a time skew on the eye diagram which is linked to chromatic dispersion effect also explaining the impossibility to measure any BER. In the case of dual modulation, the time skew is less present thanks to the combination of laser chirp and shifted optical filter as observed in previous work[START_REF] Anet-Neto | Beyond 25 Gbit/s directly modulated, directly detected OFDM using channel flattening by a Fabry-Perot filter[END_REF].4. ConclusionsWe demonstrate experimentally the use of a dual modulation scheme, using direct laser modulation and external modulation, to generated a DAC-less, DSP-free, 20 Gb/s PAM 4 signal. The transmitter assisted by optical filtering allowed transmission over 75 km SSMF with an error floor of 1.7×10 -3 . The BER performance measured after 50 km SSMF are near to classical PAM-4 scheme using DAC and external modulator. Considering previous works on integrated LM-DML[START_REF] Chaibi | Dispersion-uncompensated transmission of NRZ and PAM-4 single-sideband signals using D-EML[END_REF], we are confident on the success of the method using an integrated LM-DML as DACless PAM-4 transmitter.5. AcknowledgmentsThe DML used in this paper has been provided by III-V lab in the framework of French ANR project DIQDOT (ANR-11-INFR-0003). This work was supported in part by the Contrat de Plan Etat-Région SOPHIE and the French Ministry of Research.6. References

Acknowledgments

The DML used in this paper has been provided by III-V lab in the framework of French ANR project DIQDOT (ANR-11-INFR-0003). This work was supported in part by the Contrat de Plan Etat-Région SOPHIE and the French Ministry of Research.


Emmanuel Netter

"Free" online service in exchange for targeted advertising : the business model with feet of clay 1

Keywords: communication, marketing, publicité, éd. Lilu

The services offered by Facebook and TF1 have in common that they do not cost a euro to their users, while being perfectly profitable for those who exploit them 2 . The financing is in fact provided by advertisers, who are looking for "available human brain time" under a formula that resists the passage of time 3 . The similarities, however, end there: while both the social network and the television channel seek to get a commercial message as far as possible into the minds of those exposed to it, they pursue this common goal using radically different instruments.

Facebook, in principle, is able to paint a very fine portrait of each of its users. It takes the form of a cloud of variables: where you live, who your friends are, what places you frequent during your lunch break and on Saturday nights, which web pages you open and how long it takes before you close them, which books you pretend to read and which ones you actually read. The individual is geolocalized, timed, inserted in a social graph. His or her rich and complex personality, which has been subjected to the flame of algorithmic treatments, is reduced as if by pyrolysis to a clear, dry and supposedly reliable list of his or her centers of interest. The profile thus constituted is sold, by auction in real time, to the highest bidder. The advertising suggestion arrives in conquered territory. Perfectly in line with the target's expectations, it only needs to be whispered to be enthusiastically integrated, in a barely conscious process.

Meanwhile, on the private television channel, the advertiser tries to see the characteristics of the audience through the fog. His vision is no longer individual, but collective: he perceives a herd. From the schedule and the type of program, he will obviously draw a rough diagnosis. For example, advertisements at half-time of a soccer match will be full of shaving foam, roaring cars and musky scented shower gels. But in front of the screen, in reality, there is a young woman concerned about global warming, who sighs with lassitude at the nullity of the proposals that are addressed to her in this way. The commercial is no longer whispered, but shouted, in the hope that it will reach as many friendly ears as hostile minds. It is the famous: "Half of the money I spend on advertising is wasted, but I don't know which half" 4 . This fundamental difference may soon be a thing of the past. On February 13, 2020, the Minister of Culture Franck Riester publicly declared his intention to authorize "segmented advertising" on television, in order to put an end to "an inequity of treatment between television channels and Internet actors" 5 . Technically, the collection of information would pass through the connected televisions or through the "boxes" of the access providers. To the journalist who questioned him, 1 These few lines at the crossroads of personal data protection and business law to pay tribute to one of Strasbourg's masters of business law, forever my laboratory and master's director, without whom I would not be an academic today. 2 TF1 is one of the main French television channels.

and who pointed out that it is possible, on the Internet, to refuse to consent to data processing corresponding to targeted advertising, the minister replied that it was still necessary to work "with the CSA, with telecommunications operators" to ensure the protection of privacy in terms of personalized television advertising. These statements by Mr. Riester are edifying from two perspectives. First, from an economic point of view, because they acknowledge the incredible success of targeted advertising as a source of funding. The invention, in its current form, is not twenty years old, yet it is essentially on this basis that two of the ten largest market capitalizations in the world were built: Alphabet and Facebook. The influx of new converts is therefore not surprising. But the Minister's comments are also remarkable from a legal point of view. They downplay the threats that personal data law currently poses to this model, and suggest that a motivated working group will overcome this simple technical difficulty within a few months. Including the CSA, but not the CNIL, is a spectacular missed opportunity 6 . The whole thing amounts to denial and borders on blindness.

The reality is not well known, but it is this: the targeted advertising market, which already weighs more than 5 billion euros per year in France, and continues to expand rapidly, is threatened with a sudden end by a combination of interpretations of the general regulation on data protection 7 . The text does not impose any direct prohibition on this business model. Neither does the e-privacy directive, which governs the placing of cookies on the terminals (computers or telephones) of Internet users8 . Consequently, the professionals concerned have remained free to imagine that with sufficient effort, they would manage to ensure that their data processing complies with European requirements. In the end, this may not be possible.

One of the most fundamental requirements of the GDPR is that there be lawful basis. Once those that have no chance of being applicable in the area of interest are removed, Article 6 suggests the following possibilities: "The processing is lawful only if, and to the extent that, at least one of the following conditions is met: a) the data subject has consented to the processing of his/her personal data for one or more specific purposes;

(b) processing is necessary for the performance of a contract to which the data subject is a party (...);

(f) processing is necessary for the purposes of the legitimate interests pursued by the controller or by a third party, except where such interests are overridden by the interests or fundamental rights and freedoms of the data subject which require protection of personal data, in particular where the data subject is a child.

The hurdle may be insurmountable for "retargeting" specialists such as the French giant Criteo or data brokers. Such companies are currently under investigation by the French and Irish data protection authorities 9 . Their situation is particularly critical because they trade in information from Internet users without providing any service or being in direct contact with them. It is difficult to see why a user who correctly represents the situation would consent to expose his privacy for their benefit.

The "legitimate interest pursued by the data controller" would seem to be the most serious avenue for them. The G29, the forerunner of the European Data Protection Board (EDPB), also recognized "the economic interest of a company to know as much as possible about its potential customers in order to better target advertising for its products or services" 10 . But this was only the starting point of the reasoning. The interest thus identified must then be weighed against the rights and freedoms of the person concerned: this is the whole specificity of the lawful basis f). However, the G29 considered further on that the processing of targeted advertising, which is particularly intrusive, leads to an unfavourable balance 11 .

Companies like Facebook or Google seem to be in a slightly better position. They are in direct contact with their users and provide them with a pseudo-free service in exchange for access to their personal data. They can take advantage of this position to ask Internet users to consent to the processing of targeted advertising (I). They may also take the more radical view that a user who takes advantage of a service without a grant has, in so doing, agreed to be exposed to advertising messages: what he does not pay in euros, he pays for in other ways (II). However, the first of these positions has already failed in the French courts. The second has not yet been the subject of a national or European decision.

I -Exposure to advertising as a faculty: special consent to data processing

Google had chosen to base its data processing for targeted advertising purposes exclusively on the consent of users. Following collective complaints by the associations La Quadrature du Net (LQN) and None of Your Business (NOYB), the CNIL, in the most important decision in its recent history, was led to rule on the relevance of this choice 12 . The response took the form of an administrative sanction in the amount of 50 million euros.

In this case, the CNIL examined the process by which the new purchaser of a phone powered by an Android operating system is invited to open a Google account, if he does not already have one. Some points of the decision, very important in the absolute, will not be developed here. In particular, the lack of clarity in the privacy policy is not a problem specific to business models based on targeted advertising. Moreover, it is a grievance that can theoretically be remedied. The same is not true of the Commission's criticisms of the chosen lawful basis.

At the time of the account creation, Google checked by default a box by which the Internet user agreed to be addressed advertisements in adequacy with his centers of interest. This implied that his online activities, searches on the engine, choice of YouTube video, travel history ... were used to reveal his tastes. If the user left the default choices unchanged and clicked the "next" button, a "popup window" would appear, which stated: "This Google Account is set up to include personalization features (such as recommendations and personalized ads), which are based on information stored in your account. To change your personalization settings and the information stored in your account, select More options" 13 . The user is then reminded quite clearly of the consequences of his choice, or 10 G29, Opinion 06/2014 on the notion of legitimate interest pursued by the data controller within the meaning of Article 7 of Directive 95/46/EC, 9 April 2014, p. 27. 11 Ibid, p. 35, "Scenario 2". The example imagined by the G29, which features a site selling pizzerias, nevertheless involved much less powerful treatments than those conducted by Google or Facebook. 12 Deliberation SAN-2019-001 of January 21, 2019 : ECC, 2019, No. 5, p. 31, and No. 6, p. 28 rather of his previous non-choice, and given a chance to amend it. In practice, he didn't take it, since everyone's obsession in such cases is to get to the end of the registration process as quickly as possible, by clicking on the most pleasant looking button as soon as it appeared, without any further ado. The narrow elite attentive to these issues could, however, show their vigilance at that moment or, failing that, go at any time to the account settings once created to deactivate the targeted advertisement, which then turned into a simple contextual advertisement. Contextual advertising consists, for example, in displaying a commercial message on the margin of a search query linked to the words that have just been typed (e.g. "hotel in Marrakech"), without trying to identify the particular interests of the person for whom it is intended: this is a return to the Stone Age of advertising, the one in which television is currently blocked, much to Mr. Riester's chagrin14 .

Google had therefore skillfully saved appearances: it was possible to uncheck the box, but those who twice missed the opportunity to do so were caught in the net of custom advertising. He could get out on simple request, because consent to data processing is always revocable (art. 7.3 of the GDR), but he would never do so.

However, this was forgetting Recital 32 of the Regulation, which states: "Consent should be given by a clear affirmative act establishing a freely given, specific, informed and unambiguous indication of the data subject's agreement to the processing of personal data relating to him or her, such as by a written statement, including by electronic means, or an oral statement. This could include ticking a box when visiting an internet website (...)". The CNIL therefore recalled that an opt-in is necessary. An opt-out, even a clever and relatively elegant one, would not be enough. Its decision has been confirmed in all respects by the Conseil d'État15 . The Google company must thus convince the Net surfer to actively check the box by which he accepts to be recipient of targeted advertisements.

This would have been very simple, if it had been possible to make it a condition of access to the pseudo-free service. However, article 7.4 of the GDPR states: "When assessing whether consent is freely given, utmost account shall be taken of whether, inter alia, the performance of a contract, including the provision of a service, is conditional on consent to the processing of personal data that is not necessary for the performance of that contract".. As the EDPB points out, the "coupling" of the data processing and the service is not absolutely prohibited, but the expression "utmost account" means that it will only be allowed in "highly exceptional" cases16 . One of these extremely rare cases, according to the EDPB, would be the case where there is "an equivalent service offered by the same controller which does not imply consent to the processing of personal data for additional purposes"17 .

A question then arises, to which the EDPB unfortunately does not answer: can the alternative service free of advertising tracking be invoiced? Can a company offer the same service, at its choice, "against payment in data" (formula A) and "against payment in euros" (formula B)? The answer is doubtful. Assuming that the supervisory authorities accept the approach in principle, which is not certain, they would probably control the price charged in formula B. If it were too high, they would see an overall result that would push Internet users towards Formula A while extorting their consent, which would be illegal.

A similar problem occurs with cookies. Many sites are still struggling to make the refusal of cookies for advertising purposes as painful as possible for the Internet user. An e-privacy regulation was supposed to succeed the directive of the same name 18 . It was supposed to provide the possibility for Internet users to refuse once and for all this type of cookies in a general setting of their browser. Who would be deprived of it, if it were not to lead to any negative consequences? The EDPB has indeed just specified that it is forbidden for a site to subordinate its access to the acceptance of advertising cookies 19 . The situation becomes the following: you want to access a Google service, or an online media? Would you be so kind as to tick the box by which you agree to have your interests collected, compiled and analyzed? If you don't want to do this, please note that the service will work perfectly... but the ads that will be displayed will be much less exciting! You don't care? Ah...

In this context, the designers of the Android registration path and cookie banners obviously do not try to find out what the Internet user really wants, if he accepts the deal that is proposed to him.

Enter with payment with your data... or enter for free? There is no deal.

The reality is that the 6a lawful basis in the GDPR, consent, was not designed for such a situation. Do you wish, after a purchase on an e-commerce site, that he remembers your bank details to speed up a next purchase? This is a question that really accepts two answers. Would you like your municipality to collect and keep your email address to notify you when road work is going to take place near your home20 ? Do as you please. Your children's school will decorate its next newsletter with a few class photos, will your offspring be able to appear in it? It's up to you.

Google or Facebook services are not really free: you pay for them with data. If we accept the very principle of such a model -but do we accept it? -then it makes no more sense to refuse advertising tracking than to have a drink on the terrace of a café and then tell the waiter that you don't "agree" to pay the bill. The most adequate basis of legality is quite different.

II -Exposure to advertising as an obligation: the necessity of the treatment for the performance of the contract

Let's leave Google's defense strategy before the French authorities for Facebook's defense strategy before the Irish authorities. Banks have their tax havens, data processors their information havens: in Europe, the nirvana is in Dublin. On the desk of the Irish data protection authority, the dust peacefully piles up on files bearing the names of all the world's digital giants. The social network founded by Mark Zuckerberg is accused by the aforementioned associations LQN and NOYB, among others, of carrying out targeted advertising processing without respecting article 6 of the GDPR.

But on what basis of legality does the company claim to operate? The privacy policy, which is particularly opaque, does not allow even an attentive reader to answer this question 21 . However, in an open letter intended to denounce the bogging down of the proceedings before the Irish authority, NOYB revealed the social network's line of defense 22 : "the procedures that were triggered by three complaints filed by noyb.eu two years ago (within the first hours of the GDPR becoming applicable), the Facebook Group openly acknowledges that it simply switched from highly regulated "consent" to an alleged "data use contract". This contract allegedly obliges Facebook to track, target and conduct research on its users. According to Facebook, this switch happened at the stroke of midnight when the GDPR became applicable".

Nothing more is revealed about what the outlines of this data use contract would be, but it is likely to present the use of personal data for advertising purposes as the consideration for the use of the service. It is indeed a synallagmatic contract for valuable consideration. The lawful basis is then 6b: "processing is necessary for the performance of a contract to which the data subject is party ".

And this is the reality of the underlying business model23 . However, cases using 6b are usually situations in which treatment is necessary for the proper performance of an obligation on the professional, and not on the client. The CNIL thus evokes the classic example of an e-merchant forced to process his client's banking data and postal address to collect his payment and deliver the order 24 . In our context, it is the customer who would be supposed to carry out his obligation to expose himself to targeted advertising. The CNIL is very hostile to such a reasoning: "a treatment of advertising targeting on an online service cannot, as a general rule, be considered as objectively necessary for the execution of the contract concluded with the persons concerned, even if the treatment is mentioned in the general conditions of use of the website. Indeed, the use of the service is not conditioned by the implementation of the advertising targeting processing and the fact that this processing is necessary with regard to the business model of the organization or to the economic viability of the website is not sufficient to make it necessary for the execution of the specific contract concluded with the data subjects". The EDPB, for its part, has specifically devoted guidelines to this question. In particular, it states: "(...) Article 6(1)(b) cannot provide a legal basis for online behavioural advertising simply because such advertising indirectly finances the provision of the service. Although such processing may contribute to the provision of a service, it is not in itself sufficient to establish that it is necessary for the performance of the contract in question (...) 25 .

By refusing to see exposure to targeted advertising as a service to be paid for by the Internet user within the framework of a synallagmatic contract for valuable consideration, the EDPB is clearly seeking to protect the user as well as possible. But other people want to do him good, such as the TGI of Paris. Google having claimed that consumer law did not apply to users of its services, since they are offered free of charge, the court replied as follows: "it follows from the foregoing that, if the company Google offers to users of the disputed platform services without monetary consideration, it markets for consideration to partner companies, advertisers or merchants, data, whether personal or not, submitted free of charge by the user when registering or browsing and using this "Google+" device. Thus, a service without monetary payment cannot be considered as a completely free service, the provision of data collected free of charge and then used and valued by the Google company must be analyzed as a "benefit" within the meaning of Article 1107 of the Civil Code, which is the consideration for that which it provides to the user, so that the contract concluded with the Google company is a contract for consideration and not a contract for free"26 .

Can accepting to be exposed to personalized advertising after having undergone data processing revealing one's centers of interest constitute a contractual service or not? To answer yes is to place the Internet user under the aegis of the Consumer Code. Answering no means protecting his or her privacy -including, perhaps, against his or her will. The approach of the EDPB and that of the TGI of Paris are clearly incompatible. A single French or European court that would be seized in turn in both areas would find it difficult to allow this inconsistency to persist.

The return to harmony can only take two paths.

The first is to consider that this business model is socially harmful. This is tantamount to taking a strong position, of a political nature, which is difficult to hide behind a seemingly purely technical interpretation of section 6 of the GDPR 27 . The EDPB does not entirely disguise this, as he states in the above-mentioned guidelines: "personal data should not be considered as a tradable commodity" 28 . The old debate on the real or personal nature of the individual's right to his or her data is not very well invoked here. Privacy is not a commodity, yet it is permissible to give access to it by contract in return for payment 29 . Radically forbidding any form of monetization by the individual of his data is a perfectly admissible social choice, but one that should have been left to the European legislator. It is all the same a question of preventing an individual, even supposing that he is well informed, aware of the consequences and voluntary, from making use of his freedom. The EDPB and the CNIL have, in fact, already enacted this prohibition: the combination of their doctrines presented in the two parts of this study is implacable. This business model is a suspended death, which only has a few more steps to go before it collapses -unless national or European judges adopt other analyses than the EDPB, which is perfectly conceivable. In such a scenario, "pseudo-free" services convert to simply contextual advertising or become paying, and the discordance with consumer law disappears by itself when the business model dies out 30 .

The second, more liberal way is to allow this model, but with a framework. To take it supposes clearly abandoning the lawful basis "consent" in favour of "necessity for the performance of the contract": if the data is the contractually defined price, one cannot escape payment because one has refrained from ticking a box when entering the service. Under constant law, the combined wrath of the GDPR (the principle of minimization, protection of privacy by default, retention periods, etc.) and consumer law (notably through the prohibition of unfair terms) could already curb a large proportion of abuses, and (very) gradually impose the most virtuous models of the kind. Normative intervention would naturally make it possible to go faster and further.

Above all, in both cases, an intervention by the European legislator would ensure a homogenous and simultaneous treatment of this entire economic sector. Otherwise, the rules will take years to be clarified before the CJEU, leaving professionals and users to deal with variable control priorities and the sometimes insufficient resources of the European data protection authorities.

Europe is now trying to establish a data protection model that can serve as a reference throughout the world. This noble ambition requires it to confront the most difficult issues in this area without trembling. The first of these is the legality of funding through targeted advertising.

27 The European Parliament has understood the political nature of this debate, having "invited the Commission to prohibit platforms from displaying micro-targeted advertising" on the occasion of a resolution of 18 June 2020 on competition policy ( §105). 28 Ibid, §54. 29 For a distinction between the "economic" and "moral" sides of personality rights, V. J. Antippas, "Propos dissidents sur les droits dits 'patrimoniaux' de la personnalité", RTD. com. 2012, p. 35. 30 The revenue per user is much lower for simply contextual advertising than for targeted advertising. It is therefore not possible to assume that the switch from the second model to the first will be sufficient to finance all current pseudo-free services.

The CSA is the Conseil Supérieur de l'Audivisuel, a regulatory body for television and radio. The CNIL is the Commission Nationale de l'Informatique et des Libertés, the French data protection authority.

See the 23rd study of the e-pub Observatory of the Syndicat des régies internet, on sri-france.org. Online advertising will reach 5.862 billion euros by 2019. Most online advertising is personalized.

Directive 2002/58/EC of the European Parliament and of the Council of 12 July 2002 concerning the processing of personal data and the protection of privacy in the electronic communications sector.

"RGPD: the CNIL investigates Criteo", nextinpact.com article of March

10, 2020.

It is also a model that meets online. It is for example that of the search engine Qwant.

EC, June 19, 2020, No. 430810.

EDPS, Guidelines 05/2020 on consent under Regulation 2016/679, 4 May 2020, §35.

Ibid, §37.

See the proposal for Regulation 2017/0003 of January 10, 2017 replacing the above-mentioned Directive 2002/58/EC.

Ibid, §39.

Example taken from §18 of the above-mentioned guidelines.

The First Level Privacy Policy devotes a specific section to the lawfulness grounds employed, and cites all those available in the GDMP (including the protection of vital interests or the public interest), en bloc and without linking them to any of the purposes previously presented. The "learn more" button provides more detail, but does not specifically provide the basis for advertising tracking treatments.

https://noyb.eu/en/open-letter, document dated May 24, 2020.

Note that such an approach makes it necessary to adhere to general terms and conditions and therefore the creation of a user account. It could be difficult to adopt it in certain sectors, such as pseudo-free online media displaying targeted advertising, which could hardly ask the Internet user who occasionally visits them to create dozens of different accounts to carry out his press review. A solution would then consist in creating identity federations grouping together numerous partner magazines.

https://www.cnil.fr/fr/le-contrat-dans-quels-cas-fonder-un-traitement-sur-cette-base-legale.

Guidelines 2/2019 on the processing of personal data under Article 6(1)(b) of the EDR in the context of the provision of online services to data subjects, version 2.0 of 8 October 2019.

TGI of Paris, judgment of February 12, 2019.


Guillaume Bernard
email: guillaume.bernard@univ-lr.fr

Cyrille Suire
email: cyrille.suire@univ-lr.fr

Cyril Faucher
email: cyril.faucher@univ-lr.fr

Antoine Doucet
email: antoine.doucet@univ-lr.fr

A Comprehensive Extraction of Relevant Real-World-Event Qualifiers for Semantic Search Engines

Keywords: Event, Information Retrieval, Linked and Open Data

In this paper, we present an efficient and accurate method to represent events from numerous public sources, such as Wikidata or more specific knowledge bases. We focus on events happening in the real world, such as festivals or assassinations. Our method merges knowledge from Wikidata and Wikipedia article summaries to gather entities involved in events, dates, types and labels. This event characterization procedure is extended by including vernacular languages. Our method is evaluated by a comparative experiment on two datasets that shows that events are represented more accurately and exhaustively with vernacular languages. This can help to extend the research that mainly exploits hub languages, or biggest language editions of Wikipedia. This method and the tool we release will for instance enhance event-centered semantic search engines, a context in which we already use it. An additional contribution of this paper is the public release of the source code of the tool, as well as the corresponding datasets.

Introduction

Analysing and characterising events in natural language processing has multiple applications. One of them is semantic search engines, used to browse large digital libraries or press articles [START_REF] Brank | Semantic Annotation of Documents[END_REF][START_REF] Cybulska | Historical Event Extraction from Text[END_REF][START_REF] Shaw | A Semantic Tool for Historical Events[END_REF]. To build an efficient event based query, the event representation and description are crucial. It is necessary to collect exhaustive information from data sources in order to be as precise as possible when qualifying events. This means being able to answer some simple questions, such as where the event happened, and when and who or what was involved [START_REF] Exner | Using semantic role labeling to extract events from wikipedia[END_REF][START_REF] Shaw | LODE: Linking Open Descriptions of Events[END_REF]. The answers to these questions are often named entities [START_REF] Yadav | A Survey on Recent Advances in Named Entity Recognition from Deep Learning models[END_REF], and considered as event qualifiers. To the best of our knowledge, the state of the art is missing a method to extract an as comprehensive as possible representation of real-world-events. Research projects often propose their own definition of events and adopt their own representation that fulfill their needs. Reference data sources are numerous and nothing exists to exploit them in a unified way.

The purpose of this paper is to overcome these limitations by taking advantage of past experiments and to provide an efficient representation of events by addressing two different issues. We first wish to know how to qualify, in any language, real-world-events based on publicly available resources. Subsequently, we propose an approach to obtain an almost comprehensive event qualification by exploiting vernacular languages, that is to say, the languages spoken where the events happened. We try to demonstrate the most spoken languages are not sufficient to accurately extract event qualifiers and that vernacular languages must be processed as well.

Related Work

In the recent years, a lot of publicly available data sources emerged to provide a universal access to multilingual information. A lot of them took benefit from Wikipedia, the largest knowledge base in the history of human kind. Through the years, many ontologies projects aimed at extracting the semantic knowledge of Wikipedia articles. Back in 2007, the DBPedia project [START_REF] Lehmann | DBpedia -A largescale, multilingual knowledge base extracted from Wikipedia[END_REF] was the first knowledge graph (KG) to gather data from Wikipedia articles, infoboxes and lists. Released a few years after, YAGO2 [START_REF] Hoffart | YAGO2: A spatially and temporally enhanced knowledge base from Wikipedia[END_REF] inherits the same characteristics. It is built from Wikipedia and supplemented with WordNet [START_REF] Miller | WordNet: A lexical database for English[END_REF] and GeoNames information. YAGO2 is linked to DBPedia entities. A year after, the Wikimedia Foundation unveiled Wikidata [START_REF] Vrandečić | Wikidata: A free collaborative knowledgebase[END_REF], a community maintained knowledge graph. This one is used as a reference graph to harmonize content across versions of Wikipedia. Recent projects investigate automatic writing of Wikipedia articles in low endowed Wikipedia linguistic versions [START_REF] Vrandečić | Architecture for a multilingual Wikipedia[END_REF]. The AbstractWikipedia project aims at solving an automated text generation task from semantic knowledge hosted on Wikidata. This is made possible as Wikidata is one of the highest qualitative multilingual knowledge repository, even if the amount and quality of its knowledge is not always connected to the number of worldwide native speakers [START_REF] Kaffee | A Glimpse into Babel: An Analysis of Multilinguality in Wikidata[END_REF]. A survey [START_REF] Färber | Linked data quality of DBpedia, Freebase, OpenCyc, Wikidata, and YAGO[END_REF] compared these knowledge graphs in terms of quality according to many metrics and gives criteria to find the most suitable graph for the needs of researchers.

None of these graphs is dedicated to events. EventKG [START_REF] Gottschalk | EventKG -the Hub of Event Knowledge on the Web -and Biographical Timeline Generation[END_REF] fills this gap. It is based on the Simple Event Model [START_REF] Van Hage | Design and use of the Simple Event Model (SEM)[END_REF] (SEM) ontology and intended to store events. SEM focuses on events elementary characteristics: types, dates, locations and participants. It defines a simple model to represent real-world-events. The role of entities associated to events is to point out who, what, where and when the event happened [START_REF] Xiang | A Survey of Event Extraction From Text[END_REF]. EventKG aggregates data from multiple sources and connects them in a graph to ensure easy communication through the semantic web. EventKG is good to represent major events such as happenings, festivals and disasters [START_REF] Mishra | EXPOS É: EXploring Past news fOr Seminal Events[END_REF].

Characterizing real world events has become an important research issue for a few years. While a lot of work has been made to detect and extract events from news articles [START_REF] Leban | Event registry: Learning about world events from news[END_REF][START_REF] Mele | Event mining and timeliness analysis from heterogeneous news streams[END_REF], another trend consists of extracting the semantic knowledge from data sources in order to connect real world events to news and press articles. This purpose is striven towards the usage for digital libraries by providing for instance semantic or event based search engines to explore historical news [START_REF] Shaw | A Semantic Tool for Historical Events[END_REF]. Wikipedia articles lead sections offer qualitative data and give an overall picture of events [START_REF] Mishra | EXPOS É: EXploring Past news fOr Seminal Events[END_REF]. They often contain elementary event information: dates, places, and participating entities. The latter have also been used to extract events from real time news, with a particular focus on people, organisations, places and dates when semantically enriching documents [START_REF] Fleur | Complex event extraction from real-time news streams[END_REF]. Semantic labeling thanks to Wikidata and Wikipedia [START_REF] Exner | Using semantic role labeling to extract events from wikipedia[END_REF] has been proven useful in semantic search engines [START_REF] Rudnik | Searching News Articles Using an Event Knowledge Graph Leveraged by Wikidata[END_REF] with annotated press articles.

We notice in the state of the art that exploiting Wikidata and Wikipedia entities and elementary event knowledge is useful, especially with specific use cases as exploring digital libraries. We propose to associate Wikidata and Wikipedia to exhaustively collect real-world-event qualifiers which are dates, places and participating entities. Ontologies such as EventKG do not provide comprehensive data, some entities may miss. We propose to collect knowledge where it is: from encyclopedias. On another hand, we know Wikimedia projects are multilingual. Some studies on event mentions tracking suggested to focus on hub languages [START_REF] Rupnik | News Across Languages -Cross-Lingual Document Similarity and Event Tracking[END_REF] (languages with a high number of articles and significant overlap in article coverage) to qualify events, we will propose another approach, based on vernacular languages.

Representing Events from Wikidata and Wikipedia

At first, we address the first question: we wish to qualify, in any language, realworld-events based on publicly available resources. We present the method we developed to collect event qualifiers from Wikidata and Wikipedia. We consider they both provide sufficient data to characterize real world events. We act in the continuation of the Automated Content Extraction program [START_REF] Doddington | The Automatic Content Extraction (ACE) program. Tasks, Data and Evaluation[END_REF] and existing event ontologies [START_REF] Van Hage | Design and use of the Simple Event Model (SEM)[END_REF][START_REF] Shaw | LODE: Linking Open Descriptions of Events[END_REF]. Our event qualifiers are used in the same context as ACE's event arguments. We benefit from Wikidata to extract elementary event information and use Wikipedia to aggregate all the entities involved in it.

The Extraction of Elementary Event Information

Wikidata supplies two different event identifiers, which point subtleties: some apply for breaking events, others for event with premisses. In this paper, we conform to the Wikidata Event Type (WET) [START_REF] Rudnik | Searching News Articles Using an Event Knowledge Graph Leveraged by Wikidata[END_REF] definition which accepts both. We refer to events as happenings in the real world which have spatio-temporal anchors and additional entities involved in it. From Wikidata entities, we only collect the event type and date, the locations, participants and labels. We consider these properties discriminate two events: it is unlikely that two distinct events have the same label, type, and occurred at the same place at the same time. As a community project, Wikidata is not an exhaustive data source. Table 1 shows that expecting a comprehensive event qualifiers collection is not possible when only capitalizing on Wikidata. For instance, almost all events miss the involved participant property.

Entities Involved in the Event

To go beyond, we propose to analyze Wikipedia lead sections in search of participating entities. A lead section (i.e., a summary) on Wikipedia contains a lot of important information, a synthesis of the article itself and reports the main topic [START_REF] Foundation | Wikipedia:Summary style[END_REF]. On Wikipedia, internal links connect articles to Wikidata. We use Wikipedia lead section internal links to detect entities involved in the event. We assume it is possible to add time, location and participant information, when they are absent from Wikidata. There are, in April 2021, 310 active language editions of Wikipedia. First, and in the interest of efficiency, we presume we can only focus on some languages with the most articles, hub languages (Table 2). In addition to the number of articles, we included the number of modified pages, of contributors (and active ones) and the Wikipedia article depth [START_REF] Foundation | Wikipedia article depth -Meta[END_REF]. The latter is a Wikipedia article quality indicator based on content edits. From the top-ten language list, Cebuano (2 nd ), Swedish (3 rd ) and Dutch (6 th ) are mainly bot written and therefore excluded. In case of conflict, the higher Wikipedia depth, the higher priority. We decided to arbitrarily select five languages. Following the criteria mentioned earlier, we kept English, German, French, Italian and Spanish, covering native languages of 30% of the world's population [START_REF] Eberhard | Ethnologue: Languages of the World[END_REF] and 25.14% of all Wikipedia articles (14.125 [START_REF] Foundation | List of Wikipedias[END_REF] over 56.615 million articles). We suppose this set of Wikipedia editions is sufficient to accurately gather event qualifiers. Nevertheless, this selection is biased and excludes most Asian and African languages with large speaker communities, as Mandarin and Hindi, whose Wikipedia versions are smaller. They respectively gather 1.120 billion and 128 thousands of articles [START_REF] Foundation | List of Wikipedias[END_REF].

From articles lead sections, we keep people, locations and organisations or geopolitical entities. The number of occurrences found for each entity in all lead sections is counted and represents the entity weight in relation to the event. This weight shows the relevance of the entity in relation to the event. We assume the entities found in multiple lead sections are important entities in the event description.

Let us take the example of the assassination of Rasputin event on Wikidata (identified by Q2882749 ). From Wikidata, we retain the date, locations, participants and entity labels in multiple languages. We ignore, for the time being, other properties associated with the event type, such as the target for a political assassination. Participants and locations are linked entities and identified by their URIs in the ontology. We supplement the event characterization with entities found in Wikipedia articles. There only exists Wikipedia articles written in French and Spanish for this event. After processing, we obtain, among others, these triples: (PER, Q312997 [Felix Yusupov, perpetrator], 3), (PER, Q43989 [Grigori Rasputin, target], 2), (PER, Q34266 [Stanislas Lazovert], 1). The weights, respectively 3, 2 and 1 show that Yusupov is a major player in the event, while Lavozert has a limited implication, even if he is a known plotter. Weights synthesize historical knowledge and give an unbiased information about entities implication in the event. The Lavozert entity is absent from Wikidata and was extracted from the French lead section.

Localizing Event Qualifiers

The event description consists of an association of absolute properties such as the date and labels with links to knowledge bases. The description is fundamentally multi-lingual. In most cases, Wikidata provides multiple names in different languages (i.e. with different spellings) for each entity. To continue with the previous example, in French the entity Q312997 on Wikidata is equally written Félix Youssoupoff or Felix Youssoupov.

This final step transforms abstract entities, identified by their Wikidata URIs to a language-dependent description. It takes all the alternative spellings for every entity involved in the event and saves them in the targeted language. Our approach makes it possible to get the event description in Italian even if, in this example, only French and Spanish Wikipedias were analyzed.

Conclusion

In this section, we proposed a method to characterize real-world events with qualifiers. Our method relies on the Wikidata ontology and Wikipedia to extract all the event participating entities. Our approach is multi-lingual: entities are identified by URIs but can be turned into any existing language. By selecting a subset of all the available Wikipedia languages, we assume we can efficiently collect most of the event entities. With this paper, we release the wikivents tool1 that implements the method described in this section. It is able to automatically extract the event representation and participating entities with a Wikidata identifier as input. The package can be customized in order to gather data from other resources, out of Wikimedia projects. More information about its API and tutorials are available in the project archive.

Enhancing the Event Representation with Vernacular Languages

Although we introduced in Section 3 our method to collect most of the event qualifiers, the arbitrary selection of some hub languages is biased. Widely spoken languages that are less present on Wikipedia are ignored. Numerous languages (i.e. Arabic, Mandarin, Hindi, Bengali, Portuguese or Russian) are concerned. We intend to discover whether the language influences the event representation when processing Wikipedia articles. To answer this second question, we propose to extend the list of processed languages with vernacular languages.

In this section, we carry out a comparative experiment to know how useful and pertinent it is to benefit from vernacular language when processing Wikipedia articles. First, we introduce the dataset we built, then the evaluation process and our results. We conclude with a short error analysis.

Datasets description

Selected events In order to compare the influence of language, we built two distinct datasets with the same events. As the nature of an event is ambiguous [START_REF] Sprugnoli | Event Detection and Classification for the Digital Humanities[END_REF], we qualify of indisputable an event that is considered as such for people with various backgrounds (history scholars [START_REF] Shaw | Events and Periods as Concepts for Organizing Historical Knowledge[END_REF], psychologists [START_REF] Minsky | A framework for representing knowledge[END_REF] or NLP reseachers [START_REF] Mele | A Multi-Source Collection of Event-Labeled News Documents[END_REF], for instance). This led us to restrict events to only three categories, taken as examples: assassinations and attacks, natural disasters and political happenings. On Wikidata, the first two concern breaking events while the last gathers events with premisses. We randomly selected two event types for each category.

-Assassination and attacks: political murder (Q1139665 ) and terrorist attack (Q2223653 ). -Natural disasters: earthquake (Q7944 ) and volcanic eruption (Q7692360 ).

-Political happenings: ceremony (Q2627975 ) and election (Q40231 ).

We express the same reserve about the exhaustiveness of Wikidata. The number of events reported is not uniform over the years but tends to grow since the beginning of the 21 st century. This increase must not be interpreted as an increase of events happening in the world but as a better data quality, especially with events now better anchored in time [START_REF] Rudnik | Searching News Articles Using an Event Knowledge Graph Leveraged by Wikidata[END_REF]. Therefore, we decided to only focus on events happening in the last fifty years, from January 1970 to December 2019. This ensures to exclude poorly documented events. For the sake of the experiment, it is necessary to process events which are described in at least one Wikipedia article. Thus, we exclude events without any articles. The number of found events is reported in Table 3.

The process of gathering participating entities described in Section 3 may be slow for some events. It produces numerous API calls and can take from a few seconds to a significant amount of time depending on the number of lead sections to be processed. Consequently, we randomly select a maximum of fifty events for every event type. Selected events all satisfy the previously mentioned requirements: they have a date property and at least one related article.

Vernacular languages

The difference between the two datasets resides in the number of languages processed to gather participating entities. The first one is called "base language" and built from the five languages mentioned above. We call the other one "all languages" for which vernacular languages are processed in addition to those from the base dataset. In case a Wikipedia project in this language is missing, we fall back to its standard dialect. For instance, American English is "en-us" which does not exist on Wikipedia, but is a dialect of "en". This process introduces another bias: temporality. French was an official language in Algeria before 1950. This information is missing from Wikidata which only provides current information. Moreover, the ontology sometimes provides the languages spoken in the countries, including the non official ones. We state the hypothesis that if an event occurs somewhere, the event will be better reported on Wikipedia in one of the languages spoken where it happened.

It may happen that the political entity changed through the years: the Easter Rising occurred in the United Kingdom of Great Britain and Ireland. This country does no longer exist, as the current United Kingdom exists since 1922. This is not an issue as Wikidata still informs about official or spoken languages. In any case, our dataset comprises events from 1970 to 2019, which limits this risk. Conclusion With this paper, we release the datasets we built. 2 3 They comprise 241 events divided up among six events types, in three categories. The first dataset is produced with selected languages, the other with selected and vernacular languages. Events were processed using the wikivents tool we described in Section 3. For each of them, we also provide the content of the lead section that was used to extract entities and we saved each event in all the processed languages to simplify any further analysis.

Experimental Metrics

The comparison between the two datasets is based on four metrics we consider as relevant to evaluate our hypothesis: processing vernacular languages on Wikipedia supplies additional and more precise information about participating entities. Metrics respectively are the number of participating entities found in the lead section of Wikipedia articles (M1), the number of tokens in the lead section, to the exclusion of tokens shorter than two characters (M2), the ratio between the two previous metrics (M3) and the number of alternative names found for each Wikidata entity, as mentioned in Section 3.3 (M4). Table 4 records the results for the assassination of John Fitzgerald Kennedy in 1963. As the assassination took place in the USA, an English speaking country, no additional language gets processed in addition to the five default ones. We notice the English version of Wikipedia provides more information about this event. More entities are found in the lead section, the lead section length is longer and we have more alternative names in English than in order languages.

In a second phase, languages are sorted in decreasing order, the higher value in Table 4, the first. Sorts for this events are shown in Table 5 and demonstrate the English version of Wikipedia is the most accurate to describe the event participating entities. English is in first place in terms of participating entities, tokens and number of alternative names found. The ratio is sometimes erroneous due to the different writing styles adopted by the multiple language Wikipedia communities. This may explain why Spanish is in first place for this metric.

Experiment Evaluation

Although when building the dataset in Section 4.1 we excluded events without any Wikipedia article, it may happen that some selected events do not exist on Wikipedia in any of the processed languages. They were not filtered out in the first step because they have at least an article, but written in a language which is not a hub or a vernacular language, which we were unaware of at the first step. It is also a necessity to exclude events for which we do not know either any official or spoken language. The two overlap in most cases. We report in Table 6 the number of events excluded by this final selection. When considering vernacular languages, the number of events to analyze increases. This is the first argument in favour of our hypothesis that events are better described in their vernacular languages.

In order to compare the description of events in the two datasets, we apply, for each event, the same computations as shown in Table 4 and Table 5. For each metric, we check whether one of the official languages spoken in the event place is in the best three languages to characterize it. Results shown in Table 7 show, for each metric, for how many events a vernacular language is in the top three of language that best represent the event. Results are significant with only the first language but selecting the best third languages tends to limit the issue described with the Kennedy's assassination example. By doing so, we state that the five languages we previously identified as core languages are not sufficient to accurately extract event qualifiers. This statement refutes the hypothesis we assumed in Section 3 that led us to only consider only five hub languages.

Error Analysis

For the majority of events that contradict the hypothesis, the main reason is a lack of resources in the vernacular languages: we miss Wikipedia articles so cannot extract any lead section. Missing articles are due to a small community of speakers and then results in a small Wikipedia edition or may be explained by cultural bias. The latter is mainly true for assassination and attacks events which are treated, or not, differently in the Wikipedia language editions. For few events, the vernacular language is in fourth position or even further away and is not the best at representing the given event.

We mainly processed Indo-European languages for which the tokenization procedure is quite uniform, then comparable. This is a noticeable limit of our analysis regarding some of our metrics.

Conclusion

In this paper, we described a method to gather event qualifiers coming from Wikidata and Wikipedia. We analysed and described its shortcomings and proposed to include vernacular languages. Our experiments demonstrate that this approach is greatly beneficial when describing events. We release an implementation of our approaches, and actually hereby make publicly available the source code, the analysis as well as the datasets, to be updated regularly. In the near future, we will add features to encode the event model into SEM [START_REF] Van Hage | Design and use of the Simple Event Model (SEM)[END_REF] or LODE [START_REF] Shaw | LODE: Linking Open Descriptions of Events[END_REF]. Researchers working on real-world events may already take advantage of our tool to fulfil their needs. It can be used to qualify events for their semantic search engines. We already use the library as the entry point of an event based search engine for a historical news digital library. It uses the event representation from the wikivents library in order to forge queries to retrieve documents associated to events [?].

Table 1 .

 1 The proportion of WETs with location, date and participants qualifiers. There is a total of 952.351 events.

	Named entities category [27]	Wikidata property	Number of events Percentage
	PER[SON]	Participant (P710 )	58,885	6.18%
	DATE	Time (P585, P580, P582 )	511,312	53.69%
	LOC[ATION]	Location (P7, P276 )	524.532	55.08%

Table 2 .

 2 Properties of the different language editions of Wikipedia. Sorted by decreasing number of articles (Data collected in Oct. 2020 ).

	Language	Articles	Modified pages	Contributors	Active Contributors Article Depth
		in millions			in thousands
	English	6.151	1200	386	32	1026.81
	German	2.475	241	50	5.5	93.6
	French	2.246	280	54	5.1	237.67
	Russian	1.657	173	40	3.4	135.94
	Italian	1.631	183	44	2.5	169.03
	Spanish	1.622	270	87	4.2	208.81
	Polish	1425	113	14	1.3	30.99

Table 3 .

 3 The number and ratio of events with at least one Wikipedia article in any language (even not a hub language), from 1970 to 2019.

	Category	Event type	Events	With an article	Ratio
	Assassinations	Political murder	44	24	54.55%
	and attacks	Terrorist attack	905	806	89.06%
	Natural	Earthquake	1,102	987	89.56%
	disasters	Volcanic eruption	23	18	78.26%
	Political	Ceremony	11,428	11,233	98.29%
	happenings	Election	29,236	24.488	82.10%

Table 4 .

 4 The four metrics for the selected languages about the assassination of JFK.

				Language
	Characteristic	Italian	Spanish	German	English	French
	M1: participating entities in the lead section	40	42	13	47	35
	M2: tokens found in the lead section	218	125	179	316	279
	M3: ratio between the two previous metrics	0.183	0.336	0.073	0.149	0.125
	M4: alternative names for each Wikidata entity	83	130	166	224	115

Table 5 .

 5 Ranked languages that best represent the assassination of JFK

	Characteristic	1st	2nd	3rd	4th	5th
	Participating entities	en	es	it	fr	de
	Tokens in the lead section	en	fr	it	de	es
	Ratio	es	it	en	fr	de
	Alternative names	en	de	es	fr	it

Table 6 .

 6 Number of events excluded because of a missing spoken language, or because of missing Wikipedia articles.

	Event type	Events	Without spoken language given	Without article Base All
				language	languages
	Political murder	24	0	1	0
	Terrorist attack	50	13	5	2
	Earthquake	50	11	17	11
	Volcanic eruption	17	1	3	2
	Ceremony	50	29	9	6
	Election	50	10	11	2

Table 7 .

 7 Comparison of how many events are better described by a vernacular language. The top-three languages that best represent the event are taken into account.

	Event type Dataset	Number of events	Events better described by a vernacular language M1: entities M2: tokens M3: ratio M4: alt. names
	Political murder	Base All	23	14 22	14 22	13 20	12 18
	Terrorist attacks	Base All	34	25 30	25 30	25 29	27 28
	Earthquake	Base All	25	13 24	13 24	12 23	11 20
	Volcanic eruption	Base All	14	12 13	12 13	12 13	12 13
	Ceremony	Base All	18	12 15	13 15	13 15	15 17
	Election	Base All	31	27 30	27 30	26 29	26 26

The package is a Python 3 library called wikivents on Pypi.org and available on the Software Heritage repository at https://archive.softwareheritage.org/swh: 1:dir:ef325a054ba6f7eb1121807da7b1c92b9ecde8f8

The dataset is hosted on Zenodo: https://doi.org/10.5281/zenodo.4733506.

Available on the Software Heritage repository at https://archive. softwareheritage.org/swh:1:dir:ef325a054ba6f7eb1121807da7b1c92b9ecde8f8

Acknowledgments

This work has been supported by the European Union's Horizon 2020 research and innovation program under grants 770299 (NewsEye).