Mohamed Ali

Ben Halima
email: benhalima@gate.cnrs.fr

EXIT FROM SHORT-TERM CONTRACT A FRENCH EMPIRICAL ANALYSIS, 1990-2002

Keywords: Short-Term Contracts, Duration model, Competing risk hazard model Classification JEL : J41, J24, C10, C41 Contrats de travail temporaire, Modèle de durée, Modèle à risque concurrent

This paper tests the determinants of the transition out of short-term contracts by means of competing risk form of the semi-parametric Cox proportional hazard model. We use three labour market states distinguishing between exit into long-term contract, another short-term contract, and unemployment. For each type of exit, we define a separate hazard function that we'll call a type-specific hazard. The estimates are carried out from a dataset recording individual labour market histories, the French Labour Force Survey (LFS) collected by the French National Statistical Institute (INSEE). The competing risk model is estimated for all the individual as well as separately for men and women. Our results show that, for men and women, the conditional probability of exiting STC into LTC decreases after 12 th months. Moreover, staying in the same firm after a STC increases the chances of getting stable jobs in the future.

INTRODUCTION

The type of labour contracts was a basic matter of discussion during the last decades, especially in the developed countries. Whereas, the short-term contracts had been the dominate pattern in this major. Accordingly, the European advanced importance in this point, and especially the France one, had pushed us to take it as a real case of study in our research.

Recent studies had focused on short-term contracts, which considerably the preferable choice for the employers decision-taking, due to its restrictions flexibility which also could increase the economic mobility and reduce inequalities between unemployers and employers and wouldn't create a dual labour market, which is described in the literature [START_REF] Hunt | Firing Costs, Employment Fluctuations and Average Employment: An Examination of Germany[END_REF][START_REF] Maurin | The European Paradox : Do Flexible Contracts Create Rigid Labor Markets?[END_REF]. However, employers prefer the short-term contracts in their recruitment strategies due to a lot of reasons. First, costs reason, due to which the temporary contracts are less costly on them with respect to the permanent ones [START_REF] Bentolila | Firing costs and labour demand: how bad is Eurosclerosis[END_REF][START_REF] Bentolila | A model of labour demand with linear adjustment costs[END_REF][START_REF] Booth | An analysis of firing costs and their implications for unemployment policy[END_REF]. Second, where as the short-term contracts have a high flexibility in filling the job's vacancies. Third, absorption-tendency for the demand fluctuations adjustment's costs. Fourth, reducing uncertainty in matching value.

Whereas, the matching theory, that had been suggested by Jovanovic (1979), constitutes the model of reference integrating this dimension of the labour market. Moreover, they added that it is necessary to install a mechanism making it possible to produce an optimal pairing in order to reach an efficient production. In fact, the Firms current strategies are to ease initially short-term contracts as a probationary stage. Then, according to the applicant abilities and labour demand, long-term contracts would be proposed. Furthermore, as pointed out by [START_REF] Loh | Employment Probation as a Sorting Mechanism[END_REF], and [START_REF] Lazear | Hiring Risky Workers[END_REF] probationary periods may induce self-selection of those workers with higher ability because they have a higher probability to obtain permanent contracts.

Thus, we'll try focus in this study short-terms contracts effects. We'll take the mission of illustrating the "stepping stone" principle or arriving to a new methodology. Moreover, to what extent does a short-term contract (STC) increase the probability of finding a long-term contract (LTC)?

Existing theory suggests different answer to this question. On the one hand, Booth et al. (2002b) examined whether temporary contracts deserve to be considered as ''stepping stones.'' The authors confirm for their United Kingdom sample that over a period of 7 years, about 38% of all workers observed on short-term contracts move on to permanent employment after the STC expires with higher wages and fringe benefits. They also show that high effort among temporary workers is positively correlated with the probability of career advancement. On the other hand, the "dead-end" suggestions had been presented in the discussion table, where [START_REF] Güell | Worker transitions from temporary to Permanent employment: the case of Spain[END_REF] were the most believers on "dead-end" in studying the duration pattern of short-term contracts in Spain and the determinants of their conversion into permanent ones. D' Addio and Rosholm (2005) study transitions out of temporary jobs using the waves 1994-1999 of the European Community Household Panel.

The authors confirm that very short contracts provide higher chances of labour market exclusion especially for men. While, the empirical works available for Italy [START_REF] Adam | Partial De-Regulation: Fixed-Term Contracts in Italy and Spain» CEP Discussion Papers from Centre for Economic Performance[END_REF], France [START_REF] Abowd | he Entry and Exit of Workers and the Growth of Employment: An Analysis of French Establishments[END_REF], and Germany [START_REF] Hagen | Do fixed term contracts increase the long-term employment opportunities of the unemployed?[END_REF] all indicate that short-term contracts are stepping stones to permanent forms of employment rather than dead-end jobs.

The structure of the article is organized as follows. In the next section we present the French legislation of short-term contracts. In the section 3, we highlight the econometric problems encountered to test the determinants of the exit of short-term contracts. Section 4 describes the French Labor Force Survey, Enquête Emploi, collected by the French National Statistical Institute (INSEE). Section 5 shows a nonparametric analysis of the hazard functions for men and women, into long-term contract, short-term contract and unemployment by the method of Kaplan-Meir. Section 6 shows the econometric results from the estimate of the competing risk model for all the individual as well as separately for men and women.

Finally, a synthesis of the main results is given as a conclusion.

The French Regulation of Short-Term Contracts

French labor laws1 allow firms to hire workers on two types of regular employment contracts: Indefinite-Term Contracts (Contrats à Durée Indéterminée, CDI) and Fixed-Term Contracts (Contrats à Durée Déterminée, CDD). The current architecture of CDDs, introduced in 1979, dates back to an agreement signed in March 1990. Under this agreement, CDDs can be offered by firms for only very precise reasons: CDD cannot be used to fill a job that would exist under normal and permanent business conditions for a given firm (Article L.122).

The use of fixed term employment contracts is covered by the detailed employment legislation set out in the code du travail. This specifies the situations in which employers may use fixed term contracts and places tight restrictions on their duration and renewal. The french government has made clear its view that employers should not make excessive use of fixed term contracts, particularly short-term contracts, which have been cited as a key factor in the development of social exclusion.

Fixed term contracts can be used in five different situations: to replace absent employees; if a company grows temporarily and needs extra employees for a limited period of time; for seasonal work; to fill a vacant post until a permanent employee starts the job; and in specified jobs and sectors where permanent contracts are not appropriate.

A short-term contract must be in writing, otherwise it will be judged to be a permanent contract. It must state the reason for a fixed term contract being concluded, which must correspond to the reasons outlined above. It must state the duration of the contract, which may be either for a fixed length of time or until a specified event happens (including the completion of one or more tasks). The contract may not be broken before this finishing point unless both the employer and employee agree to it.

Generally, successive fixed term contracts may last no longer than 18 months in total, and a fixed term contract cannot be renewed more than twice in this time. However, fixed term contracts concluded for urgent safety work may not last longer than nine months. There must be a gap between successive contracts that is at least a third as long as the contract it follows, for example an employee on a nine month fixed term contract must be laid off for three months before being hired on another fixed term contract by the same employer. Fixed term employees must receive the same legal, contractual and collective rights as comparable permanent employees. At the end of a fixed term contract, employees generally receive a payment worth at least 6% (10% since January 2002) of their total gross earnings during the period covered by the contract and compensation for any paid annual leave not taken.

Although their use is formally restricted, CDDs are the most common method of hiring. For example, in 1990, 58% of all hires were through CDD, they were 68% in 1996 and 75% in 1999 [START_REF] Coutrot | Les Facteurs de Recours Aux Contrats Temporaires[END_REF]). On the other hand, during the 1990's, more than 90% of the stock of employees in private for-profit or semi-public establishments were on CDIs. For those hired under CDD approximately one in three is eventually converted to CDI [START_REF] Abowd | he Entry and Exit of Workers and the Growth of Employment: An Analysis of French Establishments[END_REF]).

The econometric model

In our analysis, we develop a competing risk form of the semi-parametric Cox proportional hazard model (see [START_REF] Cox | Exits from temporary jobs in Europe: A competing risks analysis[END_REF]. This type of model allows controlling for all the standard determinants, as well as for duration dependence, which is the pure effect of time spent in temporary employment on the probability of moving to another state. For each type of exit, we are going to define a separate hazard function that we'll call a typespecific or cause-specific hazard.

The hazard model utilizes data on the sequence, timing, and the state in which an individual occupies; the probability of the type of exit is a function of time. This is referred to as the hazard rate or function. The hazard rate is the dependent variable, and the relationship between this rate and a variety of observed and unobserved variables is modelled. The hazard model has been widely used in biomedical and social science research, by [START_REF] Cox | Regression models and life tables[END_REF], Kalbfleish and Prentice (1980), Heckman and[START_REF] Heckman | A Method of Minimizing the Distributional Impact in Econometric Models for Duration Data[END_REF][START_REF] Kiefer | Economic duration data and hazard functions[END_REF].

We will distinguish three labor market states: long-term contract in private and public establishments (state 1), short-term contract, including fixed-term contract, intermediaries and seasonal workers (state 2) and unemployment (state 3). For each type of exit, we are going to define a separate hazard function that we'll call a type-specific or cause-specific hazard.

As before let Ti be a nonnegative random variable denoting the length of short-term contract for individual i. In the competing risk model the choice set is specified by a discretestate space and the choice and switching between labor market states are formalized through transition rates, while the time spent on activities is estimated by a distribution function (see, Flinn and[START_REF] Heckman | Models for the analysis of labour force dynamics[END_REF][START_REF] Heckman | A Method of Minimizing the Distributional Impact in Econometric Models for Duration Data[END_REF]. Let ki be a random variable denoting the type of exit that occurred to individual i. We now define ( ) t h ik , the hazard for death type k at time t for individual i, as follows:

( ) { } 3 , 2 , 1 , / , Pr lim 0 = ∆ ≥ = ∆ + ≤ ≤ = → ∆ k t t T j J t t T t t h i i i t ik
Thus, the conditional probability in this equation, is the probability that individual exit occurs between t and t t ∆ + , and the exit is of type k, given that the person had not already died by time t. The overall hazard of exiting is just the sum of all the type-specific hazards, that is,

( ) ( ) ∑ = k ik i t h t h
You can interpret type-specific hazards in much the same way as ordinary hazards. Their metric is the number of events per unit interval of time, except now the events are of a specific type. Based on the type-specific hazards we can also define type-specific survival function:

( ) ( )       - = ∫ t k k du u h t S 0 exp
In order to estimate the transition rates of short-term contract and the effects of independent variables on these, we need to specify the functional form of the hazard model.

The most widely used specifications are the accelerated time model and the Cox proportional hazard model. According to the Cox proportional hazard model [START_REF] Cox | Regression models and life tables[END_REF] , covariates have a multiplicative relationship with the hazard function (the proportionality assumption), causing them to shift the hazard function up or downward. Therefore, covariates do not have a direct impact on the duration of an activity. In contrast, the accelerated time model (Cox and Oakes 1984) assumes that covariates act multiplicative on time rather than on the hazard function. Covariates, therefore, increase or decrease the time spent on an activity.

As the current paper studies the impact of explanatory variables on the exit of shortterm contract, Cox proportional hazard model is used. The competing risk accelerated time model is specified as follows:

( ) ( ) k i i k i k x t h X t h β - = exp ) (
) ( ) ∏ ≠ = r k r ir i r k ik i k i X t S X t f L β β , ,
where the subscript k denotes the kth event and r in the product term implies that the product is taken over the survivor times for all states except k. The joint density for the probability density function and survivor function for all activities are obtained by integrating ( )

t h k .
The overall likelihood function for the full sample is then given by ( ) ( )

k ik i k n i r k k ik i k X t S X t f L β β , , 1 1 ∏∏ = = =
This partitioning is easier to see if we define a censoring indicator such that:

   = otherwise 0 to due failed if 1 k i ik δ when 1 = i δ the observation is observed failing due to risk k ; when 0 = i δ
, the observation is right-censored. Incorporating ik δ into the likelihood function, the likelihood of the sampled duration times may be expressed as

( ) ( ) ik k ik i k n i r k k ik i k X t S X t f L δ δ β β - = = ∏∏ = 1 1 1 , , ik
Importantly, for this model, the assumption must be made that the K risks are conditionally independent. Given the covariates, the survival times for risk k are independent of the survival times for risk r.

Data

In this instance, we use a longitudinal micro dataset recording individual labor market histories, the French Labor Force Survey (hereafter: LFS), Enquête Emploi, collected by the French National Statistical Institute (INSEE). We consider the cohorts that were sampled from 1990 to 2002. The households in the cohorts are interviewed in March of three consecutive years. The survey is representative of the French population aged 15 and up. The sampling fraction is approximately 1/300. Large samples of about 150,000 individuals aged 15 or more, in 75,000 households, can thus be interviewed three times, in March of three subsequent years, about various aspects of their employment histories.

At each interview date, each individual is asked to describe her actual labor market state, and is also asked to provide some retrospective information on her labor market history. We had to distinguish this a complete trajectories ( )

Concentrate for example on individuals interviewed in

2 1 , , + + t t t y y y
, where t is the date of the first recorded observation. For the estimation of the empirical model, the sample is restricted to individuals responding three consecutive waves and individuals who still in the short-term contract at t, that means to households entering the survey between 1991 and 2000.

Households that are not interviewed three times generate incomplete labor market histories2 .

Excluding such households from the cohort does not bias our results under the assumption that non-participation phenomenon (panel attrition) is exogenous.

An overview of Short-Term Contract in French

The Aggregate Picture

In studying the evolution of the short-term contract proportions with respect to the total French employment contracts (Figure 1), a gradual increase for the benefit of the shortterm contracts had effectively appeared between 1990 to 2000 (2.86% to 6.67%). Otherwise, the new millennium were considerable the pick of the percentage of the short-term contract.

Figure 2 shows the share of short-term contract in total employment according to the variable of sex. Although the share of STCs in total employment increases for both men and women. Generally, the share of women in short-term contract is higher than of men especially in the years between 1990 and to 2000. After 2000 the share of short-term contract continued to decline marginally and in 2002 it reached 6.6% for women and 6.3% for men. The occurrence of this type of employment have peaked in 2000 at 7.06% for women and 6.62% for men.

Figure 3 shows that the share of short-term contract in total employment is more frequent in some age groups than in others. We note that there is a greater proportion of shortterm contract among youth [15][16][17][18][19][20][21][22][23][24] with respect to the old ages [50-59], whereas, the graph shows an increase in the gap difference from (5. 09% in 1990 to 8.53% in 2002). Thus, normally we can conclude that the short-term contract are also more related to the first working step for the employers way, while the increase in the age-group gap could be related to the experience level.

An analysis of the share of short-term contract in total employment by four sectors confirms the development of the short-term contract in particular sectors of economy. Figure 4 shows that the share of STC's is roughly increasing in all sectors during the 90's. While the biggest occupations specifically STC's are found among service and construction sectors.

Since 1993, the share of STC's in total employment increased sharply in service sectors.

While in 1993, 5.55% of STC's were active in the service sector, by 2000 this percentage has increased to 11.73%. We should note, however, that the construction and services sector still accounts for large part of all short-term contracts in the labour market. In this is related to the kind of the services working structure and the seasonable activities.

By looking at the activity rate for our sample of workers for the period from the 1990 to 2002, tow facts are immediately evident (see table 1). The first one is that working as employee with a long-term contract remains by far the most important form of employment but it continues to decrease during the period. This decrease is reflected in the corresponding increase in the percentage of short-term contracts and unemployment, while the percentage of those who are in education or job training remains roughly constant during the same period.

The second fact is that working as an employee with a short-term contract remains by far the smallest form of employment but it continues to increase by approximately four percentage points. However, the share of short-term contract in total employment has increased from 3.95% in 1990 to 8.72% in 2002. When looking at the average annual growth in long-term and short-term contract concerning the period from 1990 to 2002, fluctuations in short-term contract over all periods are much more developed than for long-term contract.

Table 2 shows one-year transition of short-term contract between the six labour market statuses in consideration for the period 1990 to 2002. It is interesting to point out when comparing the mid-1990 to the beginning of 2000. During the 90/91, around 35% of workers on a short-term contract are still in the same status one year later, with 38% of them managing to obtain a more stable form of employment but around 15% of them are not employed.

Approximately 2% of these STC are still in education or training one year later. Looking in more details at the transition between 2001 and 2002, there is a high degree of persistence for people under short-term contract: around 57% of individuals are still in the same situation of labor contract one year later, but only 22% of STC stepping-stones with a long-term contract.

During the period from 1990 to 2002, the proportion of short-term contract that led to with a long-term contract has decreased and at the same time, the share of short-term contract that led with a new STC has increased monotonically.

Table 3 shows the percentage of transition between different economic activity statuses differ according to the personal characteristics of the individuals. Looking at the gender dimension, the share for men on short-term contracts to move to long-term contracts is around tow percentage points higher than for women. This suggests that men having a temporary job are more likely to obtain a stable employment, while for women, this is more likely to represent a period of work in a rather more intermittent career path. Considering the different age group, it should be noted that the lowest degree of transition in long-term contracts (20.43%) is for those aged 16-24. Since the majority of young people have no professional experience on the labour market, they accept even short-term contract (61.29%).

The workers aged between [40][41][42][43][44][45][46][47][48][49], represent the highest percentage in the transition towards the long-term contract. The analysis of transition by levels of qualification highlights once more the importance of education for labour market outcomes. The percentage of temporary workers to move to long-term contract increases with the level of qualification, from 20.28%

for the low-qualified to 31.85% for the high qualified. Also, regardless of the economic activity statuses, the percentage that workers loosing or leaving their job decreases with level of qualifications of the individual.

The hazard function into Long-term and Short-term contract:

We have represented graphically in Figure 5, Figure 6 and Figure 7, the hazard functions for men and women, into long-term contract, short-term contract and unemployment.

We notice that both of them are non-monotonic. When considering the conditional probability of exiting STC into LTC, we note that for men and women it decreases after 12 th months. The analysis of hazard ratio confirms, men as well as for women, that short duration of STC increases significantly their chances to reach job stability through LTC.

The hazard rate measuring the conditional probability of exiting STC to another STC, reported in the Figure 6 shows that women with longer short-term contracts are more likely to get another STC. The hazard rates into STC clearly confirm this situation, by suggesting that temporary jobs have the same effects for men and women respectively. Transition rate into unemployment (Figure 7) is decreasing after the first year for both men and women.

We should ask the following question does the fact of obtaining a LTC after a STC related to the fact of staying in the same firm in another word does the fact of moving to another firm increase or decrease the probability of exiting in a LTC?

The hazard function is decreasing whatever the type of firms of transition. One can compare hazard in long-term contract (Figure 8) for the two types of firms (transition in the same firm; transition to another firm). The hazard function into LTC of the individuals with transition in the same firm is always higher that of the individuals with transition to another firm. The probability of exiting to STC in the same firm (Figure 9) is higher than that of obtaining STC in another firm until the 12 th month. But afterwards, two hazard functions are decreasing monotonically. This can be explained by the fact that STC is a probationary period in the first year to test the individual's skills. Then, according to the applicant abilities and labour demand, long-term contracts would be proposed.

Results of estimation

The estimation results of the competing risk model out of short-term contracts confirm what has been observed by descriptive statistics. Related to transitions into LTC, we notice that the age, the human capital, the labour market conditions (modelled here through the unemployment rate), being occupied in some kind of elementary tasks, sector of activity, and finally the private/public type of employment, affect the hazard rate of men and women in the same way.

6.1

Results for the whole set of the individuals Table 4 report our results for the determinants of transitions probability from shortterm contract to three economic activity statuses for the period 1990 to 2002.

First, younger workers aged between 16-24 relative to the base of individuals aged between 40-49 have a low probability of finding a long-term contract. Older workers aged between 50-59 have also a higher risk of exclusion from the labour market after a short-term contract. Since the majority of young people have no professional experience on the labour market, they accept even precarious working conditions. This result is confirmed by Booth, Francesconi and Frank (2002a) on English data.

Men have a negative and significant probability of getting another short-term contract or exit into unemployment. The chances of having an established position under long-term contract are higher for Europeans than for non-European people.

The results show that workers with low human capital with technical education hold more long-term contract than the workers with first cycle degree. The result found suggests that when short-term contract are held by individuals with high skilled (university degree), this is not an efficient way to get promoted into the labour market, but a powerful tool to put them out of the labour market. It is clear from the results associated with the exit into unemployment that those holding high skilled positions have lower risks of facing exclusion after the experience of a short-term contract.

Occupational levels variables indicate that executives or professionals have a positive and significant probability to transitions into long-term contract relative to workmen. On the other hand, holding a short-term contract with intermediary professions reduces the probability of finding a long-term contract.

Exit from short-term contract varies according to the size of firms. Compared to small firms, workers in firms with 50 to 499 employees can also worsen the chances of getting stable jobs in the future.

Having temporary jobs in the public sector is associated with an increased risk of becoming non-employed. The negative sign associated with this variable in the transition into long-term contract points at the risk of such a practice. After a short-term contract in the public sector (compared to private), workers are more likely to fall again into unemployment or short-term contract.

Transitions probability between different economic activity statuses differ according to the experience in labour market. The probability of holding a long-term contract is greater when individuals have a less experience in short term contract. On the other hand, people on short-term contract with a professional experience in the labour market find difficulties of having an established position and their moving into unemployment.

The introduction of time work effects shows that full-time workers have a positive and significant probability to obtain an LTC compared to those in part-time.

Considering the type of short-term contract, it should be noted that the individuals under fixed-term contract have a higher probability of holding long-term contracts. Therefore, individuals under fixed-term contract improve their chances of stabilization in an employment position compared to people with seasonal or intermediaries contract.

The local rate of unemployment tends to increase the probability of transitions shortterm contract or unemployment. Persistence of unemployment obviously makes the recourse to this situation of employment much more frequent.

Results for men and for women

Table 5 and Table 6 report our results for the determinants of transition probability from short-term contract to three economic activity statuses for men and women alike.

Concerning the age, for men as well as for women, young people occupying an STC are more likely to obtain another STC. On the other hand, for older men of more than 50 years old, their age is an obstacle that leads them to unemployment.

The marital statute has the same significant and positive effect for men and women.

Indeed, being married has an effect of increasing the probability of having a LTC.

By examining the results of the variable of the level of education, it should be noted that we have a significant difference between men and women related to their types of exiting after a STC. Indeed, men with higher education have a positive and significant probability to hold LTC. On the other hand, women having the same level of education find difficulties to obtain an LTC. This same phenomenon is observed for workers with technical education (having a technical curriculum). The results show the latter hold more LTC while women encounter more difficulties in having an established position and their moving to another STC.

Women working in large firms have a higher probability of finding a long-term contract. On the other hand, men working in large firms have also higher risks of exclusion from the labour market after a short-term contract.

Working in the public sector under a short-term contract has the same effect on men and women alike. Both sexes find difficulties to move to an LTC.

The time of work (full-time / part-time) doesn't have a significant effect on the types of exiting from an STC for men. On the other hand, women having full-time jobs are more likely to obtain an LTC. It should be noted too, that women having a part time job plays a significant and negative effect on the probability of moving to an LTC and doesn't increase the probability of exiting to another STC or to unemployment.

As to the wages, they have the same positive and significant effect on the probability of transition towards an LTC for both men and women.

Results for type of firm transition

Table 7 and Table 8 report our results for the determinants of transition probability from short-term contract to long-term contract or another short-term contract statuses by type of firm transition (in the same firm / in another firm).

Men have a positive and significant probability of stepping-stones to another longterm contract in the same firm. The chances of having an established position under long-term contract after a short-term contract in the same firm are higher for married than for executives or professionals workers.

Transitions probability between different statuses differ according to the type of shortterm contract in labour market. The probability of holding a long-term contract is greater when individuals have a fixed-term contract and staying in the same firm. On the other hand, people staying in the same firm or moving to another firm, on intermediaries or seasonal contract find difficulties of having an established position and their exiting into short-term contract.

Conclusion

This paper test the determinants of the transition out of short-term contract. Moreover, does a short-term contract (STC) increase the probability of finding a long-term contract (LTC)? In our analysis, we develop a competing risk form of the semi-parametric Cox proportional hazard model This type of model allows controlling for all the standard determinants, as well as for duration dependence, which is the pure effect of time spent in temporary employment on the probability of moving to another state. We will distinguish three labour exiting: long-term contract in private and public establishments (state 1), shortterm contract, including fixed-term contract, intermediaries and seasonal workers (state 2) and unemployment (state 3). For each type of exit, we are going to define a separate hazard function that we'll call a type-specific or cause-specific hazard.

The estimates are carried out from a longitudinal micro dataset recording individual labour market histories, the French Labour Force Survey. We consider the cohorts that were sampled from 1990 to 2002.

When considering the hazard functions for exiting into LTC, we note that for men and women it decreases after 12 th months. The analysis of hazard ratio confirms, men as well as for women, that short duration of STC increases significantly their chances to reach job stability through LTC. One can compare hazard function in long-term contract for the two types of firms (transition in the same firm; transition to another firm), we noted that the hazard function into LTC of the individuals with transition in the same firm is always higher that of the individuals with transition to another firm.

The competing risk model is estimated for all the individual as well as separately for men and women. The estimation results confirm what has been observed by descriptive statistics. Related to transitions into LTC, we notice that the age, the human capital, the labour market conditions (modelled here through the unemployment rate), being occupied in some kind of elementary tasks, sector of activity, and finally the private/public type of employment, affect the hazard rate of men and women in the same way. 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000

  elapsed duration of short-term contract for individual i, ( ) exit k conditional on a vector of covariates, X; the effects of the time passed since the previous labour market state (STC) on the probability moving to another state k; and k k x β denotes the covariates and parameter estimates for exit-specific k.The overall likelihood function can be partitioned into the product of the k-specific likelihoods. To see this, suppose that there are n observations at risk of failing in one of k ways. The individual contribution of the ith individual failing by event k is given by

(

  March 2000. At the first interview, they are requested to retrace month by month, their labor market history between March 1999 and March 2000. At the second interview, they are request to recall (again month by month) the period between March 2000 and March 2001, and at the third interview, the period between March 2001 and March 2002. The following standard information is completed for each interview: sex, age, education, job tenure, industry, working hours, private and public sector.

Figure 1 :Figure 2 :Figure 3 :Figure 4 :

 1234 Figure 1: The share of Short-Term Contract in total employment[START_REF] Bentolila | Firing costs and labour demand: how bad is Eurosclerosis[END_REF]-2002 Sources: French Labour Force Surveys, 1990-2002.

Figure 5 :

 5 Figure 5: Transition to Long-Term Contract by genders

Figure 6 :

 6 Figure 6: Transition to Short-Term Contract by genders

Figure 7 :

 7 Figure 7: Transition to Unemployment by genders

Figure 8 :

 8 Figure 8: Transition to Long-Term Contract by firm

Figure 9 :

 9 Figure 9: Transition to Short-Term Contract by firm

Table 1 :

 1 Main activity status by year

  [START_REF] Güell | Worker transitions from temporary to Permanent employment: the case of Spain[END_REF] 2002 Long-Term Contracts 50.79 51.24 50.09 48.13 48.46 48.31 47.9 47.89 47.05 47.54 48.55 49.33 49.63

	Self-Employed	7.97 7.98 7.97 8.22 8.14 8.13 7.87 7.42 7.53 7.19 7.81 6.66 6.53
	Short-Term Contracts 3.95	3.9	4.41 5.07 5.17	6	5.94 6.22 6.82 7.54 7.59 7.71 8.72
	Unemployment	6.81 6.76 7.58 8.31 8.65 8.89 9.54 9.70 9.45 9.55 8.57 8.71 8.21
	Education / Training 15.55 15.49 15.57 15.74 15.84 16.13 16.54 16.62 16.66 16.56 15.83 15.74 15.43
	Out of Labour Force 14.93 14.63 14.38 13.54 13.74 12.54 12.21 12.15 12.49 11.62 11.65 11.85 11.48
	Sources: French Labour Force Surveys, 1990-2002.
		Table 2: One-year transitions by main economic status
			90/91 91/92 92/93 93/94 94/95 95/96 96/97 97/98 98/99 99/00 00/01 01/02
	To Long-Term Contracts	38.24 32.79 25.53 24.21 22.83 25.95 22.48 22.37 21.35 23.69 26.59 22.81
	To Self-Employed		0.83 0.51 0.27	1	1.09 0.64 0.32 0.85 0.62	0.4	0.4	0.54
	To Short-Term Contracts	35.88 48.88 49.12 51.96 56.68 52.02 56.76 56 57.16 56.01 55.17 57.97
	To Unemployment		15.91 10.89 12.77 12.84 9.85 11.72 10.40 10.41 12.19 9.52 9.22 10.28
	To Education / Training	2.85 1.85 7.80 7.23 5.98 6.41 6.79 7.56 6.72 7.91 6.99 6.79
	To Out of Labour Force	6.29 5.08 4.52 2.77 3.57 3.27 3.23	2.8	1.96 2.46 1.64 1.61

Sources: French Labour Force

Surveys, 1990Surveys, -2002. .

Table 3 :

 3 One year transitions by main economic status and by personal characteristics

		Long-Term	Short-Term	Unemployment Education	Out of Labour
		Contracts	Contracts		/ Training	Force
				Total
	1-year transition (t+1)	45.22	32.79	14.21	3.83	3.95
	2-yaer transition (t+2)	33.06	49.71	10.19	3.16	3.88
			By Personal Characteristics
	Male	25.26	53.49	10.64	6.48	4.13
	Female	23.49	56.36	10.87	7.17	2.11
	[16-24]	20.43	61.29	9.58	3.85	4.85
	[25-39]	26.55	57.37	10.01	3.48	2.59
	[40-49]	28.19	59.16	10.3	0.03	2.32
	[50-59]	27.12	58.16	12.37	0.03	2.32
	[60-64]	24.88	58.04	10.92	0.08	6.08
	Low qualified	20.28	55.21	13.69	7.66	3.16
	Medium qualified	24.57	54.48	11.01	6.66	3.28
	High qualified	31.85	52.67	6.45	6.21	2.82

Sources: French Labour Force

Surveys, 1990Surveys, -2002. .

Table 4 :

 4 Transition from Short-Term Contract Cox Competing Risk Model

		Transition to	Transition to	Transition to
		Long-Term Contract	Short-Term Contract	Unemployment
	AGE16-24	-0.1066**	(0.0563)	0.1733***	(0.0408) -0.0881	(0.0789)
	AGE25-39	-0.0672	(0.0469)	-0.0791**	(0.0329) -0.0230	(0.0681)
	AGE50-59	-0.1261	(0.0788)	-0.0523	(0.0525) 0.2497**	(0.1045)
	AGE60-64	-0.3236	(0.2712)	0.0187	(0.1439) 0.3551	(0.2855)
	Men	-0.0538	(0.0374)	-0.1767***	(0.0266) -0.2014***	(0.0543)
	European	0.4668*** (0.1362)	-0.0136	(0.0493) -0.1794**	(0.0840)
	Married	0.1474*** (0.0357)	-0.0761***	(0.0249) -0.0970	(0.0499)
	University degree	-0.0059	(0.0775)	0.1403***	(0.0537) -0.4468***	(0.1301)
	Bachelor degree	0.2219*** (0.0629)	0.1885***	(0.0473) -0.2185**	(0.0969)
	Technical Education	0.0834**	(0.0420)	0.0833***	(0.0305) -0.0366	(0.0559)
	General Education	0.0351	(0.0556)	0.1177***	(0.0395) -0.1047	(0.0771)
	Executive or Professional	0.5250*** (0.0890)	-0.2674***	(0.0611) -0.6651***	(0.1561)
	Intermediary Profession	-0.2615*** (0.0585)	-0.2087***	(0.0431) -0.3896***	(0.0882)
	Employee	-0.2012*** (0.0462)	-0.2192***	(0.0340) -0.1991***	(0.0642)
	Firm Size2: [50 , 99]	0.1382**	(0.0625)	0.0647	(0.0472) 0.1419	(0.0867)
	Firm Size3 : [100 , 499]	0.1940*** (0.0454)	0.1835***	(0.0323) 0.0271	(0.0675)
	Firm Size4 : [500 , +]	0.0697	(0.0430)	0.0153	(0.0304) 0.1530**	(0.0609)
	Public sector	-0.4567*** (0.0421)	0.2169**	(0.0987)	0.6610***	(0.0689)
	Experience1 : [0 , 1[	0.6907*** (0.1294)	0.1496***	(0.0550) 0.7143***	(0.1931)
	Experience2 : [1 , 5[	0.1056	(0.0883)	0.1274**	(0.0626) 0.0130	(0.2348)
	Experience3 : [5 , 10[	0.0612	(0.1025)	-0.0446	(0.0725) -0.5282***	(0.1246)
	Full-Time	0.3054*** (0.1181)	-0.1816***	(0.0617) -0.5195***	(0.1575)
	Partial-Time 1: [30h, + [ / Week -0.1198	(0.0951)	-0.1573**	(0.0756) -0.2900**	(0.1245)
	Partial-Time 2: [15, 29h [ / Week -0.0488	(0.0971)	-0.0674	(0.0619) -0.4120	(0.2838)
	Fixed-Term Contract	0.1324*** (0.0462)	-0.2331	(0.1616) 0.1487	(0.2980)
	Seasonal Contract	0.2056	(0.2433)	0.9178***	(0.1671) 0.2948	(0.2841)
	Intermediaries Contract	0.3230	(0.2251)	0.7944***	(0.1614) 0.0661	(0.0521)
	Monthly Wage	0.1598*** (0.0362)	-0.0298	(0.0260) -0.0881	(0.0789)
	Rate of Unemployment	-0.0627*** (0.0122)	0.0399***	(0.0089) 0.0343***	(0.0175)
	Number of Observations (Risk)	13543	(3922)	13543	(7689)	13543	(1932)
	Log-Likelihood	-33360.96		-65500.75		-16503.51
	Restricted Log-Likelihood	-33009.38		-66344.48		-17254.81
	Wald chi-2 (30)	1230.42		1927.51		1249.07
	Coefficients are Cox Competing Risk model estimates: (***) significant at 1%, (**) significant at de 5%, (*)
	significant at 10%. Ref AGE40-49, Women, First Cycle Degree , Workman, Firm Size1: [0 , 49], Experience4 :
	[10 , +[, Partial-Time 3: [0, 15h [ / Week.

Table 5 :

 5 Men's transition from Short-Term Contract Cox Competing Risk Model

		Transition to	Transition to	Transition to
		Long-Term Contract	Short-Term Contract	Unemployment
	AGE16-24	-0.0886	(0.0855)	0.2811***	(0.0625) -0.2232**	(0.1171)
	AGE25-39	0.0143	(0.0705)	-0.1471***	(0.0506) -0.2596**	(0.1021)
	AGE50-59	-0.2117	(0.1197)	-0.1855**	(0.0810) 0.2655*	(0.1459)
	AGE60-64	-0.4516	(0.4528)	-0.0138	(0.2300) 0.7400***	(0.3678)
	European	0.3248*** (0.1224)	-0.0293	(0.0611) -0.1162	(0.1105)
	Married	0.2002*** (0.0533)	-0.1137***	(0.0381) -0.3062***	(0.0760)
	University degree	0.2803**	(0.1215)	0.1778**	(0.0881) -0.3973*	(0.2235)
	Bachelor degree	0.4650*** (0.0940)	0.1360*	(0.0785) -0.0806	(0.1579)
	Technical Education	0.1255**	(0.0564)	0.0608	(0.0420) 0.0074	(0.0773)
	General Education	0.1162	(0.0827)	0.0733	(0.0606) 0.0862	(0.1132)
	Executive or Professional	0.6951*** (0.1283)	-0.1292	(0.0910) -0.5629**	(0.2242)
	Intermediary Profession	-0.3282*** (0.0788)	-0.2287***	(0.0610	-0.3770***	(0.1212)
	Employee	-0.3045*** (0.0790)	-0.2364***	(0.0583) -0.3180***	(0.1201)
	Firm Size2: [50 , 99]	0.1131*	(0.0650)	0.0626	(0.0698) 0.05291	(0.1289)
	Firm Size3 : [100 , 499]	0.1280	(0.0882)	0.1966***	(0.0476) -0.02642	(0.0979)
	Firm Size4 : [500 , +]	-0.1280**	(0.0630)	-0.0208	(0.0449	0.06880	(0.0873)
	Public sector	-0.7187*** (0.0708)	-0.1358***	(0.0477)	0.6472***	(0.1166)
	Experience1 : [0 , 1[	1.0011*** (0.1351)	0.5670***	(0.0880) 1.7691***	(0.2977)
	Experience2 : [1 , 5[	0.1149	(0.1350)	0.2499***	(0.0857) 0.7577**	(0.2993)
	Experience3 : [5 , 10[	-0.0313	(0.1553)	0.1172	(0.0971) -0.2155	(0.3776)
	Full-Time	0.2654	(0.1976)	-0.1484	(0.1136) -0.3677	(0.2274)
	Partial-Time 1: [30h, + [ / Week -0.0387	(0.2574)	-0.0804	(0.1497) -0.3486	(0.3096)
	Partial-Time 2: [15, 29h [ / Week 0.3151	(0.2159)	0.0610	(0.1279) -0.1250	(0.2533)
	Fixed-Term Contract	0.1780	(0.3042)	-0.1516	(0.2119) -0.3890	(0.3995)
	Seasonal Contract	0.3109	(0.3304)	1.1063***	(0.2213) 0.0673	(0.4287)
	Intermediaries Contract	0.3470	(0.3038)	0.9405***	(0.2121) 0.4247	(0.4001)
	Monthly Wage	0.1809*** (0.0528)	-0.0896**	(0.0394) 0.0620	(0.0752)
	Rate of Unemployment	-0.0488*** (0.0176)	0.0404***	(0.0132) 0.0306***	(0.0253)
	Number of Observations (Risk)	6410	(1944)	6410	(3532)	6410	(934)
	Log-Likelihood	-14973.97		-27179.48		-7244.71
	Restricted Log-Likelihood	-15418.82		-27761.91		-7627.65
	Wald chi-2 (29)	789.71		1248.59		604.43
	Coefficients are Cox Competing Risk model estimates: (***) significant at 1%, (**) significant at de 5%, (*)
	significant at 10%. Ref AGE40-49, Women, First Cycle Degree, Workman, Firm Size1: [0 , 49], Experience4 :
	[10 , +[, Partial-Time 3: [0, 15h [ / Week.

Table 6 :

 6 Women's transition from Short-Term Contract: Cox Competing Risk Model

		Transition to	Transition to	Transition to
		Long-Term Contract	Short-Term Contract	Unemployment
	AGE16-24	-0.0517	(0.0764)	0.1018**	(0.0550) -0.0401	(0.1099)
	AGE25-39	-0.1060**	(0.0642)	-0.0292	(0.0439) 0.1720**	(0.0924)
	AGE50-59	-0.0610	(0.1052)	0.0128	(0.0694) 0.2012	(0.1515)
	AGE60-64	-0.3985	(0.3406)	-0.0500	(0.1857) -0.0536	(0.4579)
	European	-0.1303	(0.1127)	0.0575	(0.0859) -0.2818**	(0.1316)
	Married	0.0980**	(0.0491)	-0.0322	(0.0336) 0.0863	(0.0692)
	University degree	-0.1729**	(0.1031)	0.1108	(0.0688) -0.5184***	(0.1620)
	Bachelor degree	0.0591	(0.0856)	0.2057***	(0.0609) -0.3400***	(0.1246)
	Technical Education	0.0153	(0.0636)	0.0981**	(0.0447) -0.1004	(0.0820)
	General Education	-0.0425	(0.0761)	0.1382***	(0.0530) -0.2771***	(0.1057)
	Executive or Professional	0.3709	(0.4809)	-0.3374***	(0.0864) -0.7723***	(0.2225)
	Intermediary Profession	-0.1652**	(0.0913)	-0.1782***	(0.0635) -0.3951***	(0.1297)
	Employee	-0.0693	(0.0670)	-0.1581***	(0.0479) -0.1306	(0.0830)
	Firm Size2: [50 , 99]	0.1478**	(0.0890)	0.0542	(0.0642) 0.2200**	(0.1181)
	Firm Size3 : [100 , 499]	0.2703*** (0.0637)	0.1711***	(0.0441) 0.0881	(0.0937)
	Firm Size4 : [500 , +]	0.2592*** (0.0591)	0.0601	(0.0416) 0.2341***	(0.0854)
	Public sector	-0.3106*** (0.0540)	0.0999***	(0.0369) 0.6737***	(0.0867)
	Experience1 : [0 , 1[	0.8526*** (0.1191)	0.3553***	(0.0751) 1.8156***	(0.2512)
	Experience2 : [1 , 5[	0.07725	(0.1182)	0.0717	(0.0727) 0.6275**	(0.2539)
	Experience3 : [5 , 10[	0.15187	(0.1371)	0.1511***	(0.0823) 0.1691	(0.3011)
	Full-Time	0.2551**	(0.1149)	-0.2076***	(0.0764) -0.6124***	(0.1576)
	Partial-Time 1: [30h, + [ / Week -0.3979*** (0.1373)	-0.2183**	(0.0903) -0.6606***	(0.1896)
	Partial-Time 2: [15, 29h [ / Week -0.17516	(0.1112)	-0.1205*	(0.0725)) -0.3848***	(0.1473)
	Fixed-Term Contract	0.23060	(0.3347)	-0.2843	(0.2466) -0.3652	(0.3907)
	Seasonal Contract	0.28407	(0.3570)	0.8493***	(0.2531) 0.2507	(0.4060)
	Intermediaries Contract	0.37740	(0.3301)	0.6264**	(0.2460) 0.1839	(0.3916)
	Monthly Wage	0.1908*** (0.0499)	0.0351	(0.0356) 0.0985	(0.0734)
	Rate of Unemployment	-0.0717*** (0.0173)	0.0474***	(0.0121) 0.0453***	(0.0245)
	Number of Observations (Risk)	7133	(1978)	7133	(4157)	7133	(998)
	Log-Likelihood	-15617.13		-33008.52		-7893.06
	Restricted Log-Likelihood	-15865.95		-33313.09		-8290.03
	Wald chi-2 (29)	495.03		718.27		689.82
	Coefficients are Cox Competing Risk model estimates: (***) significant at 1%, (**) significant at de 5%, (*)
	significant at 10%. Ref AGE40-49, Women, First Cycle Degree, Workman, Firm Size1: [0 , 49], Experience4 :
	[10 , +[, Partial-Time 3: [0, 15h [ / Week.

Table 7 :

 7 Transition from Short-Term Contract to Long-Term Contract Coefficients are Cox Competing Risk model estimates: (***) significant at 1%, (**) significant at de 5%, (*) significant at 10%. Ref AGE40-49, Women, First Cycle Degree, Workman, Firm Size1: [0 , 49], Experience4 : [10 , +[, Partial-Time 3: [0, 15h [ / Week.

		Transition to Long-Term Contract
		In the same firm	To another firm
	AGE16-24	-0.0810	(0.0728)	-0.1065	(0.0929)
	AGE25-39	-0.0942	(0.0639)	-0.0066	(0.0698)
	AGE50-59	-0.2028*	(0.1202)	-0.0670	(0.1054)
	AGE60-64	-1.0593*	(0.5811)	-0.1282	(0.3110)
	Men	0.1104**	(0.0498)	-0.2639***	(0.0584)
	European	0.0409	(0.0848)	-0.3643***	(0.1064)
	Married	0.2367*** (0.0467)	0.0326	(0.0557)
	University degree	-0.0547	(0.1047)	0.0062	(0.1180)
	Bachelor degree	0.2268*** (0.0786)	0.1543	(0.1065)
	Technical Education	0.1325**	(0.0539)	0.0224	(0.0682)
	General Education	0.0353	(0.0731)	0.0619	(0.0872)
	Executive or Professional	0.5222*** (0.1232)	0.4925***	(0.1330)
	Intermediary Profession	-0.1586**	(0.0738)	-0.3439***	(0.0965)
	Employee	-0.0290	(0.0600)	-0.3621***	(0.0747)
	Firm Size2: [50 , 99]	0.1039	(0.0772)	0.1602	(0.1073)
	Firm Size3: [100 , 499]	0.1765*** (0.0590)	0.1837**	(0.0717)
	Firm Size4: [500 , +]	-0.0324	(0.0580)	0.1745***	(0.0645)
	Public sector	-0.4071*** (0.0610)	-0.4141***	(0.0596)
	Experience1 : [0 , 1[	0.0986	(0.5818)	1.0827***	(0.2079)
	Experience2 : [1 , 5[	-0.4203	(0.5903)	0.1108	(0.0916)
	Experience3 : [5 , 10[	1.3269	(0.8258)	0.0639	(0.1042)
	Full-Time	0.4074**	(0.1647)	-0.2413*	(0.1365)
	Partial-Time 1: [30h, + [ / Week -0.2113	(0.1728)	0.0175	(0.1360)
	Partial-Time 2: [15, 29h [ / Week -0.0416	(0.1417)	-0.0130	(0.1354)
	Fixed-Term Contract	0.1245**	(0.0546)	0.4604	(0.5336)
	Seasonal Contract	-0.3409	(0.2984)	1.0949**	(0.5451)
	Intermediaries Contract	0.1291	(0.2638)	0.7660	(0.5318)
	Monthly Wage	0.2385*** (0.0436)	0.0498	(0.0574)
	Rate of Unemployment	-0.0946*** (0.0158)	-0.0091	(0.01961)
	Number of Observations (Risk)	7102	(2313)	6441	(1609)
	Log-Likelihood	-18344.76		-12568.53
	Restricted Log-Likelihood	-18520.02		-12713.91
	Wald chi-2 (30)	332.62		311.98

Table 8 :

 8 Transition from Short-Term Contract to another Short-Term Contract Coefficients are Cox Competing Risk model estimates: (***) significant at 1%, (**) significant at de 5%, (*) significant at 10%. Ref AGE40-49, Women, First Cycle Degree , Workman, Firm Size1: [0 , 49], Experience4 : [10 , +[, Partial-Time 3: [0, 15h [ / Week.

		Transition to Short-Term Contract
		In the same firm	To another firm
	AGE16-24	0.1643*** (0.0609)	0.1825***	(0.0575)
	AGE25-39	-0.0848	(0.0536)	-0.0651	(0.0421)
	AGE50-59	0.0910	(0.0936)	-0.1080**	(0.0637)
	AGE60-64	-0.1483	(0.2934)	0.0199	(0.1666)
	Men	-0.1285*** (0.0407)	-0.2095***	(0.0356)
	European	0.0813	(0.0684)	-0.1119	(0.0715)
	Married	-0.0847**	(0.0375)	-0.0636**	(0.0336)
	University degree	0.0841	(0.0848)	0.1793**	(0.0701)
	Bachelor degree	0.1044	(0.0688)	0.2461***	(0.0655)
	Technical Education	-0.0072	(0.0451)	0.1540***	(0.0417)
	General Education	0.0922	(0.0586)	0.1310**	(0.0539)
	Executive or Professional	-0.2518*** (0.0976)	-0.2642***	(0.0798)
	Intermediary Profession	-0.2449*** (0.0640)	-0.1753***	(0.0594)
	Employee	-0.2156*** (0.0505)	-0.2058***	(0.0474)
	Firm Size2: [50 , 99]	0.0976	(0.0653)	0.0302	(0.0687)
	Firm Size3 : [100 , 499]	0.1709*** (0.0495)	0.1998***	(0.0429)
	Firm Size4 : [500 , +]	-0.0074	(0.0472)	0.0329	(0.0400)
	Public sector	0.1025**	(0.0467)	-0.0286	(0.0369)
	Experience1 : [0 , 1[	0.9480	(0.7092)	0.2448	(0.1837)
	Experience2 : [1 , 5[	0.5542	(0.7135)	0.1434**	(0.0564)
	Experience3 [5 , 10[	-8.5996	(79.3710) 0.1225*	(0.0630)
	Full-Time	-0.0476	(0.1031)	-0.2660***	(0.0780)
	Partial-Time 1: [30h, + [ / Week -0.0259	(0.1288)	-0.2290**	(0.0944)
	Partial-Time 2: [15, 29h [ / Week -0.0616	(0.1050)	-0.0561	(0.0773)
	Fixed-Term Contract	-0.2569	(0.1904)	-0.2169	(0.3573)
	Seasonal Contract	0.7321*** (0.2019)	1.1032***	(0.3605)
	Intermediaries Contract	0.7888*** (0.1904)	0.7752**	(0.3566)
	Monthly Wage	-0.0103	(0.0403)	-0.0364	(0.0343)
	Rate of Unemployment	0.0558*** (0.0133)	0.0272***	(0.0120)
	Number of Observations (Risk)	7102	(3373)	6441	(4316)
	Log-Likelihood	-26595.63		-33988.31
	Restricted Log-Likelihood	-26966.61		-34416.64
	Wald chi-2 (30)	830.44		1012.11

For more details about French Labour Laws, see[START_REF] Abowd | The Costs of Hiring and Separations[END_REF] for an executive summary in english, and[START_REF] Lamy | Lamy Social, Droit Du Travail[END_REF] for an explanation of the text of the law.

We excluded households that are only interviewed once or twice. This can occur for two reasons. First, if a household moves to another address no attempt is made to find this household's new address. The household that is lost is simply replaced by the INSEE by the new inhabitants occupying the original address. As a consequence, a household that have moved between the first and the second interview date, is interviewed only once. A household that have moved between the second and the third interview date, is interviewed only twice. Second, even if a household remains at the same address during the whole observation period, it can refuse to participate at the second and/or third interview date. Households that are not interviewed three times generate incomplete labour market histories.


Souheib Baarir
email: souheib.baarir@lip6.fr

Alexandre Duret-Lutz

Mechanizing the Minimization of Deterministic Generalized Büchi Automata

Deterministic Büchi automata (DBA) are useful to (probabilistic) model checking and synthesis. We survey techniques used to obtain and minimize DBAs for different classes of properties. We extend these techniques to support DBA that have generalized and transitionbased acceptance (DTGBA) as they can be even smaller. Our minimization technique-a reduction to a SAT problem-synthesizes a DTGBA equivalent to the input DTGBA for any given number of states and number of acceptance sets (assuming such automaton exists). We present benchmarks using a framework that implements all these techniques.

Introduction

Deterministic Büchi automata (DBA) are used in several domains like probabilistic model checking [START_REF] Baier | Principles of Model Checking[END_REF] or synthesis of distributed systems [START_REF] Finkbeiner | Uniform distributed synthesis[END_REF]. DBAs are commonly obtained from Büchi automata (BA) by applying Safra's construction [START_REF] Safra | Complexity of Automata on Infinite Objects[END_REF] or, when it works, some powerset-based construction [START_REF] Dax | Mechanizing the powerset construction for restricted classes of ω-automata[END_REF]. Since applications are usually more efficient when dealing with small automata, it makes sense to try to minimize these DBA (i.e., find an equivalent DBA such that no smaller equivalent DBA exist). Two techniques can be used depending on the class of the DBA at hand. Weak DBAs (where accepting cycles cannot mix with rejecting cycles) are minimizable almost like finite automata [START_REF] Löding | Efficient minimization of deterministic weak ω-automata[END_REF]. For the general case, which is NP-complete [START_REF] Schewe | Beyond hyper-minimisation-minimising DBAs and DPAs is NPcomplete[END_REF], Ehlers [START_REF] Ehlers | Minimising deterministic Büchi automata precisely using SAT solving[END_REF] gives a reduction to a SAT problem.

For model checking, several efficient algorithms have been developed to check the emptiness of BAs, but also generalized Büchi automata (GBA) [START_REF] Rozier | A multi-encoding approach for LTL symbolic satisfiability checking[END_REF], and even transition-based generalized Büchi automata (TGBA) [START_REF] Couvreur | On-the-fly emptiness checks for generalized Büchi automata[END_REF]. GBAs have multiple sets of accepting states, while TGBAs have multiple sets of accepting transitions. All these automata types are expressively equivalent, but GBAs and TGBAs are more concise than BAs. Furthermore, TGBAs are naturally obtained from linear-time temporal logic (LTL) formulae [START_REF] Duret-Lutz | LTL translation improvements in Spot[END_REF].

In this paper, we discuss the construction of minimal deterministic transitionbased generalized Büchi automata (DTGBA) for which we do not know any general minimization technique. To handle (non-deterministic) TGBA as input, we propose (and implement) two processing chains that convert TGBA into minimal DTGBA. One attempts to determinize transition-based Büchi automata via a powerset construction, the other uses Safra's construction. Although these two determinizations do not work with generalized acceptance, we interpret the resulting automaton as a DTGBA with a single acceptance set and attempt to minimize it using more acceptance sets. The minimization technique we propose is a generalization of Ehlers' SAT-based procedure [START_REF] Ehlers | Minimising deterministic Büchi automata precisely using SAT solving[END_REF] to deal with DTGBA instead of DBA. This way we effectively obtain a minimal DTGBA, even though we use determinization procedures that do not support generalized acceptance.

The paper is organized as follows. Section 2 defines the various types of automata, some conversions between them, and key concepts. Section 3 reviews the hierarchy of recurrence properties and algorithms that exist to determinize or minimize automata in that class. Section 4 shows how to encode the minimization of a DTGBA as a SAT-problem, and then discusses its use. Finally, Section 5 presents results on the minimization of DTGBA obtained from LTL formulae.

Preliminaries

Let AP be a finite set of (atomic) propositions, and let B = {⊥, } represent Boolean values. An assignment is a function : AP → B that valuates each proposition. Σ = B AP is the set of all assignments of AP. X * (resp. X ω ) denotes the set of finite (resp. infinite) sequences over a set X. The empty sequence is denoted ε. A word w ∈ (B AP ) ω is an infinite sequence of assignments. A language (also called property) is a set of words. For any infinite sequence π we denote by inf(π) the set of elements that appear infinitely often in π.

Definition 1 (Labeled Transition System

). An LTS is a tuple S = AP, Q, ι, δ where AP is a finite set of atomic propositions, Q is a finite set of states, ι ∈ Q is the initial state, δ ⊆ Q × B AP × Q is the transition relation, labeling each transition by an assignment.

A run of an LTS is an infinite sequence π = (q 0 , 0 , q 1 )(q 1 , 1 , q 2 )(q 2 , 2 , q 3 ) • • • ∈ δ ω of transitions such that q 0 = ι. For any such run, we denote by π |Q = q 0 q 1 q 2 • • • ∈ Q ω the sequence of states it visits, and we say that π recognizes the word

0 1 2 • • • ∈ (B AP ) ω .
A cycle C = (q 1 , 1 , q 2 )(q 2 , 2 , q 3 ) . . . (q n , n , q 1 ) is a finite sequence of transitions that forms a loop and visits the finite sequence C |Q = q 1 . . . q n of states. For notational convenience, we sometime interpret C |Q as a set of states.

As an implementation optimization, and to simplify illustrations, it is practical to use edges labeled by Boolean formulae to group transitions with same sources and destinations: for instance two transitions (s 1 , a b, s 2 ) and (s 1 , ab, s 2 ) will be represented by an edge from s 1 to s 2 and labeled by the Boolean formula a.

For convenience of notation, we may view the relation δ as a one-argument function δ :

Q → 2 (B AP ×Q) with δ(q) = {( , d) | (q, , d) ∈ δ} or as a two-argument function δ : Q × B AP → 2 Q with δ(q, ) = {d | (q, , d) ∈ δ}.

Definition 2 (Deterministic and Complete

). An LTS S = AP, Q, ι, δ is deterministic iff |δ(q, )| ≤ 1 for all q ∈ Q and ∈ B AP , and it is complete iff |δ(q, )| ≥ 1 for all q and . To characterize the infinite runs of an LTS that should be accepted, we consider several variants of Büchi automata that differ by their acceptance condition.

Definition 3 (Büchi-like Automata). A Büchi-like automaton is a pair A = S, F where S is an LTS, and F is a finite set whose semantic is defined differently for each type of acceptance. Given a run π and a cycle C: In all cases the language L (A) of an automaton is the set of words recognized by accepting runs of A. A cycle is rejecting iff it is not accepting.

BA: for Büchi Automata, F ⊆ Q, π is accepted iff inf(π |Q ) ∩ F = ∅, and C is accepting iff C |Q ∩ F = ∅; GBA: for Generalized Büchi Automata, F ⊆ 2 Q , π is accepted iff ∀F ∈ F, inf(π |Q ) ∩ F = ∅,
DBA, DGBA, DTBA, and DTGBA, denote the restrictions of the above types to automata where the associated LTS S is deterministic.

As an example, Fig. 1 shows one deterministic and complete automaton of each type. For BA, the states in F (called accepting states), are traditionally denoted by double circles. For GBA, F = {F 1 , F 2 , . . .} is a set of acceptance sets F i ⊆ Q, and each of these F i is pictured using colored dots on the side of the states it contains (a state may have multiple such dots if it belongs to multiple acceptance sets). For transition-based acceptance (TBA or TGBA), we put those colored dots on the transitions (of course, only one color is used for TBA).

Definition 4 (SCC).

A strongly connected component (SCC) of an automaton S, F is a set of states that are pairwise connected in S, and that is maximal with respect to inclusion. An SCC is accepting if it contains an accepting cycle, otherwise, it is rejecting. An SCC with a single state and no cycle is called trivial.

Definition 5 (Automaton Typeness

). An automaton A = S, F is said to be β-type if there exists an automaton B = S, F of acceptance type β such that L (A) = L (B). In other words, A is β-type if we can change its acceptance set so that it accepts the same language with the same transition structure but with a different type of acceptance condition (the β one).

For instance any BA S, F is GBA-type, because it can be trivially represented as the GBA S, {F} . Any GBA S, {F 1 , . . . , F n } is TGBA-type, since it is equivalent to the TGBA S, {F 1 , . . . , F n } with

F i = {(s, , d) | (s, , d) ∈ δ ∧ s ∈ F i } (i.e.
, the membership of any state to some accepting set F i is transferred to all its outgoing transitions). Similarly all BA are TBA-type, and all TBA are TGBA-type. These trivial conversions can sometime be used in the opposite direction. For instance a TGBA is "trivially" GBA-type if all the outgoing transitions of each state belong to the same acceptance sets.

Since a TGBA can represent any considered type (BA, GBA, TBA) using the same transition structure, it is often practical to consider only TGBAs and treat the other types as particular cases. For algorithms that cannot deal with generalized acceptance, a TGBA can be degeneralized into a TBA or a BA [START_REF] Babiak | Compositional approach to suspension and other improvements to LTL translation[END_REF]. For instance the TBA of Fig. 1(c) was degeneralized from the TGBA of Fig. 1(d).

Definition 6 (Realizability). A property (or an automaton) is β-realizable if there exists an automaton with β acceptance that accepts the same language.

Any Büchi-like automaton is β-realizable for β ∈ {BA, GBA, TBA, TGBA}. Furthermore any deterministic Büchi-like automaton is Dβ-realizable. However it is well known than not all BAs are DBA-realizable, and this fact holds for the three other types of Büchi acceptance as well.

Definition 7 (Weakness). An automaton is inherently weak if it contains no accepting cycle that has a state in common with a rejecting cycle.

This notion of inherent weakness [START_REF] Boigelot | On the use of weak automata for deciding linear arithmetic with integer and real variables[END_REF] generalizes the more common notion of weak automaton [START_REF] Bloem | Efficient decision procedures for model checking of linear time logic properties[END_REF][START_REF] Černá | Relating hierarchy of temporal properties to model checking[END_REF] where states of an SCC should be either all accepting or all non-accepting. Defining F as the set of states that belong to some accepting cycle will turn any inherently weak automaton into a Weak BA (WBA) [START_REF] Boigelot | On the use of weak automata for deciding linear arithmetic with integer and real variables[END_REF].

Definition 8 (Minimal-state automaton [START_REF] Maler | On syntactic congruences for ω-languages[END_REF]). For a language L ⊆ Σ ω , let

≈ L ⊆ Σ * × Σ * be the right-congruence defined by u ≈ L v iff uα ∈ L ⇐⇒ vα ∈ L for all α ∈ Σ ω . Let [•] denote the equivalence classes of L, i.e., [u] = {v ∈ Σ * | u ≈ L v}. The minimal-state automaton of L, denoted MSA(L) is the (complete and deterministic) LTS AP, {[u] | u ∈ Σ * }, [ε], δ where δ([u], ) = [u ].

Existing Determinization and Minimization Procedures

We now discuss several existing procedures to determinize and minimize Büchi automata. Some of these apply only to specific subclasses of temporal properties. Figure 2 shows a classification of temporal properties, using the names from Manna and Pnueli [START_REF] Manna | A hierarchy of temporal properties[END_REF], and with an additional couple of interesting subclasses. The whole square represents the entire set of BA-realizable properties, also called reactivity properties. This set includes persistence properties, which can be realized by weak automata, and recurrence properties ,which can be realized by deterministic automata. The intersection of these last two sets defines the obligation properties, which can be realized by weak and deterministic automata. The obligation class includes the well-known subclasses of safety and guarantee properties (not depicted here), as well as all their Boolean combinations.

Determinization. Assume that a recurrence property ϕ is represented by a possibly non-deterministic BA A ϕ = T, F , and for which we wish to obtain a DBA D ϕ = T , F . We can consider different procedures depending on the class to which ϕ belongs.

If ϕ is known to be an obligation (for most LTL formulae, this can be checked syntactically [START_REF] Černá | Relating hierarchy of temporal properties to model checking[END_REF]), then a weak DBA (WDBA) D ϕ can be obtained from A ϕ in a quite efficient way [START_REF] Dax | Mechanizing the powerset construction for restricted classes of ω-automata[END_REF]: T should be determinized by the classical powerset construction to create T = P(T ), and the set F can be computed by selecting one word of each SCC of T and checking whether it is accepted by A ϕ . Dax et al. [START_REF] Dax | Mechanizing the powerset construction for restricted classes of ω-automata[END_REF] additionally show that if it is not known whether a property ϕ is an obligation, this procedure may still be applied but its result D ϕ must then be checked for equivalence with A ϕ .

The class CONG is defined as the set of languages L which are realizable by a BA automaton whose LTS is MSA(L), this includes all obligations as well as some properties that are not expressible by weak automata. For instance the property specified by the formula G(a → X¬a) ∧ GF(a) is in CONG: it has three equivalence classes [ε], [a], and [aa], and the corresponding MSA can be used to define the DBA shown in Fig. 3(a).

The formula GFa is not in CONG because its MSA has a single state (the language has no distinguishing prefixes), yet there is no single-state DBA that can recognize GFa. However there exists a 1-state DTBA for this property, shown in Fig. 3(b). We could therefore define the class TCONG of properties that are

[ε] [a] [aa] a ā a ā (a) [ε] a ā (b)
Fig. 3: (a) G(a → X¬a) ∧ GFa specifies a property in CONG: it is realizable by a DBA whose LTS is the MSA of its language. (b) Although GFa is not in CONG, its MSA can serve as a support for an equivalent DTBA.

DTBA-realizable with their MSA as LTS. Note that GFa ∧ GFb whose MSA also has a single state, is not in TCONG: its minimal DTBA is shown in Fig. 1(c).

Dax et al. [START_REF] Dax | Mechanizing the powerset construction for restricted classes of ω-automata[END_REF] show that you can apply the classical powerset construction to determinize the LTS of any BA A ϕ = T, F recognizing a property in CONG, and the resulting deterministic LTS T = P(T ) can be labeled as a DBA D ϕ = T , F recognizing L (A ϕ ). The algorithm used to obtain the necessary F is more complex than the one used for weak automata as it requires an enumeration of all the elementary cycles in T . Futhermore, the DBAs obtained this way are not necessary minimal. This construction can be extended straightforwardly to transition-based acceptance; this way we may obtain DTBAs for properties (such as GFa) where the original state-based procedure would not deliver any DBA.

Another determinization procedure, which applies to all recurrence properties, is to use Safra's construction [START_REF] Safra | Complexity of Automata on Infinite Objects[END_REF] to convert a BA into a deterministic Rabin automaton (DRA). More generally, Schewe and Varghese [START_REF] Schewe | Tight bounds for the determinisation and complementation of generalised Büchi automata[END_REF] have recently proposed a determinization algorithm that inputs a TGBA and outputs a DRA. DRA that express recurrence properties are all DBA-type, and Krishnan et al. [START_REF] Krishnan | Deterministic ω-automata vis-avis deterministic Büchi automata[END_REF] show how to compute the associated DBAs.

Unfortunately, all these determinization procedures produce only DBA (or DTBA). To our knowledge, there is no determinization procedure that would produce a deterministic automaton with generalized acceptance.

Minimization. Minimizing a DBA, i.e., building a DBA such that no smaller equivalent DBA exist, is in general, an NP-complete problem [START_REF] Schewe | Beyond hyper-minimisation-minimising DBAs and DPAs is NPcomplete[END_REF].

However, weak DBAs (i.e., obligation properties) can be minimized using an algorithm identical to those performed on deterministic finite automata: the only requirement is to choose the acceptance of trivial SCCs correctly [START_REF] Löding | Efficient minimization of deterministic weak ω-automata[END_REF].

For the more general recurrence properties, Ehlers [START_REF] Ehlers | Minimising deterministic Büchi automata precisely using SAT solving[END_REF] gives an encoding of an equivalent minimal DBA as the solution of a SAT problem. His technique can also be extended straightforwardly to minimize a DTBA.

Until now there were no minimization procedure for generalized Büchi automata. In the next section we show an encoding inspired by Ehlers' [START_REF] Ehlers | Minimising deterministic Büchi automata precisely using SAT solving[END_REF] for minimizing DTGBAs. For any DTGBA A with n states and m acceptance sets, our encoding attempts to synthesize an equivalent DTGBA with n states and m acceptance sets for some given n or m (and possibly m > m). By combining this procedure with existing (non-generalized) determinizations, we effectively obtain a minimal DTGBA with multiple acceptance sets, even though we do not know of any determinization procedure that supports generalized acceptance. Given a complete DTGBA R = AP, Q R , ι R , δ R , F R , and two integers n and m, we would like to construct (when it exists) a complete DTGBA

C = AP, Q C , ι C , δ C , F C such that L (R) = L (C), |Q C | = n and |F C | = m.
We call R the reference automaton, and C, the candidate automaton.

Since C and R are complete and deterministic, any word of Σ ω has a unique run in R and C, and testing L (R) = L (C) can be done by ensuring that each word is accepted by R iff it is accepted by C. In practice, this is checked by ensuring that any cycle of the synchronous product C ⊗ R corresponds to cycles that are either accepting in C and R, or rejecting in both.

This observation is used by Ehlers [START_REF] Ehlers | Minimising deterministic Büchi automata precisely using SAT solving[END_REF] for his SAT encoding. In his case, a cycle in a DBA can be detected as accepting as soon as it visits an accepting state. We use a similar encoding for our setup. However, because of the generalized acceptance condition of DTGBAs, we have to keep track of all the acceptance sets visited by paths of the product to ensure that cycles have the same acceptance status in both C and R.

Encoding as a SAT Problem

Let SCC R ⊆ 2 Q R denote the set of non-trivial strongly connected components of R, and let Acc(q 1 , , q 2 ) = {A ∈ F R | (q 1 , , q 2 ) ∈ A} be the set of acceptance sets of R that contain the transition (q 1 , , q 2 ) ∈ δ R .

We encode C with two sets of variables: -The variables { q 1 , , q 2 δ C | (q 1 , q 2 ) ∈ Q 2 C , ∈ Σ} encode the existence of transitions (q 1 , , q 2 ) ∈ δ C in the candidate automaton.

-Variables { q 1 , , A i , q 2 F C | (q 1 , q 2 ) ∈ Q 2 C , ∈ Σ, A i ∈ F C } encode the membership of these transitions to the acceptance set A i ∈ F C of C.
For the product C ⊗ R, we retain the reachable states, and parts of paths that might eventually be completed to become cycles.

-A variable in { q, q , q, q , ∅, ∅ | q ∈ Q C , q ∈ Q R } encodes the existence of a reachable state (q, q ) in C ⊗ R. The reason we use a sextuplet to encode such a pair is that each (q, q ) will serve as a starting point for possible paths.

-A variable in { q 1 , q 1 , q 2 , q 2 , F, F | (q 1 , q 2 ) ∈ Q 2 C , S ∈ SCC R , (q 1 , q 2 ) ∈ S 2 , F ⊆ F C , F ⊆ F R } denotes that
there is a path between (q 1 , q 1 ) and (q 2 , q 2 ) in the product, such that its projection on the candidate automaton visits the acceptance sets F ⊆ F C , and its projection on the reference automaton visits the acceptance sets F ⊆ F R . This set of variables is used to implement the cycle equivalence check, so the only q 1 and q 2 that need to be considered should belong to the same non-trivial SCC of R. With these variables, the automaton C can be obtained as a solution of the following SAT problem. First, C should be complete (i.e., δ C is total):

q1∈Q C , ∈Σ q2∈Q C q 1 , , q 2 δ C (1)
The initial state of the product exists. Furthermore, if (q 1 , q 1 ) is a state of the product, (q 1 , , q 2 ) ∈ δ R is a transition in the reference automaton, and (q 1 , , q 2 ) ∈ δ C is a transition in the candidate automaton, then (q 2 , q 2 ) is a state of the product too:

∧ ι C , ι R , ι C , ι R , ∅, ∅ ∧ (q1,q2)∈Q 2 C , q 1 ∈Q R , ( ,q 2 )∈δ R (q 1 )
q 1 , q 1 , q 1 , q 1 , ∅, ∅ ∧ q 1 , , q 2 δ C → q 2 , q 2 , q 2 , q 2 , ∅, ∅ (2) Any transition of the product augments an existing path, updating the sets F and F of acceptance sets visited in each automata. Unfortunately, we have to consider all possible subsets G ∈ 2 F C of acceptances sets to which the candidate transition (q 2 , , q 3 ) could belong, and emit a different rule for each possible G.

∧ (q1,q2,q3)∈Q 3 C , (F,G)∈(2 F C ) 2 , S∈SCC R , (q 1 ,q 2 )∈S 2 , F ∈2 F R , ( ,q 3 )∈δ R (q 2 )           q 1 , q 1 , q 2 , q 2 , F, F ∧ q 2 , , q 3 δ C ∧ A∈G q 2 , , A, q 3 F C ∧ A ∈G ¬ q 2 , , A, q 3 F C           → q 1 , q 1 , q 3 , q 3 , F ∪ G, F ∪ Acc(q 2 , , q 3 ) (3)
If a path of the product is followed by a transition (q 2 , , q 3 ) ∈ δ R and a transition (q 2 , , q 3 ) ∈ δ C that both closes the cycle (q 3 = q 1 ∧ q 3 = q 1 ), but such that this cycle is non-accepting with respect to the reference automaton (Acc(q 2 , , q 3 ) ∪ F = F R ), then the cycle formed in the candidate automaton by (q 2 , , q 1 ) should not be accepting (at least one acceptance set of F C \ F is missing):

∧ (q1,q2)∈Q 2 C , F ∈2 F C , S∈SCC R , (q 1 ,q 2 )∈S 2 , F ∈2 F R ,
( ,q 3 )∈δ R (q 2 ), q 3 =q 1 , Acc(q 2 , ,q 3 )∪F =F R q 1 , q 1 , q 2 , q 2 , F, F ∧ q 2 , , q

1 δ C → ¬ A∈F C \F q 2 , , A, q 1 F C (4)
Conversely, if a path of the product is followed by a transition (q 2 , , q 3 ) ∈ δ R and a transition (q 2 , , q 3 ) ∈ δ C that both closes the cycle (q 3 = q 1 ∧ q 3 = q 1 ), but such that this cycle is accepting with respect to the reference automaton (Acc(q 2 , , q 3 ) ∪ F = F R ), then the cycle formed in the candidate automaton by (q 2 , , q 1 ) should also be accepting ((q 2 , , q 1 ) should belong at least to all missing acceptance sets F C \ F ):

∧ (q1,q2)∈Q 2 C , F ∈2 F C , S∈SCC R , (q 1 ,q 2 )∈S 2 , F ∈2 F R , ( ,q 3 )∈δ R (q 2 ), q 3 =q 1 Acc(q 2 , ,q 3 )∪F =F R q 1 , q 1 , q 2 , q 2 , F, F ∧ q 2 , , q 1 δ C → A∈F C \F q 2 , , A, q 1 F C (5)
Optimizations. As suggested by Ehlers [START_REF] Ehlers | Minimising deterministic Büchi automata precisely using SAT solving[END_REF], the set of possible solutions can be optionally constrained with some partial symmetry breaking clauses. Assuming Q C = {q 1 , ..., q n } and Σ = { 0 , . . . , m-1 } we can order the transitions of the solution lexicographically with respect to their source and label, as (q 1 , 0 , d 1 ), (q 1 , 1 , d 2 ), . . . , (q 1 , m-1 , d m ), (q 2 , 0 , d m+1 ), etc., and constrain the solution so that the destination of the first transition should be chosen between d 1 ∈ {q 1 , q 2 }, the destination of the second between d 2 ∈ {q 1 , q 2 , q 3 }, etc.

∧ 1≤i≤|Q|, 0≤j<|Σ|, (i-1)|Σ|+j+3≤k≤n ¬ q i , j , q k δ C (S)
ReduceStatesDTGBA(R, m = R.nb acc sets()): repeat:

n ← R.nb states() C ← SynthesizeDTGBA(R, n -1, m) if C does not exists: return R R ← C
Fig. 4: Given a complete DTGBA A, attempt to build an equivalent smaller one with the same number of acceptance sets.

Equations ( 3)-( 5) can be encoded more efficiently when q 1 and q 2 belong to a weak SCC. In that case it is not necessary to remember the history F of the acceptance sets seen by paths in that SCC, since all paths are either accepting or rejecting. Variables of the form q 1 , q 1 , q 2 , q 2 , F, F where F ∈ 2 F R can hence be restricted to just F = ∅, limiting the number of variables and clauses emitted.

State-based Output. To produce automata with state-based acceptance, it suffices to consider all variables q, , A i , q F C that share the same q and A i as aliases. This way, the DTGBA output is DGBA-type.

Usage

We call SynthesizeDTGBA(R, n, m) the procedure that:

1. inputs a complete DTGBA R, two integers n = |Q C | and m = |F C |, 2
. produces a DIMACS file with all the above clauses, 3. calls a SAT solver to solve this problem, 4. builds the resulting DTGBA C if it exists. The construction of this automaton depends only on the value of variables { q, , q 1) constraints C to be complete, there is no explicit constraint for C to be deterministic. By construction, any word w is accepted in R iff it is accepted by any run that recognizes w in C. In the presence of two transitions q, , d 1 δ C and q, , d 2 δ C when building C, we can safely ignore one of them to ensure determinism.

δ C | (q, q ) ∈ Q 2 C , ∈ Σ} ∪ { q, , A i , q F C | (q, q ) ∈ Q 2 C , ∈ Σ, A i ∈ F C }. Although equation (

Minimization: |F

C | = |F R |. Given a complete DTGBA R = AP, Q R , ι R , δ R , F R ,
we may use SynthesizeDTGBA in a loop such as the one shown in Fig. 4 to reduce the number of states of the automaton. By default, we keep the same number m = |F R | of acceptance sets for the candidate automaton.

Minimization with Generalization: |F

C | > |F R |.
A greater reduction might be obtained by increasing the number m = |F C | of acceptance sets. This can be interpreted as the converse of a degeneralization: instead of augmenting the number of states to reduce the number of acceptance sets, we augment the number of acceptance sets in an attempt to reduce the number of states.

It is however not clear how this increase of m should be done. Figure 5 shows an example of a property that can be expressed by a 4-state DTGBA if m = 1, a 2-state DTGBA if m = 2 and a 1-state DTGBA if m = 4. Interestingly, the smallest DTGBA for m = 3 also has two states. Consequently an algorithm that increments m as long as it reduces the number of states would never reach m = 4.

We leave open the problem of finding the smallest m such that no smaller equivalent DTGBA with a larger m can be found. Instead, we use the following heuristic: let m be the number of acceptance set that were "naturally" used to translate the formula ϕ into a TGBA A ϕ (before any degeneralization or determinization). In the case of (GFa ∧ GFb) ∨ (GFc ∧ GFd), each F operator will require one acceptance set during the translation [START_REF] Duret-Lutz | LTL translation improvements in Spot[END_REF], so we would use m = 4.

Implementation and Experiments

Implemented Tools

Figure 6 gives an overview of the processing chains we implemented to produce a minimal DTGBA or DTBA. With the exception of ltl2dstar 0.5.1, a tool written by Joachim Klein [START_REF] Klein | Experiments with deterministic ω-automata for formulas of linear temporal logic[END_REF] to convert LTL formulae into deterministic Rabin or Streett automata, all the other white boxes correspond to algorithms that have been implemented in Spot 1.2, and have been integrated in two command-line tools: ltl2tgba at the top of the picture, and dstar2tgba at the bottom.

ltl2tgba takes as input an LTL formula and translates it into a TGBA A = S, F [START_REF] Duret-Lutz | LTL translation improvements in Spot[END_REF]. If the desired number of acceptance sets m was not supplied on the command-line, we set m ← |F| right after this step. We now attempt WDBA minimization [START_REF] Dax | Mechanizing the powerset construction for restricted classes of ω-automata[END_REF], if that succeeded, we output a minimal weak DBA (looking for transition-based or generalized acceptance will not reduce it further). Otherwise, we simplify the TGBA using simulation-based reductions [START_REF] Babiak | Compositional approach to suspension and other improvements to LTL translation[END_REF]. If the resulting TGBA has more than one acceptance set but we plan to build a DTBA (i.e. m = 1), we degeneralize it. If the resulting TBA is nondeterministic, we attempt the transition-based variant of Dax et al. [START_REF] Dax | Mechanizing the powerset construction for restricted classes of ω-automata[END_REF]'s powerset construction followed by a cycle-enumeration to decide the acceptance of each transition. This procedure works only on a TBA, hence the previous degeneralization is also performed on any nondeterministic TGBA. If this powerset construction fails to produce an equivalent DTBA, it means the input property is not in TCONG. Otherwise the deterministic automaton is sent for SAT-based minimization. We have two procedures implemented: "DTGBA SAT" is the encoding described in Sec. 4.1, while "DTBA SAT" is an adaptation of Ehlers' encoding [START_REF] Ehlers | Minimising deterministic Büchi automata precisely using SAT solving[END_REF] to transition-based Büchi acceptance and is more-efficient to use when m = 1 (see Annex A). Not apparent on this picture, is that these two algorithms can be configured to output automata that are DBA-type or DGBA-type, as discussed in the last paragraph of Sec. 4.1. To solve SAT problems, we use glucose 2.3 [START_REF] Audemard | Predicting learnt clauses quality in modern SAT solvers[END_REF], which is ranked first in the hard-combinatorial benchmark of the 2013 SAT Competition. If the automaton could not be determinized by ltl2tgba, the second approach with dstar2tgba is used instead. This approach starts with ltl2dstar to convert the input LTL formula into a deterministic Rabin automaton (DRA). The produced DRA is then converted to a DBA [START_REF] Krishnan | Deterministic ω-automata vis-avis deterministic Büchi automata[END_REF] if such a DBA exists, otherwise it means that the formula is not a recurrence. The resulting DBA is turned into a minimal WDBA if it expresses an obligation [START_REF] Dax | Mechanizing the powerset construction for restricted classes of ω-automata[END_REF], otherwise it is simplified using simulation-based reduction, before finally proceeding to SAT-based minimization.

Experiments

To assert the effectiveness of our minimization procedures, we took LTL formulas expressing recurrence properties, and attempted to build a minimal DBA, DTBA, and DTGBA for each of them. The LTL formulae are all those listed by Ehlers [START_REF] Ehlers | Minimising deterministic Büchi automata precisely using SAT solving[END_REF], and those of Esparza et al. [START_REF] Esparza | Rabinizer: Small deterministic automata for LTL(F,G)[END_REF] that are DBA-realizable. We also added a few formulas of our own.

For comparison, we also ran Ehlers' DBAminimizer (dated November 2011) [START_REF] Ehlers | Minimising deterministic Büchi automata precisely using SAT solving[END_REF]: a tool that takes deterministic Rabin automata, as produced by ltl2dstar, and converts them into their minimal DBA by solving a SAT problem with PicoSat (version 957). This tool is named "DBAm..zer" in our tables.

We executed our benchmark on a machine with four Intel Xeon E7-2860 processors and 512GB of memory. We limited each minimization procedure (the entire process of taking an LTL formula or a Rabin automaton into a minimal DBA, including writing the problem to disk, not just the SAT-solving procedure) to 2 hours, and each process to 40GB of memory.

For presentation, we partitioned our set of formulae into four classes, based on which path they would take in ltl2tgba, denoted by the x marks in Fig. 6.

1 Formulae that correspond to obligations properties. On these formulas, the powerset construction can be used to obtain a DBA [START_REF] Dax | Mechanizing the powerset construction for restricted classes of ω-automata[END_REF], and this DBA can be minimized in polynomial time [START_REF] Löding | Efficient minimization of deterministic weak ω-automata[END_REF]. Using a SAT-based minimization in this case would be unreasonable. 2 Formulae for which ltl2tgba translator naturally produces deterministic automata, without requiring a powerset construction. 3 Formulae that ltl2tgba can successfully convert into a DTBA by applying a powerset construction. 4 Formulae that ltl2tgba would fail to convert into a DTBA, and for which dstar2tgba is needed.

For size reason, we only present an excerpt of the results for the most interesting classes: 4 (Table 1) and 3 (Table 2). 4 For each formula we show the size of the DRA constructed by ltl2dstar, the size of the DTBA or DBA built by dstar2tgba before SAT-minimization, and the size of the minimal DBA, DTBA or DTGBA after SAT-minimization. In the case of DTGBA the desired number of acceptance sets m is shown in the second column (this m was computed by running only the translation algorithm of ltl2tgba, and picking m ← |F| on the result).

Column "C." indicates whether the produced automata are complete: rejecting sink states are always omitted from the sizes we display, and this explains differences when comparing our tables with other papers that measure complete automata. When C = 0, a complete automaton would have one more state.

Cases that took more than 2 hours or 40GB are shown as "(killed)"; an additional "≤ n" gives the number of states of the smallest automaton successfully computed. SAT problems requiring more than 2 31 clauses, the maximum supported by state-of-the-art solvers, are shown as "(intmax)". Cases where the output of the SAT minimization is smaller than the input are shown with a light gray background. Bold numbers show cases where the minimal DTBA is smaller than the minimal DBA (transition-based acceptance was useful) and cases where the minimal DTGBA is smaller than the minimal DTBA (generalized acceptance Table 1: Formulae that we do not know how to determinize other than via DRA. was useful). Dark gray cells show cases where the tool returned an automaton that was not minimal. For dstar2tgba, it is because glucose answers INDETERMINATE when it is not able to solve the problem: dstar2tgba then pessimistically assumes that the problem is unsatisfiable and returns the input automaton.

The couple of cases where we are able to produce a minimal DBA, but DBAminimizer failed, are because we apply more efficient simplification routines on the DBA before it is passed to the SAT-minimization, our encoding takes advantage of SCCs in the reference automaton, and we use a different SAT solver. The cases where we fail to output minimal DBA, but successfully output a DTBA (or even a DTGBA) are due to the fact that DTBA and DTGBA will produce smaller automata, so the last iteration of the algorithm of Fig. 4, the one where the problem is UNSAT (often the more time-consuming problem), is applied to a smaller automaton. Finally bold numbers of the minDTGBA column confirm that using generalized acceptance can actually reduce the size of a DBA or DTBA. Note that useless acceptance sets have been removed from all DTGBA produced [START_REF] Babiak | Compositional approach to suspension and other improvements to LTL translation[END_REF], so |F| might be smaller than m.

Table 2 shows an excerpt of class 3 : formulae that can be determinized by the powerset construction of Dax et al. [START_REF] Dax | Mechanizing the powerset construction for restricted classes of ω-automata[END_REF]. As this construction enumerates all cycles of the determinized automaton to fix its acceptance sets, it is potentially very long. We therefore compare our two approaches: each formula of the table has two result lines, the upper line corresponds to ltl2tgba (with the powerset construction), while the lower line shows results via ltl2dstar (with Safra's construction). In this table, the former approach is almost always the fastest.

These tables show that even if powerset and Safra's construction are only able to deal with a single acceptance set, so force us to degeneralize automata, we can successfully reconstruct minimal DTGBAs with generalized acceptance.

Conclusion and Future Work

Deterministic Büchi automata are mandatory in some applications like verification of Markov decision processes, probabilistic model checking, or synthesis of distributed systems from LTL specifications. In these contexts small automata are more than welcome. Furthermore, it is well known that transition-based and generalized acceptance contributes to the conciseness of automata. However, to our knowledge, there did not exist any algorithm to produce minimal and generalized deterministic Büchi automata. Furthermore, we do not know of any determinization algorithm that would build a generalized automaton.

In this paper, we have presented a complete framework with two complete processing chains for determinizing and minimizing transition-based generalized Büchi automata. Even though we construct non-generalized deterministic automata before minimizing them, our SAT-based minimization can be used to produce minimal DTGBA for a given number of acceptance sets m.

Our results show that this SAT-based technique is effective for medium-sized automata. For large automata, SAT-solving is expensive, but it could still be run with a time constraint to produce a smaller (but not necessarily minimal) DTGBA.

In the future we plan to improve our encoding by using more structural information about the reference automaton to reduce the number clauses and variables used, and, hopefully, deal with larger automata. We also need to investigate the problem, mentioned in Section 4.2, of selecting the "best" m for a given automaton, and the possibility to extend Dax et al.'s technique to a class of properties that are realizable by a DTGBA whose LTS is a MSA (this class would contain TCONG).

Other recent algorithms from the literature should also be considered for integration in our setup. For instance our TGBA simplification step of Fig. 6 could be improved using other simulation techniques [START_REF] Schewe | Beyond hyper-minimisation-minimising DBAs and DPAs is NPcomplete[END_REF][START_REF] Clemente | Advanced automata minimization[END_REF], and an implementation of determinization technique of [START_REF] Schewe | Tight bounds for the determinisation and complementation of generalised Büchi automata[END_REF] could also contribute to reducing the size of the automaton that has to be minimized.

Fig. 1 :

 1 Fig. 1: Minimal deterministic automata recognizing the LTL formula GFa ∧ GFb.

  and C is accepting iff ∀F ∈ F, C |Q ∩ F = ∅; TBA: for Transition-based Büchi Automata, F ⊆ δ, π is accepted iff inf(π)∩F = ∅, and C is accepting iff C ∩ F = ∅; TGBA: for Transition-based Generalized Büchi Automata, F ⊆ 2 δ , π is accepted iff ∀F ∈ F, inf(π) ∩ F = ∅, and C is accepting iff ∀F ∈ F, C ∩ F = ∅.

Fig. 2 :

 2 Fig. 2: Hierarchy of temporal properties in relation with subclasses of Büchi BA.

= 4 Fig. 5 :

 45 Fig. 5: Examples of minimal DTGBA recognizing (GFa ∧ GFb) ∨ (GFc ∧ GFd).

Fig. 6 :

 6 Fig.6: The two tool chains we use to convert an LTL formula into a DTBA or a DTGBA. |F| is the number of acceptance condition of the current automaton, while m is the desired number of acceptance sets.

  m . . z e r m i n D B A m i n D T B A m i n D T G B A m C. |Q| |Q| |Q| time |Q| time |Q| time |Q| |F| time (ā ∧ Fa) R( b R XFc) 2 1 60 24 (killed) 11 1585 7 14 7 1 815 ā ∧ ((Fb U a) W Xc) 2 0 31 20 (killed) (killed≤15) (killed≤14) (killed≤13) (a R(b R Fc)) W XGb 1 1 31 24 (killed) (killed≤11) U b) R Fc) W Xc 3 1 47 32 11 1216 11 1792 9 55 (intmax) G((a ∧ b) ∨ Ga ∨ F(c ∧ XXc)) 1 1 49 27 (killed) 9 577 7 307 7 1 307 Ga R(F b ∧ (c U b)) G(F(ā ∧ Fa) U(b U Xc)) 3 1 52 35 (killed) 10 1304 7 981 (intmax) GF(a ∧ F(b ∧ Fc)) G(Fā ∨ (Fb U c)) 3 1 29 23 4 1368 4 77 3 76 (intmax) G(Fā U X(F b ∧ Xb)) 3 1 58 37 (killed) 4 480 3 512 (intmax) GF(a ∧ XXXFb) ∨ ((Fb U c) U a)) ∨ G(a ∧ b)) R F(c ∧ Fb)2 1 29 18 11 1467 11 1905 10 46 9 2 667 XFā R F(b ∨ (ā ∧ Fc)) Fa ∧ XFb) R XFc) 3 1 54 34 (killed) (killed≤13) 10 149 (intmax)

Table 2 :

 2 Formulae determinized via the TBA-variant of the procedure of Dax et al.[START_REF] Dax | Mechanizing the powerset construction for restricted classes of ω-automata[END_REF].

			D R A D T B A D B A D B A m . . z e r	m i n D B A	m i n D T B A	m i n D T G B A
		m C. |Q| |Q| |Q| |Q| time |Q| time |Q| time |Q| |F| time
	(a U Xā) ∨ XG( b ∧ XFc)	2 0	10 12 10 8 8 8	8 4.2 8	3.9 6 2.3 6	0.5 6 1 0.1 6 1	3.6 1.7
	F(a ∧ GFb) ∨ (Fc ∧ Fa ∧ F(c ∧ GF b))	5 1	4 5 7 6 6 5	5 0.1 5	0.0 4 0.0 4	0.0 4 1 0.0 4 1 68.9 1.9
	GF(a ↔ XXb)	1 1	7 11 9 9 9 6	6 1.2 6	2.7 4 1.8 4	0.1 4 1 0.2 4 1	0.1 0.2
	GF(a ↔ XXXb)	1 1	15 23 17 17 17 (killed) (killed≤11) (killed≤8) (killed≤11) (killed≤8)	(killed≤8) (killed≤8)
	(GFb ∧ GFa) ∨ (GFc ∧ GFd)	4 1	5 9 13 8 8 5	5 2.2 5	2.0 4 1.5 4	0.1 1 4 25.3 1.3 1 4 406.0
	X((a M F((b ∧ c) ∨ ( b ∧ c))) W(Gc U b))	3 1	14 18 29 22 22 (killed) (killed≤12) 11 4628.4 22 1 1617.2 (killed≤12) 11 3934.0 10 3 2010.5
	X(a R(( b ∧ Fc) M Xā)) 2 0	10 12 13 13 13 10 1449.4 10 3424.5 9 52.3 8 2 37.1 10 4188.5 9 52.7 8 2 13.0
	X(G(ā M b) ∨ G(a ∨ Gā))	1 0	7 8 14 13 13 7	7 1.3 7	0.2 6 1.1 6	0.1 6 1 0.4 6 1	0.1 0.4
	XXG(Fa U Xb)	2 1	10 14 21 18 18 8 80.6 8 11.3 6 12.2 5 2 337.0 8 2.9 6 1.1 5 2 17.5

This work has been supported by the project ImpRo/ANR-2010-BLAN-0317.

Detailed results and instructions to reproduce the benchmark can be found at http://www.lrde.epita.fr/ ~adl/forte14/.

A Synthesis of Equivalent DTBA

This section gives our transition-based adaptation of Ehlers' encoding [START_REF] Ehlers | Minimising deterministic Büchi automata precisely using SAT solving[END_REF]. After giving a straightforward adaptation of his encoding to deal with DTBA instead of DBA, we list some additional optimizations we applied in our implementation.

From a reference DTBA R = Σ, Q R , ι R , δ R , F R , we give a set of constraints that ensures a candidate DTBA

We encode C with two sets of variables: -The variables { q 1 , , q 2 δ C | (q 1 , q 2 ) ∈ Q 2 C , ∈ Σ} encode the existence of transitions (q 1 , , q 2 ) ∈ δ C in the candidate automaton.

C , ∈ Σ} encode the membership of these transitions to the acceptance set F C . For the product C ⊗ R, we retain the reachable states, and parts of paths that might eventually be completed to become cycles.

-

denotes that there is an acyclic path between (q 1 , q 1 ) and (q 2 , q 2 ) in the product, such that its projection on the candidate automaton C does not visit

denotes that there is an acyclic path between (q 1 , q 1 ) and (q 2 , q 2 ) in the product, such that its projection on the reference automaton R does not visit F R . The problem is encoded as follows. The candidate automaton is complete:

The initial state of the product exists. Furthermore if (q 1 , q 1 ) is a state of the product, (q 1 , , q 2 ) ∈ δ R is a transition in the reference automaton, and (q 1 , , q 2 ) ∈ δ C is transition in the candidate automaton, then (q 2 , q 2 ) is a state of the product too:

Each state of the product corresponds to an empty path that is non-accepting in the reference and in the candidate automata:

Otherwise when one of the two transitions does not close the cycle (q 3 = q 1 ∨ q 3 = q 1 ), then the non-accepting path is prolonged:

( ,q 3 )∈δ R (q 2 ), (q 2 , ,q 3 ) ∈F R (q 3 =q 1 )∨(q3 =q1) q 1 , q 1 , q 2 , q 2 R ∧ q 2 , , q 3 δ C → q 1 , q 1 , q 3 , q 3 R (9)

If a path of the product that is non-accepting with respect to the reference automaton, is completed by a non-accepting transition (q 2 , , q 3 ) and a transition (q 2 , , q 3 ) that both closes the cycle (q 3 = q 1 ∧ q 3 = q 1 ), then (q 2 , , q 1 ) is also non-accepting:

Otherwise when one of the two transitions does not close the cycle (q 3 = q 1 ∨ q 3 = q 1 ) and the candidate transition (q 2 , , q 3 ) is non-accepting, then the non-accepting path is prolonged (note that we don't care whether (q 2 , , q 3 ) ∈ F R or not):

, ( ,q 3 )∈δ R (q 2 ), (q 3 =q 1 )∨(q3 =q1) q 1 , q 1 , q 2 , q 2 C ∧ q 2 , , q 3 δ C ∧¬ q 2 , , q 3 F C → q 1 , q 1 , q 3 , q 3 C (11)

Conversely, if a path of the product that is non-accepting with respect to the candidate automaton, is completed by an accepting transition (q 2 , , q 3 ) and a transition (q 2 , , q 3 ) that both closes the cycle (q 3 = q 1 ∧ q 3 = q 1 ), then (q 2 , , q 1 ) is also accepting:

The symmetry-breaking equation (S) of Section 4 applies here as well.

As we did in our DTGBA encoding of Sec. 4.1, variables of the form q 1 , q 1 , q 2 , q 2 C or q 1 , q 1 , q 2 , q 2 R should be limited to cases where q 1 and q 2 belong to the same SCC of R, since it is not possible to build a cycle outside an SCC. Furthermore, variables of the form q 1 , q 1 , q 1 , q 1 R or q 1 , q 1 , q 2 , q 2 C are actually superfluous. Each time we use such a variable in equations ( 9)- [START_REF] Esparza | Rabinizer: Small deterministic automata for LTL(F,G)[END_REF], we could replace it by q 1 , q 1 G . Doing so will avoid generating |Q C | × |Q R | variables, and all the clauses generated by equation [START_REF] Couvreur | On-the-fly emptiness checks for generalized Büchi automata[END_REF] which is no longer needed.