Julien Niguez
email: julien.niguez@ens-cachan.fr

Saïd Amari
email: said.amari@ens-cachan.fr

Jean-Marc Faure
email: jean-marc.faure@ens-cachan.fr

Analysis of timed automata with guards in dioids algebra

Keywords: Timed automata with guards, discrete event systems, linear representation, dioids algebra

In this paper, we propose a new linear representation to model the behavior of Timed Automata with Guards (TAGs) using the formalism of dioids algebra. This linear modeling is used to define the parallel composition and properties of determinism for TAGs. The contribution is illustrated with an example of a jobshop to analyze the performances of this system.

I. INTRODUCTION

We are interested in this work to analyze the behavior of a class of timed Discrete Event Systems (DES). The timing aspect of DES can be handled through several modeling tools and analysis. In this paper, we will consider two complementary formalisms: approaches based on dioids algebra (in particular (max,+) and (min,+) algebra), and models based on timed automata.

On the first hand, (max,+) algebra (introduced in [START_REF] Baccelli | Synchronization and Linearity[END_REF]) is particularly effective for the study of quantitative measures of DES, such as asymptotic performances, earliest or latest behaviors. However, this formalism is not adapted to dealing with conflicts or choices that are very common in DES. It has been shown in [START_REF] Gaubert | Performance Evaluation of (max,+) Automata[END_REF] that automata with multiplicities in (max,+) algebra, also called (max,+) automata, can be used to handle this issue. This approach combines ideas of automata with results on (max,+) algebra, to manage both logical and timing aspects of DES. (max,+) automata are the subject of numerous publications during the last years on performance evaluation ( [START_REF] Gaubert | Performance Evaluation of (max,+) Automata[END_REF], [START_REF] Gaubert | Modeling and Analysis of Timed Petri nets using Heaps of Pieces[END_REF]) and control ( [START_REF] Komenda | Supervisory control of (max,+) automata: a behavioral approach[END_REF], [START_REF] Lahaye | Compositions of (max,+) automata[END_REF], [START_REF] Su | The synthesis of time optimal supervisors by using heaps-of-pieces[END_REF]). More recently, an approach presented in [START_REF] Boukra | New representations for (max,+) automata with applications to performance evaluation and control of discrete event systems[END_REF] proposes a new representation of (max,+) automata that takes advantages of both (max,+) and (min,+) algebras to determine the completion dates for the worst and the best schedules. Nevertheless, (max,+) automata only consider single weighted transitions (transitions associating a single duration to an event), which are not suited for industrial application. This comes from the fact that in practice, an event does not occur at the exact same time, and a task does not have an exact duration. It is more realistic to use intervals in order to describe these aspects.

On the other hand, timed automata are particularly efficient at handling intervals as durations of tasks and bounds of occurrences. There were first presented in [START_REF] Alur | Model-checking for realtime systems[END_REF] as timed graphs that use comparison between clocks values and transitions guards to rule the system evolutions. Based on works about timed transitions systems ( [START_REF] Henzinger | Timed transition systems[END_REF]), a first extension of these automata were proposed in [START_REF] Alur | A theory of timed automata[END_REF]. In order to prevent that the system evolve into deadlocks caused by time elapsing (no more transition is validated for the clocks values), timed automata completed with state invariants, called Timed Automata with Guards (TAGs), were introduced in [START_REF] Gaubert | Performance Evaluation of (max,+) Automata[END_REF]. Finally, timed automata used in UPPAAL software were presented in [START_REF] Pettersson | Modeling and Verification of Real-Time Systems Using Timed Automata : Theory and practice[END_REF]. UPPAAL automata are particularly powerful thanks to the high number of possibilities they offer (urgencies, synchronizations). However, to the best of our knowledge, none of these formalisms had been used as a base for a linear representation. Hence, it is not possible to use results of (max,+) algebra on these automata.

In order to fill the gap between timed automata and (max,+) based approaches, [START_REF] Komenda | Synchronous composition of interval weighted automata[END_REF] proposed an utilization of techniques based on semirings of interval and linear algebra to model a class of timed automata (Interval Weighted Automata) in a linear manner. However, the clocks used in these automata are reset at every transition. This restriction is not suitable for modeling systems in which durations are stated for sequences instead of events. This paper proposes a linear representation of TAGs by means of dioids, taking advantage of the modeling capacity of TAGs and the analysis possibilities of (max,+) automata at the same time.

The paper is organized as follows. In the following section, we recall the formalism of TAGs. A linear representation of TAGs is introduced in section III, and an application of this representation is presented in section IV. Finally, conclusions and possible future works are drawn up.

II. TIMED AUTOMATA WITH GUARDS

This section reminds the formalism of Timed Automata with Guards presented in [START_REF] Cassandras | Introduction to Discrete event Systems[END_REF] and provides some illustrative examples.

A. Definition of a TAG

Definition 1 [START_REF] Cassandras | Introduction to Discrete event Systems[END_REF]: A Timed Automaton with Guards, denoted by 𝐺𝐺, is a 7-tuple 𝐺𝐺 = (𝑄𝑄, Σ, 𝑄𝑄 0 , 𝑄𝑄 𝑚𝑚 , 𝑇𝑇𝑇𝑇𝑇𝑇, 𝐼𝐼𝐼𝐼𝐼𝐼, 𝐶𝐶) where:

• 𝑄𝑄 is the set of states;

• 𝑄𝑄 0 ⊂ 𝑄𝑄 is the set of initial states;

• 𝑄𝑄 𝑚𝑚 ⊂ 𝑄𝑄 is the set of final (or marked) states;

• Σ is a finite set of events;

• 𝐶𝐶 is the set of clocks, 𝑐𝑐 1 , … , 𝑐𝑐 𝑛𝑛 , with 𝑐𝑐 𝑖𝑖 (𝑡𝑡) ∈ ℝ + , 𝑡𝑡 ∈ ℝ + ;

• 𝑇𝑇𝑇𝑇𝑇𝑇 is the set of timed transitions of the automaton with 𝑇𝑇𝑇𝑇𝑇𝑇 ⊆ 𝑄𝑄 × 𝒞𝒞(𝐶𝐶) × Σ × 2 𝐶𝐶 × 𝑄𝑄 where 𝒞𝒞(𝐶𝐶) is the set of admissible constraints for the clocks in the set 𝐶𝐶;

• 𝐼𝐼𝐼𝐼𝐼𝐼 is the set of state invariants, 𝐼𝐼𝐼𝐼𝐼𝐼 ∶ 𝑄𝑄 → 𝒞𝒞(𝐶𝐶);

The set 𝑇𝑇𝑇𝑇𝑇𝑇 of timed transitions is to be interpreted as follows. If (𝑞𝑞 𝑖𝑖𝑛𝑛 , 𝑔𝑔𝑔𝑔𝑇𝑇𝑇𝑇𝑔𝑔, 𝑒𝑒, 𝑇𝑇𝑒𝑒𝑟𝑟𝑒𝑒𝑡𝑡, 𝑞𝑞 𝑜𝑜𝑜𝑜𝑜𝑜 ) ∈ 𝑇𝑇𝑇𝑇𝑇𝑇 then there is a transition from 𝑞𝑞 𝑖𝑖𝑛𝑛 to 𝑞𝑞 𝑜𝑜𝑜𝑜𝑜𝑜 with the complete label (𝑔𝑔𝑔𝑔𝑇𝑇𝑇𝑇, ; 𝑒𝑒, 𝑇𝑇𝑒𝑒𝑟𝑟𝑒𝑒𝑡𝑡) where 𝑔𝑔𝑔𝑔𝑇𝑇𝑇𝑇𝑔𝑔 ∈ 𝒞𝒞(𝐶𝐶), 𝑒𝑒 ∈ Σ, and 𝑇𝑇𝑒𝑒𝑟𝑟𝑒𝑒𝑡𝑡 ⊆ 𝐶𝐶.

The set of admissible clock constraints 𝒞𝒞(𝐶𝐶) is specified as follows:

• If 𝑰𝑰 ⊆ ℝ + , then all conditions of the form 𝑐𝑐 𝑖𝑖 (𝑡𝑡) ∈ 𝑰𝑰 are in 𝒞𝒞(𝐶𝐶).

• If 𝑔𝑔 1 and 𝑔𝑔 2 belong to 𝒞𝒞(𝐶𝐶), then 𝑔𝑔 1 ∧ 𝑔𝑔 2 belongs to 𝒞𝒞(𝐶𝐶)

Example 1: Fig. 1 depicts an example of an alarm modeled with a TAG, called 𝐺𝐺 1 , with a clock 𝑐𝑐 1 and a state invariant in state 2. This automaton will issue an event alarm if the duration between 2 consecutive occurrences of msg is smaller than 1 time unit. State 1 is considered as final. For the sake of simplicity, when the guard is [0; +∞[, i.e. when an event can occur at any time, the notationis used in place of [0; +∞[. • There is no need for the bounds of admissible clock constraints to be integer.

• All clocks are set to 0 when the system is initialized.

• Initial (final) states are indicated with incoming (outgoing) arrows. In Fig. 1, state 0 is initial and state 1 is final.

• The mechanism of 𝑇𝑇𝑒𝑒𝑟𝑟𝑒𝑒𝑡𝑡 allow modeling systems in which durations are stated for sequences of events. For example, the constraint "sequence 𝑇𝑇𝑎𝑎 must last at least 5 t.u. and at most 10 t.u." can be modeled as follow. This kind of constraint cannot be treated with automata used in [START_REF] Komenda | Synchronous composition of interval weighted automata[END_REF].

Properties of TAGs, such as determinism and model execution are detailed in [START_REF] Cassandras | Introduction to Discrete event Systems[END_REF]

B. Parallel Composition

Definition 2 [START_REF] Cassandras | Introduction to Discrete event Systems[END_REF]: Consider two timed automata with guards

𝐺𝐺 1 = �𝑄𝑄 1 , Σ 1 , 𝑄𝑄 0,1 , 𝑄𝑄 𝑚𝑚,1 , 𝑇𝑇𝑇𝑇𝑇𝑇 1 , 𝐼𝐼𝐼𝐼𝐼𝐼 1 , 𝐶𝐶 1 � and 𝐺𝐺 2 = �𝑄𝑄 2 , Σ 2 , 𝑄𝑄 0,2 , 𝑄𝑄 𝑚𝑚,2 , 𝑇𝑇𝑇𝑇𝑇𝑇 2 , 𝐼𝐼𝐼𝐼𝐼𝐼 2 , 𝐶𝐶 2 �.
The parallel composition of 𝐺𝐺 1 and 𝐺𝐺 2 is the automaton:

𝐺𝐺 1||2 = 𝒜𝒜𝒜𝒜�𝑄𝑄 1 × 𝑄𝑄 2 , Σ 1 ∪ Σ 2 , 𝑄𝑄 0,1 × 𝑄𝑄 0,2 , 𝑄𝑄 𝑚𝑚,1 × 𝑄𝑄 𝑚𝑚,2 , 𝑇𝑇𝑇𝑇𝑇𝑇 1||2 , 𝐼𝐼𝐼𝐼𝐼𝐼 1||2 , 𝐶𝐶 1 ∪ 𝐶𝐶 2 �
where 𝒜𝒜𝒜𝒜 corresponds to accessible transitions and states,

𝐼𝐼𝐼𝐼𝐼𝐼 1||2 ∶ 𝑄𝑄 1 × 𝑄𝑄 2 → 𝒞𝒞�𝐶𝐶 1||2 � = 𝒞𝒞(𝐶𝐶 1 ) ∧ 𝒞𝒞(𝐶𝐶 2 ) with 𝐼𝐼𝐼𝐼𝐼𝐼 1||2 (𝑞𝑞 1 , 𝑞𝑞 2 ) = 𝐼𝐼𝐼𝐼𝐼𝐼 1 (𝑞𝑞 1 ) ∧ 𝐼𝐼𝐼𝐼𝐼𝐼(𝑞𝑞 2 )
, and 𝑇𝑇𝑇𝑇𝑇𝑇 1||2 is defined as follows:

𝑇𝑇𝑇𝑇𝑇𝑇 1||2 ⊆ (𝑄𝑄 1 × 𝑄𝑄 2 ) × 𝒞𝒞(𝐶𝐶) 1||2 × (Σ 1 ∪ Σ 2 ) × 2 𝐶𝐶 1 ∪𝐶𝐶 2 × (𝑄𝑄 1 × 𝑄𝑄 2 ) • For all 𝑒𝑒 ∈ Σ 1 ∩ Σ 2 , if (𝑞𝑞 𝑖𝑖,𝑖𝑖𝑛𝑛 , 𝑔𝑔𝑔𝑔𝑇𝑇𝑇𝑇𝑔𝑔 𝑖𝑖 , 𝑒𝑒, 𝑇𝑇𝑒𝑒𝑟𝑟𝑒𝑒𝑡𝑡 𝑖𝑖 , 𝑞𝑞 𝑖𝑖,𝑜𝑜𝑜𝑜𝑜𝑜 ) ∈ 𝑇𝑇𝑇𝑇𝑇𝑇 𝑖𝑖 for 𝑖𝑖 = 1,2, then ��𝑞𝑞 1,𝑖𝑖𝑛𝑛 , 𝑞𝑞 2,𝑖𝑖𝑛𝑛 �, 𝑔𝑔𝑔𝑔𝑇𝑇𝑇𝑇𝑔𝑔 1 ∧ 𝑔𝑔𝑔𝑔𝑇𝑇𝑇𝑇𝑔𝑔 2 , 𝑒𝑒, 𝑇𝑇𝑒𝑒𝑟𝑟𝑒𝑒𝑡𝑡 1 ∪ 𝑇𝑇𝑒𝑒𝑟𝑟𝑒𝑒𝑡𝑡 2 , �𝑞𝑞 1,𝑜𝑜𝑜𝑜𝑜𝑜 , 𝑞𝑞 2,𝑜𝑜𝑜𝑜𝑜𝑜 �� ∈ 𝑇𝑇𝑇𝑇𝑇𝑇 1||2 ; • For all 𝑒𝑒 1 ∈ Σ 1 \Σ 2 and 𝑞𝑞 2 ∈ 𝑄𝑄 2 , if (𝑞𝑞 1,𝑖𝑖𝑛𝑛 , 𝑔𝑔𝑔𝑔𝑇𝑇𝑇𝑇𝑔𝑔 1 , 𝑒𝑒 1 , 𝑇𝑇𝑒𝑒𝑟𝑟𝑒𝑒𝑡𝑡 1 , 𝑞𝑞 1,𝑜𝑜𝑜𝑜𝑜𝑜 ) ∈ 𝑇𝑇𝑇𝑇𝑇𝑇 1 , then ��𝑞𝑞 1,𝑖𝑖𝑛𝑛 , 𝑞𝑞 2 �, 𝑔𝑔𝑔𝑔𝑇𝑇𝑇𝑇𝑔𝑔 1 , 𝑒𝑒 1 , 𝑇𝑇𝑒𝑒𝑟𝑟𝑒𝑒𝑡𝑡 1 , �𝑞𝑞 1,𝑜𝑜𝑜𝑜𝑜𝑜 , 𝑞𝑞 2 �� ∈ 𝑇𝑇𝑇𝑇𝑇𝑇 1||2 ; • For all 𝑒𝑒 2 ∈ Σ 2 \Σ 1 and 𝑞𝑞 1 ∈ 𝑄𝑄 1 , if (𝑞𝑞 2,𝑖𝑖𝑛𝑛 , 𝑔𝑔𝑔𝑔𝑇𝑇𝑇𝑇𝑔𝑔 2 , 𝑒𝑒 2 , 𝑇𝑇𝑒𝑒𝑟𝑟𝑒𝑒𝑡𝑡 2 , 𝑞𝑞 2,𝑜𝑜𝑜𝑜𝑜𝑜 ) ∈ 𝑇𝑇𝑇𝑇𝑇𝑇 2 , then ��𝑞𝑞 1 , 𝑞𝑞 2,𝑖𝑖𝑛𝑛 �, 𝑔𝑔𝑔𝑔𝑇𝑇𝑇𝑇𝑔𝑔 2 , 𝑒𝑒 2 , 𝑇𝑇𝑒𝑒𝑟𝑟𝑒𝑒𝑡𝑡 2 , �𝑞𝑞 1 , 𝑞𝑞 2,𝑜𝑜𝑜𝑜𝑜𝑜 �� ∈ 𝑇𝑇𝑇𝑇𝑇𝑇 1||2 .
Example 2: Recall the automaton 𝐺𝐺 1 of Fig. 1. Suppose that a second TAG, called 𝐺𝐺 2 and shown in Fig. 2.1, was built in order to issue an event 𝑇𝑇𝑎𝑎𝑇𝑇𝑇𝑇𝑎𝑎5 if two occurrences of events 𝑎𝑎𝑟𝑟𝑔𝑔 are more than 5 time units apart. The parallel composition of 𝐺𝐺 1 and 𝐺𝐺 2 , called G 1||2 , is shown in Fig.

C. Case of single-clock systems

In most cases, for small-size systems, only one clock is sufficient. Concerning larger systems, they can be handled by using decentralized approaches, in which each sub-system is modeled with a single clock. In that specific case of single clock systems, the parallel composition could be simplified since the conjunction of two guards would become equivalent to the intersection of the intervals. If the result of that intersection is the empty set, then the guard can never be validated, and the associated transition can be deleted. This section presents our proposition for a linear representation of TAGs using dioids. In this section, we will assume that for all 𝑞𝑞 ∈ 𝑄𝑄, 𝐼𝐼𝐼𝐼𝐼𝐼(𝑞𝑞) = 𝑡𝑡𝑇𝑇𝑔𝑔𝑒𝑒, that is, the linear notation proposed below does not consider the set of state invariants 𝐼𝐼𝐼𝐼𝐼𝐼. To maintain the coherence of the examples, state invariants from Fig. 1, 2 and 3 will be held by outgoing transitions of these states e.g. the state invariant 𝑐𝑐 < 1 of the state (1,D) in Fig. 3 will become a guard in the transition from state (1,D) to state (1,F): ([0; 1[ ; 𝑇𝑇𝑎𝑎𝑇𝑇𝑇𝑇𝑎𝑎5 ; -). Moreover, we will only consider single-clock system in this section.

A. Definition

Consider a dioid (𝔻𝔻,⊕,⊗, 𝜖𝜖, 𝑒𝑒), such that 𝜖𝜖 (resp. 𝑒𝑒) is the neutral element for ⊕ (resp. ⊗).

The set ℝ ∪ {-∞} with the maximum playing the role of addition and conventional addition playing the role of multiplication is a dioid, denoted ℝ 𝑀𝑀𝑀𝑀𝑀𝑀 and usually called (max,+) algebra, with 𝑒𝑒 = 0 and 𝜖𝜖 = -∞. Dioid ℝ 𝑀𝑀𝑀𝑀𝑀𝑀 completed with ⊤ = +∞ is denoted ℝ � 𝑀𝑀𝑀𝑀𝑀𝑀 .

Similarly, the (min,+) algebra is the set ℝ ∪ {+∞} with the minimum as addition, the conventional addition as multiplication, 𝑒𝑒 = 0 and 𝜖𝜖 = +∞. Definition 3: A TAG can be defined as a 7-tuple �𝑄𝑄, Σ, 𝑇𝑇𝑇𝑇𝑇𝑇, 𝛼𝛼, 𝛽𝛽, 𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 , 𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 �, called linear representation, where:

• 𝑄𝑄 is the set of states;

• Σ is a finite set of events;

• 𝑇𝑇𝑇𝑇𝑇𝑇 is the set of timed transitions of the automaton; Namely, for 𝔻𝔻 = ℝ � 𝑀𝑀𝑀𝑀𝑀𝑀 ., a TAG can be represented with two (max,+) automata as presented in [START_REF] Cassandras | Introduction to Discrete event Systems[END_REF]. These automata correspond to the extremal behavior of the system modeled: 𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (resp. 𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 ) describes the upper bound (resp. lower bound) of the system. For the sake of simplicity, we will use the notation ⊤ = +∞ in the examples presented below. Similarly to generalized daters introduced in [START_REF] Gaubert | Performance Evaluation of (max,+) Automata[END_REF] in order to describe the evolution and the dynamic of (max,+) automata, we propose a definition for generalized bounds for a TAG.

• 𝛼𝛼 ∈ ℝ � 𝑀𝑀𝑀𝑀𝑀𝑀 1×|𝑄𝑄| , if 𝑞𝑞 ∈ 𝑄𝑄 0 then 𝛼𝛼 𝑞𝑞 = 𝑒𝑒 else 𝛼𝛼 𝑞𝑞 = 𝜖𝜖; • 𝛽𝛽 ∈ ℝ � 𝑀𝑀𝑀𝑀𝑀𝑀 |𝑄𝑄|×1 , if 𝑞𝑞 ∈ 𝑄𝑄 𝑚𝑚 then 𝛽𝛽 𝑞𝑞 = 𝑒𝑒 else 𝛽𝛽 𝑞𝑞 = 𝜖𝜖; • 𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 : Σ → 𝔻𝔻 |𝑄𝑄|×|𝑄𝑄| , [𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑒𝑒 𝑣𝑣 )] 𝑞𝑞 𝑖𝑖𝑖𝑖 𝑞𝑞 𝑜𝑜𝑜𝑜𝑜𝑜 ≜ � sup(𝑔𝑔𝑔𝑔𝑇𝑇𝑇𝑇𝑔𝑔) 𝑖𝑖𝑖𝑖 (𝑞𝑞 𝑖𝑖𝑛𝑛 ,
𝐼𝐼𝐼𝐼 ℝ � 𝑀𝑀𝑀𝑀𝑀𝑀 , � 𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝜀𝜀) = 𝛼𝛼 𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑤𝑤𝑒𝑒 𝑣𝑣 ) = 𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑤𝑤) ⊗ 𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑒𝑒 𝑣𝑣 ) 𝐼𝐼𝐼𝐼ℝ � 𝑀𝑀𝑀𝑀𝑀𝑀 , � 𝑥𝑥 𝐼𝐼𝑛𝑛𝐼𝐼 (𝜀𝜀) = 𝛼𝛼 𝑥𝑥 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑤𝑤𝑒𝑒 𝑣𝑣 ) = 𝑥𝑥 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑤𝑤) ⊗ 𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑒𝑒 𝑣𝑣 )
where 𝜀𝜀 is the empty word and 𝑒𝑒 𝑣𝑣 ∈ Σ.

�𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑤𝑤)�

𝑞𝑞 can be interpreted as the maximal date at which the state 𝑞𝑞 can be reached following a sequence 𝑤𝑤 from an initial state. By convention, �𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑤𝑤)� 𝑞𝑞 = 𝜖𝜖 if the state 𝑞𝑞 cannot be reached following the sequence 𝑤𝑤 from an initial state. An application of generalized bounds is exposed in section IV.

B. Determinism

The determinism of a TAG can be expressed with its linear representation. However, we can find two definitions of the determinism:

• Time-determinism [START_REF] Cassandras | Introduction to Discrete event Systems[END_REF]: an automaton is deterministic if for all events at all states, the guards of the associated transitions are mutually exclusive.

• Event-determinism [START_REF] Lahaye | Compositions of (max,+) automata[END_REF]: an automaton is deterministic if there is a single 𝑖𝑖 such that 𝛼𝛼 𝑖𝑖 ≠ 𝜖𝜖 and for all 𝑒𝑒 𝑣𝑣 ∈ Σ, there exists at most one 𝑗𝑗 such that 𝜇𝜇(𝑇𝑇) 𝑖𝑖𝑖𝑖 ≠ 𝜖𝜖.

It is clear that the second definition is stronger than the first one. For the example in Fig 3 . From the state (1B), there is more than one outgoing transition labelled with the event 𝑎𝑎𝑟𝑟𝑔𝑔, which means that the automaton is not eventdeterministic. However, the guards of these transitions do not overlap, hence the automaton is time-deterministic.

Property 1: if an automaton is event-deterministic, then for a sequence 𝑤𝑤, there exists at most one 𝑘𝑘 such that �𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑤𝑤)� 𝑘𝑘 ≠ 𝜖𝜖 and �𝑥𝑥 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑤𝑤)� 𝑘𝑘 ≠ 𝜖𝜖.

Proof: Consider a TAG with its linear representation 𝐺𝐺 = �𝑄𝑄, Σ, 𝑇𝑇𝑇𝑇𝑇𝑇, 𝛼𝛼, 𝛽𝛽, 𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 , 𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 �. We suppose that 𝐺𝐺 is eventdeterministic.

• 𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝜖𝜖) = 𝛼𝛼 and 𝑥𝑥 𝐼𝐼𝑛𝑛𝐼𝐼 (𝜖𝜖) = 𝛼𝛼. Since 𝐺𝐺 is eventdeterministic, there is a single 𝑖𝑖 such that 𝛼𝛼 𝑖𝑖 ≠ 𝜖𝜖. Hence the property is true for 𝑤𝑤 = 𝜖𝜖

• Suppose that the property is true for a sequence 𝑤𝑤 (the calculation will only be shown for 𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 since it works in a similar way for 𝑥𝑥 𝐼𝐼𝑛𝑛𝐼𝐼

𝛼𝛼 1||2 ∈ ℝ � 𝑀𝑀𝑀𝑀𝑀𝑀 1×|𝑄𝑄 1 ×𝑄𝑄 2 | , �𝛼𝛼 1||2 � 𝑞𝑞 𝑖𝑖 ×𝑞𝑞 𝑗𝑗 = � [𝛼𝛼 1 ] 𝑞𝑞 𝑖𝑖 ⊕ [𝛼𝛼 2 ] 𝑞𝑞 𝑗𝑗 𝑖𝑖𝑖𝑖 [𝛼𝛼 1 ] 𝑞𝑞 𝑖𝑖 ≠ 𝜖𝜖 𝑇𝑇𝐼𝐼𝑔𝑔 [𝛼𝛼 2 ] 𝑖𝑖 ≠ 𝜖𝜖 𝜖𝜖 𝑒𝑒𝑎𝑎𝑟𝑟𝑒𝑒 𝛽𝛽 1||2 ∈ ℝ � 𝑀𝑀𝑀𝑀𝑀𝑀 |𝑄𝑄 1 ×𝑄𝑄 2 |×1 , �𝛽𝛽 1||2 � 𝑞𝑞 𝑖𝑖 ×𝑞𝑞 𝑗𝑗 = � [𝛽𝛽 1 ] 𝑞𝑞 𝑖𝑖 ⊕ [𝛽𝛽 2 ] 𝑞𝑞 𝑗𝑗 𝑖𝑖𝑖𝑖 [𝛽𝛽 1 ] 𝑞𝑞 𝑖𝑖 ≠ 𝜖𝜖 𝑇𝑇𝐼𝐼𝑔𝑔 [𝛽𝛽 2 ] 𝑖𝑖 ≠ 𝜖𝜖 𝜖𝜖 𝑒𝑒𝑎𝑎𝑟𝑟𝑒𝑒 • 𝜇𝜇 1||2,𝑆𝑆𝑜𝑜𝑝𝑝 = Σ → 𝔻𝔻 |𝑄𝑄 1 ×𝑄𝑄 2 |×|𝑄𝑄 1 ×𝑄𝑄 2 | • 𝜇𝜇 1||2,𝐼𝐼𝑛𝑛𝐼𝐼 = Σ → 𝔻𝔻 |𝑄𝑄 1 ×𝑄𝑄 2 |×|𝑄𝑄 1 ×𝑄𝑄 2 |
Coefficients matrices of 𝜇𝜇 1||2,𝑆𝑆𝑜𝑜𝑝𝑝 and 𝜇𝜇 1||2,𝐼𝐼𝑛𝑛𝐼𝐼 can be calculated as follows: In other words, if the k th column of 𝜇𝜇 1||2,𝑆𝑆𝑜𝑜𝑝𝑝 (𝑒𝑒 𝑣𝑣 ) and 𝜇𝜇 1||2,𝐼𝐼𝑛𝑛𝐼𝐼 (𝑒𝑒 𝑣𝑣 ) are empty for all 𝑒𝑒 𝑣𝑣 ∈ Σ 1||2 , then there will be no transition entering the corresponding state.

• For all 𝑒𝑒 𝑣𝑣 ∈ Σ 1 ∩ Σ 2 , 𝐼𝐼𝐼𝐼 ℝ � 𝑀𝑀𝑖𝑖𝑛𝑛 , �𝜇𝜇 1||2,𝑆𝑆𝑜𝑜𝑝𝑝 (𝑒𝑒 𝑣𝑣 )� �𝑞𝑞 1,𝑖𝑖𝑖𝑖 × 𝑞𝑞 2,𝑖𝑖𝑖𝑖 �,�𝑞𝑞 1,𝑜𝑜𝑜𝑜𝑜𝑜 × 𝑞𝑞 2,𝑜𝑜𝑜𝑜𝑜𝑜 � = � ⨁ 𝑖𝑖=1,
�𝜇𝜇 1||2,𝑆𝑆𝑜𝑜𝑝𝑝 (𝑒𝑒 1 )� �𝑞𝑞 1,𝑖𝑖𝑖𝑖 × 𝑞𝑞 2 �,�𝑞𝑞 1,𝑜𝑜𝑜𝑜𝑜𝑜 × 𝑞𝑞 2 � = �𝜇𝜇 1,𝑆𝑆𝑜𝑜𝑝𝑝 (𝑒𝑒 1 )� 𝑞𝑞 1,𝑖𝑖𝑖𝑖 ,𝑞𝑞 1,𝑜𝑜𝑜𝑜𝑜𝑜 �𝜇𝜇 1||2,𝐼𝐼𝑛𝑛𝐼𝐼 (𝑒𝑒 1 )� �𝑞𝑞 1,𝑖𝑖𝑖𝑖 × 𝑞𝑞 2 �,�𝑞𝑞 1,𝑜𝑜𝑜𝑜𝑜𝑜 ×𝑞𝑞 2 � = �𝜇𝜇 1,𝐼𝐼𝑛𝑛𝐼𝐼 (𝑒𝑒 1 )� 𝑞𝑞 1,𝑖𝑖𝑖𝑖 ,𝑞𝑞 1,𝑜𝑜𝑜𝑜𝑜𝑜 • For all 𝑒𝑒 2 ∈ Σ 2 \Σ 1 and 𝑞𝑞 1 ∈ 𝑄𝑄 1 , �𝜇𝜇 1||2,𝑆𝑆𝑜𝑜𝑝𝑝 (𝑒𝑒 2 )� �𝑞𝑞 1 × 𝑞𝑞 2,𝑖𝑖𝑖𝑖 �,�𝑞𝑞 1 × 𝑞𝑞 2,𝑜𝑜𝑜𝑜𝑜𝑜 � = �𝜇𝜇 𝑖𝑖,𝑆𝑆𝑜𝑜𝑝𝑝 (𝑒𝑒 2 )� 𝑞𝑞 2,𝑖𝑖𝑖𝑖 ,𝑞𝑞 2,𝑜𝑜𝑜𝑜𝑜𝑜 �𝜇𝜇 1||2,𝐼𝐼𝑛𝑛𝐼𝐼 (𝑒𝑒 2 )� �𝑞𝑞 1 × 𝑞𝑞 2,𝑖𝑖𝑖𝑖 �,�𝑞𝑞 1 ×𝑞𝑞 2,𝑜𝑜𝑜𝑜𝑜𝑜 � = �𝜇𝜇 𝑖𝑖,𝐼𝐼𝑛𝑛𝐼𝐼 (𝑒𝑒 2 )� 𝑞𝑞 2,𝑖𝑖𝑖𝑖 ,𝑞𝑞 2,𝑜𝑜𝑜𝑜𝑜𝑜
Hence, the notations 𝜇𝜇̇1 ||2,𝑆𝑆𝑜𝑜𝑝𝑝 and 𝜇𝜇̇1 ||2,𝐼𝐼𝑛𝑛𝐼𝐼 can be introduced, corresponding to 𝜇𝜇 1||2,𝐼𝐼𝑛𝑛𝐼𝐼 and 𝜇𝜇 1||2,𝑆𝑆𝑜𝑜𝑝𝑝 in which every column of 𝜖𝜖 is deleted.

Example 5: According to the definition 5, the dimension of matrices of 𝜇𝜇 1||2,𝐼𝐼𝑛𝑛𝐼𝐼 and 𝜇𝜇 1||2,𝑆𝑆𝑜𝑜𝑝𝑝 for the automaton resulting of the parallel composition of 𝐺𝐺 1 and 𝐺𝐺 2 is too important to be detailed in this paper (|𝑄𝑄 1 × 𝑄𝑄 2 | = 16). However, it is possible to determine matrices 𝜇𝜇̇1 ||2,𝑆𝑆𝑜𝑜𝑝𝑝 and 𝜇𝜇̇1 ||2,𝐼𝐼𝑛𝑛𝐼𝐼 , that are detailed in the following order:

𝐴𝐴 = 𝜇𝜇̇1 ||2,𝑖𝑖𝑛𝑛𝐼𝐼 (𝑎𝑎𝑟𝑟𝑔𝑔), 𝐵𝐵 = 𝜇𝜇̇1 ||2,𝑆𝑆𝑜𝑜𝑝𝑝 (𝑎𝑎𝑟𝑟𝑔𝑔), 𝐶𝐶 = 𝜇𝜇̇1 ||2,𝐼𝐼𝑛𝑛𝐼𝐼 (𝑇𝑇𝑎𝑎𝑇𝑇𝑇𝑇𝑎𝑎), 𝐷𝐷 = 𝜇𝜇̇1 ||2,𝑆𝑆𝑜𝑜𝑝𝑝 (𝑇𝑇𝑎𝑎𝑇𝑇𝑇𝑇𝑎𝑎), 𝐸𝐸 = 𝜇𝜇̇1 ||2,𝐼𝐼𝑛𝑛𝐼𝐼 (𝑇𝑇𝑎𝑎𝑇𝑇𝑇𝑇𝑎𝑎5), 𝐹𝐹 = 𝜇𝜇̇1 ||2,𝑆𝑆𝑜𝑜𝑝𝑝 (𝑇𝑇𝑎𝑎𝑇𝑇𝑇𝑇𝑎𝑎5). 𝐴𝐴 = ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 𝜖𝜖 0 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 1 0 𝜖𝜖 5 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 ⎦ ⎥ ⎥ ⎥ ⎥ ⎤ ; 𝐵𝐵 = ⎣ ⎢ ⎢ ⎢ ⎢ ⎡ 𝜖𝜖 ⊤ 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 5

;

It can be noted that defined as such, 𝜇𝜇̇𝑆𝑆 𝑜𝑜𝑝𝑝 and 𝜇𝜇̇𝐼𝐼 𝑛𝑛𝐼𝐼 may contain cycles of states that cannot be reached from the initial states. However, the corresponding coefficients will not impact the representation aside from the size of matrices.

IV. APPLICATION TO A JOBSHOP

We consider here a jobshop processing with two jobs 𝒥𝒥 1 and 𝒥𝒥 2 to illustrate our contribution (this example come from [START_REF] Gaubert | Modeling and Analysis of Timed Petri nets using Heaps of Pieces[END_REF] and [START_REF] Lahaye | Compositions of (max,+) automata[END_REF]). This jobshop will be studied using TAGs and their linear representations. However, for the sake of simplicity, the system is presented with a Petri net model in Fig. 4.

Job 𝒥𝒥 1 (resp. 𝒥𝒥 2 ) consists of three tasks 𝑇𝑇, 𝑎𝑎 and 𝑐𝑐 (𝑔𝑔, 𝑒𝑒 and 𝑖𝑖). Processing times are exposed in Fig. 4. We will consider that a task does not have an exact duration, hence, we will associate an interval to every transition of the system, that corresponds to the processing times ±10% (e.g. a processing time of 2 time unites will be represented as the interval [1.8; 2.2]). Two resources ℛ 1 and ℛ 2 are shared by tasks, such as ℛ 1 can be used by 𝑇𝑇, 𝑎𝑎, 𝑔𝑔 and 𝑒𝑒, and ℛ 2 by 𝑎𝑎, 𝑐𝑐, 𝑒𝑒 and 𝑖𝑖.

Figure 4 -Jobshop represented as a Petri net

The transformation of timed Petri nets into TAG is not addressed in this paper. For our application, the TAG model of Fig. 5 is inferred from the (max,+) automaton presented in [START_REF] Lahaye | Compositions of (max,+) automata[END_REF]. Also, it is simple to see that the system is eventdeterministic in Fig 5.

A. Analysis for one job

It is possible to determine generalized bounds (def. 4) for processing times of jobs 𝒥𝒥 1 and 𝒥𝒥 2 :

• Processing time of one job The end of the job 𝒥𝒥 2 corresponds to the state 9. For this reason, the processing time of one job 𝒥𝒥 2 is from 4.5 to 5.5 time units.

It can be noted that proposition 1 is respected for both sequences: since the TAG is event-deterministic, generalized bounds of sequences 𝑇𝑇𝑎𝑎𝑐𝑐 and 𝑒𝑒𝑔𝑔𝑖𝑖 only have one coefficient different from 𝜖𝜖.

B. Analysis for a set of jobs

Another analysis can be done on the completion date for a given number of jobs, whatever the kind of job. Jobs 𝒥𝒥 1 and 𝒥𝒥 2 both consist of three tasks, which may be executed in parallel (e.g. tasks 𝑇𝑇 and 𝑐𝑐 do not use the same resource, hence, the (n+1) th job 𝒥𝒥 1 can start before the end of the n th job 𝒥𝒥 1 ). For this reason, jobs may overlap and the duration of a succession of n job could be different from n times the duration of a single job.

Since a TAG of the system can be interpreted as two (max,+) automata, it is possible to adapt the method presented in [START_REF] Boukra | New representations for (max,+) automata with applications to performance evaluation and control of discrete event systems[END_REF] in order to determine bounds of completion dates for the worst and the best cases.

For the completion date of 10 jobs:

• In the worst case, we found that the interval of the completion date is [37.8; 46.2] time units that corresponds to a succession of 10 jobs 𝒥𝒥 1 .

Representation of TAG in Fig. 5: • In the best case, we found that the interval of the completion date is [36.9; 45.1] time units that corresponds to an alternation of 𝒥𝒥 2 𝒥𝒥 1 .

𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑇𝑇) = ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎡ 𝜖𝜖 2
We managed here to get bounds that estimate the possible durations of sequences in the best and the worst cases, where [START_REF] Boukra | New representations for (max,+) automata with applications to performance evaluation and control of discrete event systems[END_REF] only provides a single value for the same durations. This is a clear improvement in the way that in a real application, the completion date of a succession of tasks cannot be exactly evaluated since the duration of a single task may vary depending to the environment of the system.

V. CONCLUSIONS

The paper has presented a new formal modeling of Timed Automata with Guards (TAGs) by dioids algebra. A linear representation of the behavior of TAGs is given. The definitions of a parallel composition and properties concerning the determinism of TAGs are proposed. This linear representation of TAGs is applied on a jobshop system to evaluate the temporal performances. In future works, an extension of the formalism to multiple-clocks systems could be considered. It would be also interesting to use this linear modeling of TAGs for diagnosis and fault-tolerant control of discrete event systems.

Figure 1 :

 1 Figure 1: A Timed Automaton with Guards 𝐺𝐺 1 Remark 1:

2 . 2 .

 22 The set of transitions has been built exhaustively according to definition 2. Since clocks 𝑐𝑐 1 and 𝑐𝑐 2 reset when entering the state (1,B) as shown in the transition (-; 𝑎𝑎𝑟𝑟𝑔𝑔; 𝑐𝑐 1 , 𝑐𝑐 2 ), conditions 𝑐𝑐 1 ∈ ]0; 1[ and 𝑐𝑐 2 ∈ ]5; +∞[ of the transition (]0; 1[ 1 ∧ ]5; +∞[ 2 ; 𝑎𝑎𝑟𝑟𝑔𝑔 ; 𝑐𝑐 1 , 𝑐𝑐 2 ) cannot be satisfied. Hence, the state (2,D) and its successors are not reachable.

Figure 2 -

 2 Figure 2 -1. A Timed Automaton with Guards 𝐺𝐺 2 (top) -2. Parallel composition 𝐺𝐺 1||2 of 𝐺𝐺 1 and 𝐺𝐺 2 (bottom)

Example 3 :

 3 Consider that the automata 𝐺𝐺 1 and 𝐺𝐺 2 from examples 1 and 2 share the same clock 𝑐𝑐. The automaton 𝐺𝐺 1||2 ′ shown in Fig. 3 is the result of the parallel composition.

Figure 3 -

 3 Figure 3 -TAG 𝐺𝐺 1||2 ′ for a single-clock case III. LINEAR REPRESENTATION OF TIMED AUTOMATA WITH GUARDS USING DIOIDS ALGEBRA

  𝑔𝑔𝑔𝑔𝑇𝑇𝑇𝑇𝑔𝑔, 𝑒𝑒 𝑣𝑣 , 𝑇𝑇𝑒𝑒𝑟𝑟𝑒𝑒𝑡𝑡, 𝑞𝑞 𝑜𝑜𝑜𝑜𝑜𝑜 ) ∈ 𝑇𝑇𝑇𝑇𝑇𝑇 𝜖𝜖 𝑒𝑒𝑎𝑎𝑟𝑟𝑒𝑒 • 𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 : Σ → 𝔻𝔻 |𝑄𝑄|×|𝑄𝑄| , 𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑒𝑒 𝑣𝑣 ) 𝑞𝑞 𝑖𝑖𝑖𝑖 𝑞𝑞 𝑜𝑜𝑜𝑜𝑜𝑜 ≜ � inf(𝑔𝑔𝑔𝑔𝑇𝑇𝑇𝑇𝑔𝑔) 𝑖𝑖𝑖𝑖 (𝑞𝑞 𝑖𝑖𝑛𝑛 , 𝑔𝑔𝑔𝑔𝑇𝑇𝑇𝑇𝑔𝑔, 𝑒𝑒 𝑣𝑣 , 𝑇𝑇𝑒𝑒𝑟𝑟𝑒𝑒𝑡𝑡, 𝑞𝑞 𝑜𝑜𝑜𝑜𝑜𝑜 ) ∈ 𝑇𝑇𝑇𝑇𝑇𝑇 𝜖𝜖 𝑒𝑒𝑎𝑎𝑟𝑟𝑒𝑒 In other words, coefficients �𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑒𝑒 𝑣𝑣 )� 𝑖𝑖𝑖𝑖 and �𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑒𝑒 𝑣𝑣 )� 𝑖𝑖𝑖𝑖 correspond respectively to the upper and lower bounds of the intervals in guard for every (𝑞𝑞 𝑖𝑖𝑛𝑛 , 𝑔𝑔𝑔𝑔𝑇𝑇𝑇𝑇𝑔𝑔, 𝑒𝑒 𝑣𝑣 , 𝑇𝑇𝑒𝑒𝑟𝑟𝑒𝑒𝑡𝑡, 𝑞𝑞 𝑜𝑜𝑜𝑜𝑜𝑜 ) ∈ 𝑇𝑇𝑇𝑇𝑇𝑇.

Remark 2 :

 2 it is possible to take into account initial and final delays through vectors 𝛼𝛼 and 𝛽𝛽. 𝛼𝛼 𝑞𝑞 𝑖𝑖 = 𝐼𝐼 (resp. 𝛽𝛽 𝑞𝑞 𝑖𝑖 = 𝐼𝐼) means than the state 𝑖𝑖 is initial (final) with an initial (final) delay of n time unit. By convention, if a state 𝑖𝑖 is not initial (final), 𝛼𝛼 𝑞𝑞 𝑖𝑖 = 𝜖𝜖 (𝛽𝛽 𝑞𝑞 𝑖𝑖 = 𝜖𝜖). Example 4: Recall the automaton 𝐺𝐺 1 from Fig. 1. We had 𝑄𝑄 = {0,1,2,3} , Σ = {𝑎𝑎𝑟𝑟𝑔𝑔, 𝑇𝑇𝑎𝑎𝑇𝑇𝑇𝑇𝑎𝑎} , 𝑄𝑄 0 = {0}, 𝑄𝑄 𝑚𝑚 = {1}. For this example, we obtain the following initial/final vectors and matrices (these four matrices represent the behavior at the latest and at the earliest of the TAG 𝐺𝐺 1 ): 𝛼𝛼 = (𝑒𝑒 𝜖𝜖 𝜖𝜖 𝜖𝜖) ; 𝛽𝛽 = � 𝜖𝜖 𝑒𝑒 𝜖𝜖 𝜖𝜖 � ; 𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑎𝑎𝑟𝑟𝑔𝑔) = � 𝜖𝜖 ⊤ 𝜖𝜖 𝜖𝜖 𝜖𝜖 ⊤ 1 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 � ; 𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑇𝑇𝑎𝑎𝑇𝑇𝑇𝑇𝑎𝑎) = � 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 1 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 � ; 𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑎𝑎𝑟𝑟𝑔𝑔) = � 𝜖𝜖 0 𝜖𝜖 𝜖𝜖 𝜖𝜖 1 0 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 � ; 𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑇𝑇𝑎𝑎𝑇𝑇𝑇𝑇𝑎𝑎) = � 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 0 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 � ;

Definition 4 :

 4 Consider two vectors 𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑤𝑤) ∈ ℝ � 𝑀𝑀𝑀𝑀𝑀𝑀 1×|𝑄𝑄| and 𝑥𝑥 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑤𝑤) ∈ ℝ � 𝑀𝑀𝑀𝑀𝑀𝑀 1×|𝑄𝑄| , 𝑤𝑤 ∈ Σ * , called generalized bounds, and defined as follows:

Remark 3 :

 3 Following that definition, built matrices of 𝜇𝜇 1||2,𝐼𝐼𝑛𝑛𝐼𝐼 and 𝜇𝜇 1||2,𝑆𝑆𝑜𝑜𝑝𝑝 contain values for transitions that cannot be reached from the initial states. In particular, if ∃𝑘𝑘 ∈ [1; |𝑄𝑄 1 × 𝑄𝑄 2 |] such that for all 𝑒𝑒 𝑣𝑣 ∈ Σ 1||2 , 𝛼𝛼 𝑘𝑘 �𝜇𝜇 1||2,𝑆𝑆𝑜𝑜𝑝𝑝 (𝑒𝑒 𝑣𝑣 )� :,𝑘𝑘 = 𝜖𝜖 and �𝜇𝜇 1||2,𝐼𝐼𝑛𝑛𝐼𝐼 (𝑒𝑒 𝑣𝑣 )� :,𝑘𝑘 = 𝜖𝜖 then the corresponding states cannot be reached from the initial states.

Figure 5 -

 5 Figure 5 -Jobshop represented as a TAGThe linear representation of this TAG is:𝛼𝛼 = (𝑒𝑒𝜖𝜖𝜖𝜖𝜖𝜖𝜖𝜖𝜖𝜖𝜖𝜖𝜖𝜖𝜖𝜖𝜖𝜖𝜖𝜖), 𝛽𝛽 = (𝜖𝜖𝜖𝜖𝜖𝜖𝜖𝜖𝜖𝜖𝑒𝑒𝜖𝜖𝜖𝜖𝑒𝑒𝜖𝜖𝜖𝜖) ⊤ , 𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑇𝑇) ∈ 𝔻𝔻 |11|×|11| , 𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑇𝑇) ∈ 𝔻𝔻 |11|×|11| , 𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑎𝑎) ∈ 𝔻𝔻 |11|×|11| , 𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑎𝑎) ∈ 𝔻𝔻 |11|×|11| , 𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑐𝑐) ∈ 𝔻𝔻 |11|×|11| , 𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑐𝑐) ∈ 𝔻𝔻 |11|×|11| , 𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑔𝑔) ∈ 𝔻𝔻 |11|×|11| , 𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑔𝑔) ∈ 𝔻𝔻 |11|×|11| , 𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑒𝑒) ∈ 𝔻𝔻 |11|×|11| , 𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑒𝑒) ∈ 𝔻𝔻 |11|×|11| , 𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑖𝑖) ∈ 𝔻𝔻 |11|×|11| , 𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑖𝑖) ∈ 𝔻𝔻 |11|×|11| .Three of these matrices are detailed as an example. The other are not shown for the sake of clarity.

𝒥𝒥 1 : 2 = 5 . 4

 1254 𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑇𝑇𝑎𝑎𝑐𝑐) = 𝛼𝛼 ⊗ 𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑇𝑇) ⊗ 𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑎𝑎) ⊗ 𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑐𝑐) 𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑇𝑇𝑎𝑎𝑐𝑐) = (𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 6.6 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖) 𝑥𝑥 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑇𝑇𝑎𝑎𝑐𝑐) = 𝛼𝛼 ⊗ 𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑇𝑇) ⊗ 𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑎𝑎) ⊗ 𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑐𝑐) 𝑥𝑥 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑇𝑇𝑎𝑎𝑐𝑐) = (𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 5.4 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖) Hence, it is possible to reach the state 6 between �𝑥𝑥 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑇𝑇𝑎𝑎𝑐𝑐)� and �𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑇𝑇𝑎𝑎𝑐𝑐)� 2 = 6.6 time units. Since the state 2 correspond to the end job 𝒥𝒥 1 , the processing time of one job 𝒥𝒥 1 is from 5.4 to 6.6 time units. • Processing time of one job 𝒥𝒥 2 : 𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑔𝑔𝑒𝑒𝑖𝑖) = 𝛼𝛼 ⊗ 𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑔𝑔) ⊗ 𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑒𝑒) ⊗ 𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑖𝑖) 𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑔𝑔𝑒𝑒𝑖𝑖) = (𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 5.5 𝜖𝜖 𝜖𝜖) 𝑥𝑥 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑔𝑔𝑒𝑒𝑖𝑖) = 𝛼𝛼 ⊗ 𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑔𝑔) ⊗ 𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑒𝑒) ⊗ 𝜇𝜇 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑖𝑖) 𝑥𝑥 𝐼𝐼𝑛𝑛𝐼𝐼 (𝑔𝑔𝑒𝑒𝑖𝑖) = (𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 4.5 𝜖𝜖 𝜖𝜖)

  𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 2.2 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 ⎦ 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 2.2 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 1.1 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 0 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 𝜖𝜖 ⎦

  ). For 𝑒𝑒 𝑣𝑣 ∈ Σ, 𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑤𝑤𝑒𝑒 𝑣𝑣 ) = 𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑤𝑤) ⊗ 𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑒𝑒 𝑣𝑣 ) �𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑤𝑤𝑒𝑒 𝑣𝑣 )� 𝑘𝑘 = ��𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑤𝑤)� 𝑖𝑖 ⊗ �𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑒𝑒 𝑣𝑣 )� Since the property is true for 𝑤𝑤, there is at most one 𝑗𝑗 such that �𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑤𝑤)� 𝑖𝑖 ≠ 𝜖𝜖. Hence �𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑤𝑤𝑒𝑒 𝑣𝑣 )� 𝑘𝑘 = �𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑤𝑤)� 𝑖𝑖 ⊗ �𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑒𝑒 𝑣𝑣 )� Then there is at most one 𝑎𝑎 such that �𝜇𝜇 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑒𝑒 𝑣𝑣 )� 𝑖𝑖𝑗𝑗 ≠ 𝜖𝜖, hence, such that �𝑥𝑥 𝑆𝑆𝑜𝑜𝑝𝑝 (𝑤𝑤𝑒𝑒 𝑣𝑣 )� 𝑗𝑗 ≠ 𝜖𝜖. The property is true for a sequence 𝑤𝑤𝑒𝑒 𝑣𝑣 . The property is true for 𝜖𝜖, and the heredity has been proved for any 𝑤𝑤. Hence, the property is proved by induction. █ �𝑄𝑄 1 , Σ 1 , 𝑇𝑇𝑇𝑇𝑇𝑇 1 , 𝛼𝛼 1 , 𝛽𝛽 1 , 𝜇𝜇 1,𝑆𝑆𝑜𝑜𝑝𝑝 , 𝜇𝜇 1,𝐼𝐼𝑛𝑛𝐼𝐼 � and 𝐺𝐺 2 = �𝑄𝑄 2 , Σ 2 , 𝑇𝑇𝑇𝑇𝑇𝑇 2 , 𝛼𝛼 2 , 𝛽𝛽 2 , 𝜇𝜇 2,𝑆𝑆𝑜𝑜𝑝𝑝 , 𝜇𝜇 2,𝐼𝐼𝑛𝑛𝐼𝐼 �. The parallel composition of 𝐺𝐺 1 and 𝐺𝐺 2 is the automaton 𝐺𝐺

					𝑖𝑖𝑘𝑘
		𝑖𝑖
	C. Parallel composition
	Definition	5:	Consider	two	TAGs
	𝐺𝐺 1 =

𝑖𝑖𝑘𝑘

Moreover, 𝐺𝐺 is event-deterministic. 1||2 = 𝐴𝐴𝑐𝑐�𝑄𝑄 1 × 𝑄𝑄 2 , Σ 1 ∪ Σ 2 , 𝑇𝑇𝑇𝑇𝑇𝑇 1||2 , 𝛼𝛼 1||2 , 𝛽𝛽 1||2 , 𝜇𝜇 1||2,𝑆𝑆𝑜𝑜𝑝𝑝 , 𝜇𝜇 1||2,𝐼𝐼𝑛𝑛𝐼𝐼 � with:

  2 �𝜇𝜇 𝑖𝑖,𝑆𝑆𝑜𝑜𝑝𝑝 (𝑒𝑒 𝑣𝑣 )� 𝑞𝑞 𝑖𝑖,𝑖𝑖𝑖𝑖 ,𝑞𝑞 𝑖𝑖,𝑜𝑜𝑜𝑜𝑜𝑜 𝑖𝑖𝑖𝑖 �𝜇𝜇 𝑖𝑖,𝑆𝑆𝑜𝑜𝑝𝑝 (𝑒𝑒 𝑣𝑣 )� For all 𝑒𝑒 1 ∈ Σ 1 \Σ 2 and 𝑞𝑞 2 ∈ 𝑄𝑄 2 ,

				𝑞𝑞 𝑖𝑖,𝑖𝑖𝑖𝑖 ,𝑞𝑞 𝑖𝑖,𝑜𝑜𝑜𝑜𝑜𝑜	≠ 𝜖𝜖
			𝜖𝜖 𝑒𝑒𝑎𝑎𝑟𝑟𝑒𝑒
	𝐼𝐼𝐼𝐼 ℝ � 𝑀𝑀𝑀𝑀𝑀𝑀 ,
	�𝜇𝜇 1||2,𝐼𝐼𝑛𝑛𝐼𝐼 (𝑒𝑒 𝑣𝑣 )�	�𝑞𝑞 1,𝑖𝑖𝑖𝑖 × 𝑞𝑞 2,𝑖𝑖𝑖𝑖 �,�𝑞𝑞 1,𝑜𝑜𝑜𝑜𝑜𝑜 ×𝑞𝑞 2,𝑜𝑜𝑜𝑜𝑜𝑜 �
	= � ⨁ 𝑖𝑖=1,2 �𝜇𝜇 𝑖𝑖,𝐼𝐼𝑛𝑛𝐼𝐼 (𝑒𝑒 𝑣𝑣 )�	𝑞𝑞 𝑖𝑖,𝑖𝑖𝑖𝑖 ,𝑞𝑞 𝑖𝑖,𝑜𝑜𝑜𝑜𝑜𝑜	𝑖𝑖𝑖𝑖 �𝜇𝜇 𝑖𝑖,𝐼𝐼𝑛𝑛𝐼𝐼 (𝑒𝑒 𝑣𝑣 )�	𝑞𝑞 𝑖𝑖,𝑖𝑖𝑖𝑖 ,𝑞𝑞 𝑖𝑖,𝑜𝑜𝑜𝑜𝑜𝑜	≠ 𝜖𝜖
			𝜖𝜖 𝑒𝑒𝑎𝑎𝑟𝑟𝑒𝑒
	•


Jean-François Mignot
email: jeffmignot@yahoo.fr

Keywords: Adoption, descent, divorce, international comparison, historical demography, France, Italy

Adoption law in France and Italy is quite similar, and since the 1990s, these two countries have been among those which adopt the largest numbers of children from abroad. But over a longer timescale, what are the similarities and differences in their adoption practices? This article retraces the history of adoption law and practices in France and Italy since the nineteenth century. While adoption law in the two countries has followed a similar trajectory, the actual numbers of simple adoptions are very different, mainly because far fewer stepfamilies are formed after divorce in Italy than in France. By contrast, the number of full adoptions and the characteristics of the children concerned are similar in both countries. After facing a scarcity of domestic adoptable children, potential adopters have, since 2011, been confronted with a drop in the number of minors available for intercountry adoption. As a consequence, intercountry adoptees in France and Italy tend to be older, and more often have siblings and/or health problems or disabilities than in the past.

Introduction

Today, France and Italy have relatively similar adoption laws that differ from those in English-speaking countries. Since the 1990s, they have also been among those countries like Spain and, even more so, the United States, that have adopted the largest number of minors from other countries, unlike Germany or the United Kingdom, for example, which practise far less intercountry adoption, or Japan, where virtually no foreign minors are adopted.

Adoption is a legal institution that creates a parent-child relationship between an adopter and an adoptee that is not based on the adoptee being the biological offspring of the adoptive person or couple. Adoption enables the adoptee to inherit the adopter's surname and property.1 French law distinguishes between simple adoption and full or plenary (plénière) adoption. Full adoption creates between an adopted minor and an adoptive person or couple a parentchild relationship that replaces that between the adoptee and his/her birth parents. Full adoption thus creates a new legal relationship, both exclusive and substitutory, whereby the adoptee takes on surname and inheritance rights solely from the adoptive family. Simple adoption, on the other hand, creates a parent-child relationship between the adopteewho may well be an adultand the adopter in addition to that existing between the adoptee and his/her birth parents. With simple adoption, the adoptee adds to his/her original surname and inheritance rights those received from the adopter.

Adoption has long been of interest to anthropologists [START_REF] Fine | Adoptions. Ethnologie des parentés choisies[END_REF], sociologists [START_REF] Fisher Allen | Still "Not Quite As Good As Having Your Own"? Toward a Sociology of Adoption[END_REF] and psychologists [START_REF] Savard | La théorie de l'attachement. Une approche conceptuelle au service de la protection de l'enfance[END_REF], but demographers have only recently begun to analyse the phenomenon. Even now, the study of adoption occupies only a marginal place in demography, as can been seen from its virtual absence from the discipline's reference handbook [START_REF] Caselli Graziella | Démographie. Analyse et synthèse I. la dynamique des populations[END_REF]. Indeed, adoption has very little impact on population dynamics, and can only be studied in relation to law, a discipline that has few ties with demography. However, with the increasing number of intercountry adoptions, adoption has become a form of migration (Weil, 1984). Furthermore, since the 1940s, intercountry adoption has been linked to demographic crises (war, disease or famine) in the sending countriesnot necessarily those with the lowest incomes or the highest birth ratesand with demographic and legal changes in the receiving countries, where the spread of contraception and abortion has reduced the number of abandoned, and therefore adoptable, minors [START_REF] Peter | Intercountry Adoption in the New Millennium; the "Quiet Migration" Revisited[END_REF].

Demographically speaking, it is of particular interest to compare adoption practices in France and Italy, for two reasons. First, no western country other than Italy has had adoption laws so similar to those of France for so long. Consequently, comparing adoption practices in the two countries makes it possible to identify variations "controlling for legal environment", i.e. differences in behaviour that are not due to differences in adoption law but in the opportunity or desire to adopt; in other words, differences in demographic behaviour. Second, comparing adoption practices in France and Italy enables us to examine not only full adoptions (particularly intercountry) but also simple adoptions, which do not exist in common-law countries like the United States, where there are no long-term aggregate or individual data on adoption [START_REF] Wayne | Family Matters: Secrecy and Disclosure in the History of Adoption[END_REF][START_REF] Davis | Children for Families or Families for Children[END_REF]Herman, 2008;[START_REF] Lovelock | Intercountry Adoption as a Migratory Practice: A Comparative Analysis of Intercountry Adoption and Immigration Policy and Practice in the United States, Canada and New Zealand in the Post W.W.II Period[END_REF].

This article presents a comparative history of adoption law and practice in France and Italy since the nineteenth century, analysing the degree of similarity between the two countries over the long term and the signification of the differences observed. We begin with a historical review of adoption law in France since 1804 and Italy since 1865. Then we look at variations in the annual numbers of full and simple adoptions. Last, distinguishing between domestic and intercountry full adoptions, we analyse their numbers and characteristics, and the demographic developments they reveal.

Adoption laws with similar histories

Adoption law determines who may adopt, who may be adopted, what procedure is to be followed in adopting and what are the legal consequences of the adoption. There have been three main periods since the nineteenth century: first, the establishment of simple adoption of adults for inheritance purposes; second, simple adoption of minors for child protection; and finally full adoption. These stages occurred in both France [START_REF] Gutton | Histoire de l'adoption en France[END_REF][START_REF] Halifax | L'adoption plénière en France : de l'établissement d'une filiation légale à la constitution d'une filiation sociale, Thèse de démographie sous la direction de François Héran[END_REF][START_REF] Murat | Les transformations de la famille. Quel impact sur les finalités de l'adoption ?[END_REF][START_REF] Neirinck | L'évolution de l'adoption[END_REF] and Italy [START_REF] Brand | Adoption -Italie[END_REF] Center for Adoption [START_REF] Policy | Overview of Italian Adoption Law[END_REF][START_REF] Sénat | L'adoption[END_REF], with Italy lagging slightly behind France. France (1804France ( -1923) ) and Italy (1865-1942) Adoption was introduced into French and Italian law at the same time as their first civil codes in the nineteenth century, themselves strongly inspired by Roman law, which recognized the adoption for inheritance purposes of adults who were sui juris, i.e. not subject to the legal power of another, known as "adrogation".

a. Simple adoption of adults for inheritance purposes in

In France the 1804 Civil Code introduced the adoption of adults over age 21. Men and women aged over 50 were entitled to adopt, whether married or not, on condition they had no legitimate children. This adoption had two major effects: it added the surname of the adopter to that of the adoptee, and gave the adoptee the same rights to inherit from the adopter as a legitimate child. Adoption, therefore, did not nullify the relationship between adoptees and their birth family; it created an additional parent-child relationship. Furthermore, adoption entailed for adoptees a number of marital prohibitions: they could not marry either their adopter or the adopter's spouse or any other children (adopted or biological) of the same adopter. Adoption also created mutual claims to maintenance payments between adopter and adoptee. However, adoption did not bring adoptees into the family of their adopter, since adoptees could only inherit from the adopter and not from the adopter's ascendants or collateral kin.

Likewise in Italy, the 1865 Civil Code, the first of united Italy, greatly inspired by the Code Napoléon, introduced adoption for adults aged 18 (although the age of civil majority was 21). More specifically, only persons of age whose parents gave their consent could be adopted. Men and women aged over 50 were entitled to adopt, whether married or not, on condition they had no legitimate or legitimized children and were at least 18 years older than the adoptee. The legal effects of adoption were identical to those of the French Civil Code, except that a person could not adopt their own natural child (whereas in France throughout the nineteenth century, most adoptions involved people adopting their natural children so that they could inherit like legitimate children). As in France, adoption created an additional parent-child relationship: it did not nullify the adoptees' relationship with their birth family and merely added to the adoptees' surname and inheritance rights those they took from the adopter.

b. Simple adoption not merely for inheritance purposes but also for child protection, in France (1923)(1924)(1925)(1926)(1927)(1928)(1929)(1930)(1931)(1932)(1933)(1934)(1935)(1936)(1937)(1938)(1939) and Italy (1942-1967) The First World War caused some 1,400,000 deaths in France and 650,000 in Italy [START_REF] Rohrbasser | Hécatombe[END_REF]. As a result, adoption was seen as one way of caring for war orphans not taken in by their extended families [START_REF] Ivan | Ni père ni mère. Histoire des enfants de l'Assistance publique[END_REF]. In France, the law of 19 June 1923 made minors adoptable. Adults aged at least 40 with no legitimate children were entitled to adopt a minor, as were infertile couples and many couples who had lost an only child during the war. The adoption of a minor conferred on the adopter "paternal authority" over the adoptee, i.e. all the rights and responsibilities of a father with respect to his minor children (replaced since the law of 4 June 1970 by "parental authority"). However the law only authorized simple adoption, which created an additional parent-child relationship.

In Italy, the Royal Decree no. 1357 of 31 July 1919 and Law no. 1458 of 24 September 1940, both relating to the adoption of war orphans, provided evidence that legislators were beginning to see adoption as an instrument of social welfare for abandoned children. However, it was not until 1942 that the new Civil Code made minors adoptable. Adults over 50 with no legitimate children were entitled to adopt a minor [START_REF] Brand | Adoption -Italie[END_REF]. As in France, the adoption of minors conferred paternal authority on the adopter, but the law still only authorized simple adoption. After the war, the clauses on adoption in the 1942 Civil Code were amended to remove their racist elements, in particular the prohibition on adopting non-Aryans (Royal Decree of 20 January 1944).

c. Full adoption, in France (since 1939) and Italy (since 1967)

In France the decree-law of 29 July 1939, also called the Code de la famille, introduced full adoption into French law (légitimation adoptive from 1939 to 1966, adoption plénière since 1966). This new type of adoption not only brought the adopted child into the adopter's family but also, crucially, nullified the relationship, particularly for inheritance, that bound adoptees to their birth family. Consequently, this adoption guaranteed the exclusiveness of the parentchild relationship between the adoptive parents and the child and thus overcame a certain reluctance to adopt, and also ensured that the adoptee would not be moved from one family to another. Couples wishing to apply for full adoption had to be married for a minimum period (10 years in 1939, two years since 1996), with at least one spouse above a certain age (35 in 1941, 28 since 1996) and a certain number of years older than the adoptee (at least 15 years since 1966), and, until 1976, have no legitimate children of their own (since 1976 couples or individuals with children, legitimate or not, may adopt). Furthermore, since 1966, full adoption is open not only to married couples but also to single persons above a certain age (30 in 1966, 28 since 1996). To qualify for full adoption, minors must be under a certain age (5 years in 1939, 15 since 1966) and be orphaned or abandoned. Since 1966, the couples and persons entitled to adopt a child under the conditions of full adoption can also make a simple adoption; and a simple adoptee may be of any age. Although the 1939 regulations were reorganized in the Law of 11 July 1966, two types of adoption have existed, in practice, since 1939: simple adoption creating an additional parent-child relationship, and full adoption creating a new and exclusive parent-child relationship.

Law no. 431 of 5 June 1967 introduced full adoption in Italy. As in France, this new type of adoption, intended to give abandoned minors a family, brought the adoptee into the adopter's family and nullified adoptees' parent-child relationship with their birth family. From 1967 to 1983, full adoption was called "special adoption" (adozione speziale) to distinguish it from simple adoption, known as "ordinary adoption" (adozione ordinaria). Couples aged at least 35, married for at least five years and not separated were entitled to practice full adoption; the full adoptee could be a minor, on condition that he/she was at least 18 years younger than the adopter. For simple adoption, adopters could be individuals or couples with no children, the aim in this case being to transmit their surname and estate to an adopted minor or an adopted adult if both parties agreed. These regulations were reorganized by Law no. 184 of 4 May 1983: simple adoption, reserved for adults over 18, is now called "adoption of persons of legal age" (adozione di persone maggiori di età), and full adoption, reserved for minors (whether abandoned or not), is called "adoption of minors" (adozione di minori). Since Law no. 149 of 28 March 2001, the maximum authorized age difference between the adoptee and the fully adopted minor has been raised from 40 to 45 years. In short, the two major types of adoptionsimple and fullhave existed in Italy since 1967.

d. Current state of adoption law

At present, adoption law in France and Italy is very similar. Both countries distinguish between simple adoption, mainly for inheritance purposes, and full adoption to provide a nurturing environment for the adopted child, whose main objective, from the legislator's viewpoint, is to promote the child's interests. Over time, the same changes have occurred in France and Italy: the preferred form has become full rather than simple adoption; furthermore, legislators have come to see full adoption as intended not so much to satisfy the desire of the adopter (to bring up a child), even less those of the adoptee's birth parents (not to have to bring up a child), but rather to meet the needs of the adoptee (to have loving parents). In both countries, the stipulations of full adoption law are similar (see Table 1, which only covers adoption from outside the family, since adoption within the family is subject to fewer conditions). Both There does, however, remain one major difference between French and Italian law on full adoption. In France, since 1966, single men and women, in particular homosexuals, have been able to fully adopt a minor (although overt homosexuality has often been grounds for administrative refusal), and since the Law of 17 May 2013, this right has been extended to married couples of the same sex. In Italy, however, single persons may not adopt under the conditions of full adoption and, since there is no same-sex marriage, homosexual couples are generally excluded likewise. Although same-sex couple adoption has yet to be analysed by demographers in France, the question has been examined from a demographic standpoint in the United States [START_REF] Davis | Demographics of Gay and Lesbian Adoption and Family Policies[END_REF].

French and Italian law is also fairly similar regarding access of abandoned and adopted children to information about their origins: this access remains quite difficult but has been recently liberalized. France and Italy are among the small number of countries whose Civil Code allows a woman to give birth "in secret" and not recognize her child [START_REF] Lefaucheur | De la tradition française au droit à la vérité de la biographie -ou du recours à l'histoire dans les débats parlementaires sur l'accouchement dit sous X[END_REF]. In practice, this means that the mother's name can be omitted from the child's birth certificate. Consequently, for many years it was extremely difficult for children born secretly (né sous X) in both France and Italy to obtain any details about their birth parents, even nonidentifying information (state of health, circumstances and reasons for abandonment, etc.), while access to nominative records (first and last names of birth parents and siblings) was almost totally impossible. It is generally easier for domestic adoptees (from the same country) not born anonymously, particularly the few who were legally recognized before being abandoned or adopted by consent, to find out about their origins.

In Italy, Law no. 149 of 28 March 2001 liberalized adoptees' access to information about their origins. From the age of 25 (the usual age of majority has been 18 since 1975) an adoptee may apply to the juvenile court to have access to identifying or other information about their birth parents. However, if the adoptee was born anonymously or if at least one of the birth parents has refused to release their identity, then this information cannot be divulged. In France, since the Law of 22 January 2002 relating to access to the origins of adopted persons and wards of the State, the secrecy of parenthood may be reversed: an adoptee after reaching majority may apply to the high council for access to personal origins (Conseil national pour l'accès aux origines personnelles, CNAOP) to obtain information about their birth parents (for a quantitative approach to the activities of the CNAOP, see Voisin and Georges, 2011). Again, if the birth parents of the adoptee born in secret refuse to waive that secrecy, the adoptee is not allowed to know their identities. In neither country is there a recognized general right for children born anonymously (even when they are adult) to know their origins, let alone the identity of their birth parents. In 2013, however, the Constitutional Court in Italy did establish the right of an individual to know his/her origins, even if the mother wishes to remain anonymous, if it is essential for that person's health.

Numbers of simple and full adoptions

How have adoption practices changed since their recognition under French and Italian law? To find out, we begin by comparing adoption numbers in the two countries.

a. Statistical sources on adoption

France and Italy are among the few countries with long-term statistical data on both simple and full adoption. In both countries a centralized administration records adoptions each year.

In France, the main source of information is a publication from the Ministry of Justice that has had various names and which we will call the Compte Général (ministère de la Justice, 1841Justice, -1932Justice, , 1933Justice, -1960Justice, , 1961Justice, -1976[START_REF] Justice | Annuaire statistique de la Justice[END_REF]. This is a statistical yearbook that has recorded judgements of simple adoption since 1841 (no data for 1804-1840) and of full adoption since 1952 (no data for 1939-1951). Information on adoption was no longer included from the early 1980s, so is supplemented by two one-off surveys the Ministry of Justice carried out in 1992 [START_REF] Belmokhtar | Les adoptions simples et plénières en 1992[END_REF] and 2007 [START_REF] Belmokhtar Zakia | L'adoption simple et plénière en 2007 : des projets différents[END_REF]. The yearbooks and surveys provide data on simple and full adoptions, both domestic and intercountry, but for the judgements of full adoption of foreign-born children they only include those issued in France (and not in other countries). Furthermore, for intercountry adoptions (full adoptions in the vast majority of cases), since 1979, the Ministry of Foreign Affairs has registered the number of "adoption" visas it issues to minors each year (ministère des Affaires étrangères, 2014). Because a child adoption judgement may not be issued until at least six months after the child's arrival and a court may refuse the adoption application, the number of adoption visas issued in a given year is not a rigorous count of the number of intercountry adoptions in that year. However, changes in the number of adoption visas issued over the years does give a fairly accurate idea of trends. In the case of wards of the state, the National Observatory for Children in Danger (Observatoire national de l'enfance en danger, ONED) records the number of adoptable French-born minors (who, if adopted, are almost all adopted via a full adoption procedure) (ONED, 2007(ONED, -2013)).

In Italy, the main sources of information are publications from various ministries and other institutions (Ministero di agricoltura, industria e commercio, 1891-1906;Ministero di grazia e giustizia, 1907Ministero di grazia e giustizia, -1935;;ISTAT, Movimento dei procedimenti civili, 1936[START_REF] Belmokhtar | Les adoptions simples et plénières en 1992[END_REF] Ministero della giustizia since 1997). In 2011, for the 150th anniversary of Italian unification, the national statistical institute ISTAT collected and published these historical series, which record simple adoption judgements from 1891 (no data for 1865-1890) until 1983 (no data since 1984) and full adoption judgements since 1968 (ISTAT, 2011). Furthermore, for intercountry adoptions, a number of institutions have, since the 1990s, recorded the number of foreign-born minors authorized to enter Italy [START_REF] Istituto | Come cambia l'adozione internazionale in Italia. Le coppie e i bambini nel monitoraggio della Commissione per le adozioni internazionali negli anni 2000-2007[END_REF]; Commissione per le adozioni internazionali, 2014). As in France, the number of minors authorized to enter the country does not strictly correspond to the number of foreign-born adoptees in Italy that year, but does give a fair idea of the trends.

Unfortunately, no source provides information about changes in the characteristics of the native-born or foreign women or couples who have put their children up for adoption. This is the least well researched aspect of the history of adoption in France, Italy and most other countries (for Ukraine, see Mykytyn-Gazziero, 2014).

b. Trends in the numbers of simple adoptions

The number of simple adoptions in France and Italy followed parallel trends from the nineteenth century to the mid-1970s (Figure 1). In France, when the only form of adoption was simple adoption of adults for inheritance purposes , there were about 100 a year. In Italy, when it was also solely for inheritance purposes , there were about 100 per year until the First World War, then 200-500 a year between the Wars, and more than 1,000 per year at the start of the Second World War. Then, in both countries, the introduction of simple adoption of minors not only for inheritance but also child protection led to a considerable increase in annual numbers. In France, from 1923 to 1939, more than 1,000 simple adoptions took place each year, although unfortunately it is not known what proportion were minors. In Italy from 1942 to 1967, the number of simple adoptions per year exceeded 2,000, most of whom were minors (from 1955 to 1979, between 55% and 80% of simple adoptions were of minors ; [START_REF] Brand | Adoption -Italie[END_REF]. The introduction of full adoption [START_REF] Ivan | Ni père ni mère. Histoire des enfants de l'Assistance publique[END_REF]( in France, 1967 in Italy) led to a fall in the number of simple adoptions up to the mid-1970s, as many adopters preferred to create an exclusive parent-child relationship with the adoptee rather than an additional one [START_REF] Marie-Pierre | Effectivité de la loi du 11 juillet 1966[END_REF]. In France, from the post-war years (marked by the effects of the World War II) until the mid-1970s, and even more in Italy after 1967, the annual number of simple adoptions declined. Independently of differences in the timing of changes in adoption laws in the two countries, the trends in annual numbers of simple adoptions run parallel until the mid-1970s. They were few in number until the turn of the twentieth century, then rose sharply in France following the First World War and Italy following the Second, peaking in both countries after the Second World War and then falling until the mid-1970s. In both countries it seems to have been the increase in the number of adoptable minors following the world wars (war orphans and abandoned children) that, along with the legalization of simple adoption of minors, had the strongest influence on trends in the number of simple adoptions per year until the mid-1970s. Although we have no accurate information on the identity of adoptees and adopters in Italy, in France from 1923 until the mid-1970s, simple adoption was typically a case of an aunt or step-mother, unmarried or widowed with no children, adopting a niece or stepdaughter that she had looked after as a minor, in order to bequeath property to her [START_REF] Fine | Regard anthropologique et historique sur l'adoption. Des sociétés lointaines aux formes contemporaines[END_REF]Mignot, 2015a).

Since the mid-1970s, the annual number of simple adoptions has boomed in France, but fallen in Italy, so much so that ISTAT stopped recording their number as early as 1983. In the most recent period in France, the annual number of simple adoptions has probably exceeded 10,000 [START_REF] Belmokhtar Zakia | L'adoption simple et plénière en 2007 : des projets différents[END_REF] while in Italy it has been below 1,000 (688 in 2012 and 743 in 2013 according to a personal communication from the Direzione Generale di Statistica -Ministero della Giustizia). It is true that, unlike French law, Italian law does not allow simple adoptions (adozioni di persone maggiori d'età) of minors; but in France since at least the 1990s, 85% of simple adoptions have been of adults, aged around 33 on average [START_REF] Belmokhtar | Les adoptions simples et plénières en 1992[END_REF][START_REF] Belmokhtar Zakia | L'adoption simple et plénière en 2007 : des projets différents[END_REF]. And above all, since 1983, Italian law has allowed simple adoption of minors within families (adozioni di casi particolari); but from 1993 to 2012 the annual number of these casi particolari has always been below 1,000 (minimum 491 in 1993, maximum 711 in 2008) [START_REF] Giustizia Minorile | L'applicazione della Legge 4 maggio 1983 n. 184[END_REF][START_REF] Giustizia Minorile | Dati statistici relativi all'adozione anni 2000-2012[END_REF].

Consequently the low number of simple adoptions in Italy is probably not due primarily to the specific features of Italian adoption law. How can we explain why the numbers of simple adoptions were similar until the mid-1970s and have diverged since? In France, their number rose sharply in parallel with the massive increase in stepfamilies after divorce (Mignot, 2015a). Since the 1970s, the increase in simple adoptions in France has been due to simple adoption of stepchildren by stepparents; in other words, stepparents, usually with no children of their own, adopt the stepchild they have helped bring up, in order to pass on their inheritance [START_REF] Martial | L'adoption de l'enfant du conjoint dans les familles recomposées[END_REF][START_REF] Martial | S'apparenter. Ethnologie des liens de familles recomposées[END_REF]. Conversely, stepfamilies are still quite rare in Italy because of the lower number of divorces. Since the 1970s there have been between twice and seven times as many divorces a year in France as in Italy, and the total divorce rate in Italy is onethird to one-eighth that of France [START_REF] Ined | Base de données Démographie des pays développés[END_REF]. On the other hand, the rate of remarriage appears to be lower in France than in Italy, at least in recent years: 2.1% of divorcees resident in France in 2012 remarried that year (INSEE, 2014) compared with 3% in Italy (ISTAT, 2013). It is not known whether the stepfamilies most likely to practise simple adoption (i.e. those including not only a parent and child but also a spouse with no children) are proportionately more numerous in France than in Italy. Overall, it is probably the relative infrequency of divorce and the low number of stepfamilies that explain why simple adoptions are much rarer in Italy than in France. But this does not rule out the existence of other possible mechanisms. (a) Sources : Ministère de la Justice, Compte général; [START_REF] Belmokhtar | Les adoptions simples et plénières en 1992[END_REF][START_REF] Belmokhtar Zakia | L'adoption simple et plénière en 2007 : des projets différents[END_REF][START_REF] Istat | Serie storiche. Tavola 6.9 Provvedimenti giudiziari in materia di stato delle persone -Anni 1891-2008 (valori assoluti). Adozioni di minori (di cui : adozioni di minori stranieri)[END_REF]communication

c. Trends in the numbers of full adoptions

Full adoption has existed in France since 1939 (known as légitimation adoptive until 1966) and in Italy since 1967. Since those dates the numbers offull adoptions in both countries have been of a similar magnitude, around 2,500-5,000 per year (Figure 2). Although the annual number rose in France until the late 1970s [START_REF] Jacques | L'adoption[END_REF][START_REF] Marie-Pierre | Effectivité de la loi du 11 juillet 1966[END_REF] and in Italy until the late 2000s, the figures are now stable, with no increase observed, either in France or in Italy.

Numbers and characteristics of domestic and intercountry full adoptions

To understand why the annual number of full adoptions in France and Italy has levelled off, it is necessary to describe their characteristics. Although, to our knowledge, no information is published about Italian simple adoptions (but like French ones they are almost all domestic), it is possible to compare French and Italian full adoptions, at least for recent years. How far have the trends in domestic and intercountry full adoption been similar in France and Italy? Do French and Italian adoptees resemble each other? a. Few domestic minors available for full adoption Since at least the 1990s, the number of domestic minors available for full adoption has been low and stable in Italy, and low and falling in France (Figure 3). In France the total number (stock) of adoptable domestic minors fell from over 4,000 in the early 1990s to just over 2,000 in the 2010s. In Italy the stock never reached 2,000 from the mid-1990s to the mid-2010s. Given the number of approved potential adopters, three to twelve times higher than the number of adoptable minors (depending on year and country), there are not enough adoptable minors to meet demand (ONED, 2007(ONED, -2013;; Commissione per le adozioni internazionali, 2014). In both countries the liberalization of contraception and abortion has reduced the number of unwanted births and even more so the number of abandoned newborns. For example, the number of children born secretly in France fell from approximately 2,000 per year in the late 1960s to approximately 1,000 in the 1990s and 600 in the 2000s (Villeneuve-Gokalp, 2001). Similarly, the number (flow) of abandoned children was approximately 1,000 per year in the 2000s (ONED, 2007(ONED, -2013;;[START_REF] Fréchon Isabelle | État des lieux de l'enfance en danger, sources et données disponibles en France[END_REF]. This is why there are so few adoptable domestic minors in France, Italy and other Western countries (United Nations, 2009).

b. Development of intercountry adoptions and their recent decline

The shortage of adoptable domestic minors and the length of national adoption procedures have caused potential adopters in France and then in Italy to turn to intercountry adoption. The same holds in most western countries, where intercountry adoption has been extensively researched (Weil, 1984), particularly by the British demographer Peter Selman [START_REF] Peter | Intercountry Adoption in the New Millennium; the "Quiet Migration" Revisited[END_REF][START_REF] Peter | Trends in Intercountry Adoption: Analysis of Data from 20 Receiving Countries, 1998-2004[END_REF][START_REF] Peter | The Rise and Fall of Intercountry Adoption in the 21 st Century[END_REF][START_REF] Peter | Global Trends in Intercountry Adoption: 2001-2010[END_REF].

From 1990 to 2005 (in France) and 2010 (Italy), there were around 3,000 intercountry adoptions per year, with a rising trend (Figure 4). Since 2011, however, the number has fallen, more in France than in Italy. The traditional home countries of intercountry adoptees have become wealthier and more peaceful, fertility has declined, social and child support policies have been set in place, and the stigma attached to illegitimate births has weakened. As a consequence, the number of orphaned or abandoned children in those countries has fallen, and the number of domestic adoptions has risen. Furthermore, an increasing number of sending countries have ratified the Hague Convention, which states that it is preferable, in the best interests of the children, that they be adopted by family friends or relatives or, failing that, by fellow citizens, since intercountry adoption should only be a last resort. Following ratification, a large number of countries have drastically restricted the number of intercountry adoptions so as to prevent child trafficking and, more generally, promote children's interests. Consequently, the scarcity of adoptable children observed in France and Italy is also affecting other countries, especially since 2011 (Mignot, 2015b). This decline in the number of minors available for intercountry adoption has enabled China, for example, to stipulate that persons wishing to adopt Chinese children must be married heterosexual couples who have both completed secondary education, are in work and are not morbidly obese. Similarly in Brazil, the recent development of domestic adoption means that the only children left available for intercountry adoption are those with "special needs", i.e. older children, with siblings and/or with health problems or disabilities. The longer-term retrospective data (which cannot be used to describe recent years) provide information on the period when intercountry adoptions gradually took over from domestic ones (Figure 5; for France see [START_REF] Denéchère | Des enfants venus de loin[END_REF]. Until the late 1980s, the proportion of intercountry adoptions was probably higher in France than Italy, but from the early 1990s to the early 2010s, they accounted for around two-thirds of all adoptions in both countries. However, since the early 2010s, the number of intercountry (full) adoptions of minors in France and Italy has fallen (observable in Figure 4, but not in Figure 5, which is based on different data) and the number of adoptable domestic minors has plateaued for full adoptions in France and Italy (Figure 3). As a result, the proportion of full adoptions of foreign nationals each year has declined in recent years, from two-thirds to barely one half of the total. Overall, therefore, the two countries have had similar trajectories, at least since the 1980s. One major reason for this is that French and Italian potential adopters are faced not only with a dearth of domestic adoptable minors but also a falling number of foreign adoptable minors (Mignot, 2015b).

c. Characteristics of intercountry full adoptions

Since the 2000s, the characteristics of French and Italian intercountry adopters have been similar: most of them are married couples aged around 40, with above-average educational attainment, and who are either sterile or infertile. Of some 350 Italian families (non-representative sample) with at least one child aged 7-11, it has been shown that those including intercountry adoptees have certain distinct additional characteristics: adoptive parents enjoy a better than average quality of relationship, have more friends and display a higher level of psychosocial well-being than non-adoptive parents (Rosnati et al., 2013). The major difference between French and Italian intercountry adopters is that some of the French adopters are single persons, whereas for legal reasons all Italian adopters are married couples.

Since the early 2000s, just under 50% of intercountry adoptees in France have been boys [START_REF] Halifax | L'adoption en France : qui sont les adoptés, qui sont les adoptants ?[END_REF]; Ministère des Affaires étrangères, 2014), while in Italy the proportion is 55-61% [START_REF] Istituto | Come cambia l'adozione internazionale in Italia. Le coppie e i bambini nel monitoraggio della Commissione per le adozioni internazionali negli anni 2000-2007[END_REF]. This over-representation of boys in full adoptions in Italy is probably due less to the preferences of Italian adopters (who are not allowed to express a gender preference) than to the high number of boys among adoptable minors in the countries they tend to adopt from. Italians adopt in particular from Russia and Ukraine, which mainly give up boys for intercountry adoption. Of minors adopted from Russia by French nationals between 2003 and 2013, 60-66% were boys [START_REF] Halifax | L'adoption en France : qui sont les adoptés, qui sont les adoptants ?[END_REF]; Ministère des Affaires étrangères, 2014). The balanced sex ratio of intercountry adoptions in France can thus be explained by the fact that French adopters tend to adopt both from countries that more often give up boys to intercountry adoption and from countries that more often give up girls. Among minors adopted from China and Vietnam by French nationals from 2003 to 2013, for example, the proportion of boys ranged between 2% and 47% [START_REF] Halifax | L'adoption en France : qui sont les adoptés, qui sont les adoptants ?[END_REF]; Ministère des Affaires étrangères, 2014).

Since the early 2000s, the age of children adopted internationally has tended to increase in both France and Italy. The proportion of intercountry adoptees aged under 5 at the time of adoption in France fell from 82% in 2004 to 67% in 2013, and in Italy from 64% in 2000 to 47% in 2013. The main reason for this is the same in both countries: in line with the Hague Convention, the minors' home countries tend only to give up for intercountry adoption those children who are less easily adoptable by fellow citizens, in particular older children. In other words, as domestic adoption develops in the traditional sending countries of intercountry adoptees, the only minors available for intercountry adoption are older. Age is not the only personal characteristic that makes a minor less adoptable: if the minor is inseparable from siblings, or has a health problem or a physical or mental disability, this also reduces their chances of being adopted. Indeed, since the latter half of the 2000s, somewhere between one-half and two-thirds of intercountry adoptees in France and Italy have been children "with special needs", i.e. older, with siblings or a disability. It is clear that Western potential adopters are now competing with potential adopters in the home countries for the most desired minors, namely healthy newborns.

Last, since the 2000s, French and Italian potential adopters have been attracted to slightly different sets of countries [START_REF] Peter | Global Trends in Intercountry Adoption: 2001-2010[END_REF]. French nationals adopt mainly from Asia (China and Vietnam until the latter signed the Hague Convention in 2011), Latin America (Colombia, Haiti) and Africa (Ethiopia, Madagascar) and only very recently from Europe (Russia), while Italians adopt mainly from Europe (Russia, Ukraine, Bulgaria, Belarus, Poland) and only to a lesser extent from Latin America (Colombia, Brazil) and Africa (Ethiopia).

The reasons for this are not clear. First, the fact that Italy signed a bilateral adoption agreement with Russia in 2008 might account for some of the overrepresentation of Russian adoptees in Italy. But that would only explain the period since then. Second, some of the overrepresentation in France of adoptees from French-speaking countries can be explained by the preference of potential adopters for countries where some people speak their language, such as Vietnam, Haiti or Madagascar. In more general terms, the greater diversity of origins of intercountry adoptees in France may be due to the importance of adoption in French foreign policy, with the government authorizing adoption bodies to contact a large number of different countries. And the relative rarity of Chinese adoptees in Italy may stem from the fact that Italian potential adopters are not allowed to make individual approaches to a country of their choice (they may only adopt from a country where an authorized Italian adoption body is represented), a limitation which may prevent them adopting from countries which are open to French adopters. Under the Italian intercountry adoption procedure, once the couple have been approved, they mandate an authorized adoption body (ente autorizzato) to implement the procedure abroad until a match is found. More generally, it may well be that Italian adopters place a higher value than French ones on adopting white children, who may pass for their own children if they were not too old when adopted. However, there are not sufficient data to confirm this (concerning the construction of ethnic and national identity among intercountry adoptees in Italy, see [START_REF] Ferrari Laura | Internationally Adopted Adolescents: How Do They Integrate Ethnic and National Identity?[END_REF][START_REF] Rosa | Parental Cultural Socialization and Perception of Discrimination As Antecedents For Transracial Adoptees' Ethnic Identity[END_REF]. At all events, it is clear that the differences between France and Italy in the home countries of intercountry adoptees affect the adoptees' characteristics: the countries that Italians adopt from explain why they adopt more boys and more older minors than the French.

Conclusion

From this comparison of adoption in France and Italy since the nineteenth century we may draw a number of conclusions. First, the histories of adoption law in France and Italy are quite similar, and their laws on simple and full adoption still have many points in common. While it is no surprise that the number of simple adoptions followed similar trends in the two countries from the late nineteenth century to the mid-1970s, it is striking that since that date the number of simple adoptions has remained very low in Italy but has boomed in France. This divergence in the practice of simple adoption mainly reveals the gap that has opened up between France and Italy in divorce rates: each year in France close to 10,000 step-parents, mostly with no children, adopt their step-children in order to pass on their estate, whereas in Italy the small number of stepfamilies makes this much less frequent.

Regarding full adoption, since both French and Italian potential adopters are faced with a low number of adoptable minors in their own countries, they have been obliged since the 1970s, first in France and then in Italy, to adopt children from abroad. Since 2011, however, the number of intercountry adoptions has fallen in both countries as a result of sociodemographic, political and legal developments that have reduced the number of minors available. Consequently intercountry adoptees in France and Italy tend to be older, more often with siblings and more often with health problems or a disability than before. Potential adopters, particularly sterile couples, may therefore seek in future to circumvent the shortage of adoptable minors by making greater use of surrogate motherhood, even if this is illegal in both Italy and France.

With regard to both full and simple adoption, it would also be of interest to compare the characteristics of adoptees and adopters in Italy and France over a longer period. But this would require an Italian data sourceyet to be foundequivalent to that of the Compte général. Analyses of this sort, which could be done for other countries, such as Spain and Germany, would certainly throw new light on the history of adoption law and practice in western countries, and more generally, on their demographic histories. A comparison of the effects of adoption on the health and well-being of adoptees in France and Italy is also needed, since the studies currently available in France (Halifax, 2001;[START_REF] Halifax | Étude relative au devenir des enfants adoptés en France et à l'international[END_REF] and Italy [START_REF] Marco | La famiglia adottiva. Come accompagnarla e sostenerla[END_REF][START_REF] Rosa | Il legame adottivo. Contributi internazionali per la ricerca e l'intervento[END_REF][START_REF] Segatto | The Recovery Function of Adoption. A Study Carried Out in the Italy's Veneto Region[END_REF] were conducted independently and did not not use directly comparable methodologies.

  France and Italy have ratified the Hague Convention on Protection of Children and Co-operation in Respect of Intercountry Adoption and have modified their laws on domestic and intercountry adoption as a result. The Convention came into force in France in 1998 and in Italy in 2000 (The Hague Conference on Private International Law, 2014).

Figure 1 .

 1 Figure 1. Annual number of simple adoptions in France and Italy, 1841-2007

  personnelle de la Direction générale de la statistique du Ministère de la Justice italien. (b) Champs : en France, ce sont les adoptés simples dont le jugement d'adoption a été prononcé par un tribunal de première instance / grande instance, par année de jugement d'adoption (données annuelles de 1841 à 1980, et données ponctuelles en 1992 et 2007) ; en Italie, ce sont les adoptions simples (adozioni ordinarie), par année de jugement d'adoption (données annuelles de 1891 à 1983, données indisponibles depuis 1984).

Figure 2 .

 2 Figure 2. Annual number of full adoptions in France and Italy, 1952-2008

Figure 3 .

 3 Figure 3. Total numbers of domestic minors available for full adoption in France andItaly, 1991-2012

Figure 4 .

 4 Figure 4. Number of intercountry adoptions of minors in France and Italy, 1991-2014

Figure 5 .

 5 Figure 5. Foreign minors as a proportion of all full adoptions in France and Italy, 1967-2008

Tableau 1. Le droit de l'adoption en France et en Italie en 2014 France Italie

			France	Italie
			Adoption simple Adoption simple	Adoption plénière Adoption plénière France mais seulement transcrit	Adoption simple (adozione Adoption simple (adozione di persone maggiori d'età) di persone maggiori d'età)	Adoption plénière Adoption plénière (adozione dei minori) (adozione dei minori)
	Les conditions que Les effets juridiques de l'adoption doivent remplir les adoptés	Âge et statut matrimonial Perte de lien de filiation Droit de la filiation Consentement Droit social	Avoir au moins 15 ans de moins que l'adoptant -L'adopté conserve ses droits et devoirs dans sa famille d'origine mais il prend le nom de l'adoptant et il lui succède (à lui et à sa famille) comme un enfant légitime. L'adoption est révocable sur décision judiciaire pour motifs graves Consentement nécessaire si l'adopté a plus de 15 ans	Avoir moins de 15 ans, et avoir au moins 15 ans de moins que l'adoptant Être sans famille (« pupille de l'État » ou déclaré abandonné par jugement du tribunal), ou avoir été expressément consenti à L'adoptant et l'adopté ont le même lien de filiation qu'un parent et son enfant légitime. L'adoption est irrévocable l'adoption par ses parents Les adoptants bénéficient des Consentement nécessaire si l'adopté a plus de 13 ans mêmes prestations que suite à une naissance	Avoir plus de 18 ans, pas déjà adopté, avoir au moins 18 ans de moins que l'adoptant et ne pas être son enfant né hors mariage -L'adopté conserve ses droits et devoirs dans sa famille d'origine mais il prend le nom de l'adoptant et il lui succède (à lui seul, pas à sa famille) comme un enfant légitime. L'adoption est révocable en cas d'indignité de l'adoptant envers l'adopté ou de l'adopté envers l'adoptant Consentement nécessaire	Avoir moins de 18 ans, avoir entre 18 et 45 ans de moins que l'adoptant (exceptions permises) et ne pas être son enfant né hors mariage Être sans famille et avoir été déclaré adoptable par le tribunal (dichiarazione di adottabilità) L'adoptant et l'adopté ont le même lien de filiation qu'un parent et son enfant légitime. L'adoption est irrévocable Les adoptants bénéficient des Consentement nécessaire si mêmes prestations que suite à une l'adopté a plus de 14 ans naissance
		Durée de
		placement dans la future		Au moins 6 mois		Au moins 1 an (affidamento preadottivo)
		famille
	Les conditions que	Âge et statut matrimonial	Avoir plus de 28 ans, ou être un couple marié depuis plus de 2 ans ou dont les deux membres ont plus de 28 ans	Avoir au moins 35 ans (sauf exceptions) et être sans enfant légitime ou légitimé	Être des époux majeurs de 18 ans, mariés depuis au moins 3 ans (durée de cohabitation avant mariage incluse), non séparés et
	doivent					capables d'élever des mineurs
	remplir les adoptants	Agrément		Nécessaire, il est accordé par le service départemental de l'Aide sociale à l'enfance pour cinq ans		Nécessaire, il est accordé par le tribunal des mineurs pour trois ans
				L'Aide sociale à l'enfance, qui
		Administrative		recueille les mineurs adoptables, apparente le mineur adoptable et
	La procédure d'adoption	Judiciaire	Le jugement d'adoption est prononcé par un tribunal (tribunal de grande instance)	son adoptant Le jugement d'adoption est prononcé par un tribunal (tribunal de grande instance) ou, s'il est prononcé par un pays étranger reconnaissant l'adoption plénière,	Le jugement d'adoption est prononcé par un tribunal (tribunale civile)	Le jugement d'adoption (dichiarazione di adozione) est prononcé par un tribunal (tribunale per i minorenni)
				il n'a pas à être prononcé en



  VILLENEUVE-GOKALP Catherine, 2011, « Les femmes qui accouchent sous le secret en France, 2007-2009 », Population, 1, p. 135-169.  VOISIN Joëlle, GEORGES Philippe, 2011, Audit du fonctionnement du conseil national d'accès aux origines personnelles (CNAOP). Rapport définitif, Paris, IGAS.  WEIL R.H., 1984, « International Adoptions: The Quiet Migration », International Migration Review, 18, p. 276-293.

In Italy, adoption is subject to a legal framework distinct from "affiliation" (affiliazione), which existed in Italian law from 1939 to 1983. Affiliation transferred paternal authority to the affiliator and allowed the affiliatee to enjoy maintenance entitlements until they reached the age of majority and even to take on the affiliator's surname. However, affiliation did not create a parent-child relationship: the affiliatee did not inherit from the affiliator. The number of affiliations in Italy fell from nearly

2,500 a year in 1955 to fewer than 500 in 1979[START_REF] Brand | Adoption -Italie[END_REF].

2 I wish to thank Francesca Caroccia and Paola Ronfani for their invaluable comments on earlier versions of this article. I also thank Matteo Sgarzi for his help and the Direzione Generale di Statistica at the Ministero della Giustizia for agreeing to provide me with their recent data on simple adoption.