Jonathan Benchimol
email: jonathan.benchimol@essec.edu

André Fourçans
email: fourcans@essec.edu

The role of money and monetary policy in crisis periods : the Euro area case

Keywords: Euro area, Money, DSGE forecasting. JEL Classi…cation: E31, E51, E58

In this paper, we test two models of the Eurozone, with a special emphasis on the role of money and monetary policy during crises. The role of separability between money and consumption is investigated further and we analyse the Euro area economy during three di¤erent crises: 1992, 2001 and 2007. We …nd that money has a rather signi…cant role to play in explaining output variations during crises whereas, at the same time, the role of monetary policy on output decreases signi…cantly. Moreover, we …nd that a model with non-separability between consumption and money has better forecasting performance than a baseline separable model over crisis periods.

Introduction

The ability to accurately forecast the future path for macroeconomic series such as output or in ‡ation is crucial information for the business sector, government and central bank in their decision-making process. [START_REF] Christiano | DSGE Models for Monetary Policy Analysis[END_REF] show that Dynamic Stochastic General Equilibrium (DSGE) models provide valuable information about business cycle dynamics and the e¤ects of various economic shocks on the economy. For all those reasons, DSGE models are increasingly being utilized by central banks and other policy-making institutions to assist with policy decisions, as pointed by [START_REF] Edge | How useful are estimated DSGE model forecasts for central bankers ? Brookings Papers on Economic Activity[END_REF].

In policy analysis, it is believed that monetary policy has long and variable e¤ects on the overall economy. To capture such complex interactions between policy variables and the economy as a whole, macroeconomic forecasting becomes indispensable in actual policy making [START_REF] Blinder | Is There a Core of Practical Macroeconomics That We Should All Believe ?[END_REF][START_REF] Diebold | The Past, Present, and Future of Macroeconomic Forecasting[END_REF]. [START_REF] Sims | Bayesian Methods for Dynamic Multivariate Models[END_REF] introduced Bayesian methods to vector autoregressive (VAR) models to improve the accuracy of out-of-sample forecasts in a dynamic multivariate framework. They showed how to compute Bayesian probability distributions or error bands around out-of-sample forecasts. More recently, researchers have started to examine the forecasting performance of these models. In one such investigation, [START_REF] Smets | Shocks and frictions in US business cycles: a Bayesian DSGE approach[END_REF] show that a DSGE model can generate forecasts that have a lower root mean-squared deviation (RMSD) than a Bayesian Vector Autoregression (BVAR).

On the other hand, [START_REF] Edge | A comparison of forecast performance between Federal Reserve sta¤ forecasts, simple reducedform models, and a DSGE model[END_REF] show that the out-ofsample forecasting performance of the Federal Reserve Board's new DSGE model for the U.S. economy (EDO) is in many cases better than their largescale macro-econometric model (FRB/US).

In a DSGE framework applied to the Eurozone, [START_REF] Benchimol | Money and risk in a DSGE framework: A Bayesian application to the Eurozone[END_REF] show that the role of money with respect to the economy, especially on output dynamics, increases with risk aversion. Yet they don't develop a complete analysis of the role of money and of monetary policy during crisis periods. The purpose of our paper is to …ll this gap by focusing on the ‡uctuations of micro and macro parameters; on variance decompositions of variables with respect to shocks; and on output and in ‡ation forecasts.

They have shown that money has an explicit role when risk aversion is high enough, which may be the case during crisis periods. Yet, these periods do not last long. And other parameters changes in the very short term may also a¤ect the role of money and monetary policy. That is why, in the present article, we use relatively small samples for the estimations, in order to capture the impact of very short term parameters changes on the dynamics of the model.

First, we compare two types of New Keynesian models in a DSGE framework. The …rst model is a standard one whereby money is included in the utility function with a separability assumption, as in the baseline model of [START_REF] Galí | Monetary Policy, In ‡ation and the business cycle: An introduction to the new Keynesian framework[END_REF]. The second model introduces money in the utility function by assuming non-separability between real money balances and consumption as in [START_REF] Benchimol | Money and risk in a DSGE framework: A Bayesian application to the Eurozone[END_REF]. By using Bayesian techniques, we estimate these two models with Eurozone data over three di¤erent crises: during speculative attacks on currencies in the European Exchange Rate Mechanism (ERM) at the beginning of the 1990s (Black Wednesday crisis); following the bursting of the Dot-com bubble at the beginning of 2001 (Dotcom crisis) ; and during the subprime crisis from 2007 to 2010 (Subprime crisis).

Second, we analyze the results on the dynamics of the model, by studying the variations of micro and macro parameters during these crisis periods as well as the variance decomposition of the variables (notably current output, ‡exible-price output and in ‡ation) with respect to structural shocks (preference shock, technology shock, money shock and interest rate shock). We also study the forecasting performances of the two models over the periods under scrutiny. Focusing on these three periods sheds light on the speci…c role of money and monetary policy in crisis situations and leads to interesting results as to output and in ‡ation dynamics during these periods.

The results show that the role of money increases during crises. It also demonstrates that a New Keynesian model with non-separable preferences between money and consumption is able to better forecast output than a simple New Keynesian model with separable preferences during crises.

The study leads to policy implications as to the conduct of monetary policy, especially during crisis periods.

In Section 2, we present the models used for the empirical analysis presented in Section 3. We analyze the ERM crisis in Section 4, the Dot-com crisis in Section 5, and the Subprime crisis in Section 6. For each crisis, we provide estimated parameters, variance decompositions and analyse predictive properties of each model over time. We discuss the results and compare the three crises in Section 7. Section 8 concludes.

The models

These two models consist of households that supply labor, purchase goods for consumption, hold money and bonds, and …rms that hire labor and produce and sell di¤erentiated products in monopolistically competitive goods markets. Each …rm sets the price of the good it produces, but not all …rms reset their price during each period. Households and …rms behave optimally: households maximize the expected present value of utility, and …rms maximize pro…ts. There is also a central bank that controls the nominal rate of interest.

The separable baseline model

The following New Keynesian DSGE model is mainly inspired by [START_REF] Galí | Monetary Policy, In ‡ation and the business cycle: An introduction to the new Keynesian framework[END_REF], and serves as a baseline model.

Households

We assume a representative in…nitely-lived household, seeking to maximize

E t " 1 X k=0 k U t+k # (1)
where U t is the period utility function and < 1 is the discount factor. We assume the existence of a continuum of goods represented by the interval [0; 1]. The household decides how to allocate its consumption expenditures among the di¤erent goods. This requires that the consumption index C t be maximized for any given level of expenditures. Furthermore, and conditional on such optimal behavior, the period budget constraint takes the form

P t C t + M t + Q t B t B t 1 + W t N t + M t 1 (2)
for t = 0; 1; 2:::, P t is an aggregate price index, M t is the quantity of money holdings at time t, B t is the quantity of one-period nominally riskless discount bonds purchased in period t and maturing in period t + 1 (each bond pays one unit of money at maturity and its price is Q t where i t = log Q t is the short term nominal rate), W t is the nominal wage, and N t is hours of work (or the measure of household members employed).

The above sequence of period budget constraints is supplemented with a solvency condition, such as 8t lim n !1 E t [B n ] 0, in order to avoid Ponzi-type schemes. Preferences are measured with a common time-separable utility function (MIU). Under the assumption of a period utility given by

U t = e " P t C 1 t 1 + e " m t 1 # M t P t 1 # N 1+ t 1 + ! (3)
where consumption, labor, money and bond holdings are chosen to maximize (3) subject to the budget constraint (2) and the solvency condition. is the coe¢ cient of relative risk aversion of households (or the inverse of the intertemporal elasticity of substitution), # is the inverse of the elasticity of money holdings with respect to the interest rate, and is the inverse of the elasticity of work e¤ort with respect to the real wage. The utility function also contains two structural shocks: " p t is a general shock to preferences that a¤ects the intertemporal substitution of households (preference shock accounts for changes in the marginal rate of substitution between goods, real money balances and work) and " m t is a money shock (it accounts for changes in households'money holdings). and are positive scale parameters.

Firms

We assume a continuum of …rms indexed by i 2 [0; 1]. Each …rm produces a di¤erentiated good but uses an identical technology with the following production function,

Y t (i) = A t N t (i) 1 (4)
where A t = exp (" a t ) is the level of technology assumed to be common to all …rms and to evolve exogenously over time, " a t is the technology shock, and is the measure of decreasing returns.

All …rms face an identical isoelastic demand schedule, and take the aggregate price level P t and aggregate consumption index C t as given. As in the standard [START_REF] Calvo | Staggered prices in a utility-maximizing framework[END_REF] model, our generalization features monopolistic competition and staggered price setting. At any time t, only a fraction 1 of …rms, with 0 < < 1, can reset their prices optimally, while the remaining …rms index their prices to lagged in ‡ation.

Central bank

Finally, the model is closed by adding the monetary policy smoothed Taylortype reaction function:

{t = (1 i ) (^ t ) + x ŷt ŷf t + i {t 1 + " i t (5)
where and x are policy coe¢ cients re ‡ecting the weight on in ‡ation and on the output gap; the parameter 0 < i < 1 captures the degree of interest rate smoothing. " i t is an exogenous ad hoc shock accounting for ‡uctuations of nominal interest rate.

Solution

The solution of this model leads to six equations with six variables: ‡exibleprice output (ŷ (1 ) + + (6)

^ t = E t [^ t+1 ] + (1 ) (1 ) ( (1 ) + + ) (1 + ") ŷt ŷf t (7) ŷt = E t [ŷ t+1 ] 1 ({ t E t [^ t+1 ] c ) 1 E t " p t+1 (8) c mp t = # ŷt a 2 # {t m # + 1 # " m t (9) {t = (1 i ) (^ t ) + x ŷt ŷf t + i {t 1 + " i t ( 10
)
where

m = log ( ) + a 1 n = log ( ) c = log ( ) with a 1 = log 1 e 1 1 e 1 1 and a 2 = 1 e 1 1
.

" m t is the shock on real money balances, " p t is the shock preferences, " i t is the exogenous component of the interest rate and " a t is the technology shock.

The non-separable model

As in the previous model the representative in…nitely-lived household seeks to maximize

E t " 1 X k=0 k U t+k # (11)
Now, the period utility function U t is such as:

U t = e " p t 0 @ 1 1 (1 b) C 1 t + be " m t M t P t 1 ! 1 1 1 + N 1+ t 1 A (12
) where consumption, labor, money and bond holdings are chosen to maximize (11) subject to the same budget constraint and the same solvency condition as in the baseline model. This CES utility function depends positively on the consumption of goods, C t , positively on real money balances, M t =P t , and negatively on labour N t , as in the baseline model.

is the inverse of the elasticity of money holdings with respect to the interest rate, and can be seen as a non separability parameter. b and are positive scale parameters. We use the same production function and Taylor rule as in the baseline model.

This New Keynesian DSGE model was developed in [START_REF] Benchimol | Money and risk in a DSGE framework: A Bayesian application to the Eurozone[END_REF]. As in the …rst model, it leads to six equations with six macro variables: ‡exible-price output (ŷ f t ), ‡exible-price real money balances ( c mp f t ), in ‡ation (^ t ), output (ŷ t ), nominal interest rate ({ t ), and real money balances ( c mp t ), such as

ŷf t = y a ât + y m c mp f t y c + y sm " M t (13) c mp f t = m y+1 E t h ŷf t+1 i + m y ŷf t + 1 " M t ( 14
)
^ t = E t [^ t+1 ] + x ŷt ŷf t + m c mp t c mp f t (15) ŷt = E t [ŷ t+1 ] r ({ t E t [^ t+1 ]) + mp E t c mp t+1 (16)
+ sp E t " P t+1 + sm E t " M t+1 c mp t = ŷt i {t + 1 " M t (17) {t = (1 i ) ^ t + x ŷt ŷf t + i {t 1 + " i t ( 18
)
where

y a = 1+ ( ( )a 1 )(1 )+ + y m = (1 )( )(1 a 1 ) ( ( )a 1 )(1 )+ + y c = log " " 1 1 ( ( )a 1 )(1 )+ + y sm = ( )(1 a 1 )(1 ) (( ( )a 1 )(1 )+ + )(1 ) m y+1 = a 2 ( ( ) a 1 ) m y = 1 + a 2 ( ( ) a 1 ) x = ( ) a 1 + + 1 (1 ) (1 ) (1 )
(1

+ ") m = (1 ) (1 ) ( ) (1 a 1 ) (1 ) (1 + ") r = 1 a 1 ( ) mp = ( )(1 a 1 ) a 1 ( ) sp = 1 a 1 ( ) sm = (1 a 1 )( ) ( a 1 ( ))(1 ) i = a 2 with a 1 = 1 1+(b=(1 b)) 1= (1 ) ( 1)= and a 2 = 1 exp(1= ) 1 .
As we assume that households get utility from holding money, these two models include money in the utility function. The baseline model considers separability between consumption and real money balances, as is generally the case in the literature. In this case, real money balances are irrelevant in explaining the dynamics of the model, due to this separability condition. Consequently the money equation ( 9) becomes completely recursive from the rest of the system. In that case, money has no role to play in the equations explaining the other variables of the model (equations 6, 7, 8 and 10).

The second model introduces non-separability between consumption and real money balances in order to analyse the situation where the marginal rate of substitution between current and future consumption depends on current and future real money balances. In that case money enters explicitly in the equations that determine output (current output and its ‡exible-price counterpart) and in ‡ation (equations 13, 15 and 16). This results from the fact that consumption and money being linked in the agents utility function, money enters the equations where output appears, insofar Y t = C t at equilibrium.

Empirical results

Data

In our Eurozone model, ^ t is the log-linearized in ‡ation rate measured as the yearly log di¤erence of GDP de ‡ator from one quarter to the same quarter of the previous year, ŷt is the log-linearized output measured as the yearly log di¤erence of GDP from one quarter to the same quarter of the previous year, and {t is the short-term (3-month) nominal interest rate. These data are extracted from the Euro area Wide Model database (AWM) of [START_REF] Fagan | An area-wide model (AWM) for the Euro area[END_REF]. c mp t is the log-linearized real money balances measured as the yearly log di¤erence of real money from one quarter to the same quarter of the previous year, where real money is measured as the log di¤erence between the money stock and the GDP De ‡ator. We use the M 3 monetary aggregate from the OECD database. ŷf t , the ‡exible-price output, and c mp f t , the ‡exible-price real money balances are completely determined by structural shocks.

Bayesian estimations

We study three di¤erent crisis periods: 1990Q1 to 1993Q4, during the speculative attacks on currencies in the European Exchange Rate Mechanism (Black Wednesday crisis); 2000Q1 to 2003Q4, during the burst of the Dotcom bubble (Dot-com crisis); and 2006Q1 to 2009Q4, during the Subprime's crisis.

Calibration of the models is explained in Appendix 9.A and all the marginal densities are presented in Appendix 9.B.

Each period is of 16 quarters. For every quarter of each period we run a Bayesian estimation by using the 25 observations before each respective quarter. We thus obtain 16 Bayesian estimations for each period of analysis.

Our purpose here is not to present all these results, a very cumbersome task indeed1 . What is of interest is to draw from these estimations the evolution of the micro and macro parameters, the unconditional variance decomposition of variables with respect to shocks and the forecasting performance of the two models.

Methodology

The above estimations provide the values of micro and macro parameters through time. These parameters explain the dynamics of the di¤erent variables during the crises under consideration.

The estimated micro parameters on which we concentrate are the risk aversion coe¢ cient, the Taylor rule coe¢ cients, the measure of decreasing returns, and the probability of …rms that reoptimize optimally their price every period. The other parameters are calibrated.

Several key macro-parameters of the non-separable model are also analyzed, such as: the parameter of the gap between real money balances and its ‡exible-price counterpart on in ‡ation ( m ); the expected real money growth shock parameter on output ( sm ); the expected real money growth parameter on output ( mp ); the ‡exible-price real money parameter on ‡exible-price output ( y m ); and the money shock parameter on ‡exible-price output ( y sm ). Other common macro-parameter of the two models are analyzed, notably the real interest rate parameter on output ( r ) and the technology shock parameter on ‡exible-price output ( y a ). The successive estimations and simulations lead to variance decompositions of variables with respect to shocks. In order to study the role of each shock on the variance of the variables, we analyze the unconditional variance decomposition of output, in ‡ation, interest rate and real money balances with respect to the preference shock (" P t ), the technology shock (" a t ), the money shock (" M t ) and the interest rate shock (" i t ). This analysis reveals the potential role of money and monetary policy, but also of technology and preferences on the dynamics of the system.

Finally, after each estimation, we run out-of-sample (over four periods, i.e. one year) DSGE forecasts in order to compare the forecasting performance of the two models. To conduct these forecasting exercises, we simulate our estimated models from a given state and analyze the trajectories of the forecasted endogenous variables for the baseline model and the non-separable money model. These forecasting exercises are done following the Metropolis-Hastings iterations, on the basis of the posterior means of each estimated variables. The main objective of this exercise is to compare the forecasts to the actual data. Then, a comparison of the two models' forecasts is provided by the calculation of the Root Mean Square Deviation (RMSD).

To illustrate the prediction performance of our DSGE models, we perform sixteen out-of-sample prediction over the three crises.

In order to evaluate the forecasting performances, the models are re-estimated every quarter, by taking twenty …ve observations before a given quarter, and this for each of the sixteen quarters of a crisis period. For each four out-of-sample forecast, we calculate the sum of the corresponding RMSD values, and compare these values between the two models.

4 European Exchange Rate Mechanism crisis

Parameters analysis

The results of the Bayesian estimates are summarized in the following …gures, where each date corresponds to the end of each estimation sample (of twenty …ve observations). In all the …gures, the dashed line refers to the non-separable model while the solid line refers to the baseline model. Figure 1 shows the evolution of micro and macro-parameters. Even though these values do not change much in absolute terms, such small vari-ations may be enough to explain changes in the dynamic impact of shocks on variables and on the overall interdependent system of equations over time.

A closer look at the value of these parameters shows that risk aversion, the expected money growth parameter on output, the expected money growth shock parameter on output, and the in ‡ation and output coe¢ cients of the Taylor rule, display a small peak in 1992Q1.

Moreover, after the Black Wednesday crisis (i.e. after 1993Q1), more …rms choose to reoptimize optimally their prices. During the period, the real interest rate parameter on output and the technology shock parameter on ‡exible-price output are rather constant.

There does not exist wide di¤erences between both models as to the dynamics of the parameters estimations.

Variance decomposition

For each Bayesian estimation of the two models, we compute the unconditional variance decomposition of the variables. This variance decomposition gives interesting information as to the role of each shock. Figure 2 shows that money plays a non-negligible role in output variations during the European Monetary System crisis. This role reaches its maximum in 1991Q4, where about 10% of the output's variance is explained by the money shock. This result is mainly due to the variation in the expected money growth parameter and in the expected money growth shock parameter on output (see Figure 1). After and before the crisis, money seems to play a less signi…cant role. We don't present the role of money on in ‡ation as far as it is almost nil (less than 0.1%).

Figure 2 also shows that the role of monetary policy on output and in ‡ation decreases by the end of the crisis, and that technology plays a lower role during the crisis, especially as far as ‡exible-price output is concerned.

Shocks on output from money, monetary policy, technology and prefer-ences explain 100% of the output variance. The role of technology increases after 1993Q1, at the same time as the role of monetary policy, of money and of preferences decrease. The role of preferences on interest rates and in ‡ation increases after the crisis (this role is negligible on real money balances) whereas it decreases on output.

Forecasting performances

From each Bayesian estimation, we simulate the out-of-sample forecasts of output and in ‡ation over the next four periods (one year). A negative number implies that the non-separable money model's RMSD is higher than the baseline model's RMSD. In that case the baseline model has better forecasting performances than the non-separable model. Figure 3 shows that the model with non-separability demonstrates a better predictive power for output dynamics than the baseline model between 1990Q2 and 1991Q2 and during the speculative attacks on currencies in the European Exchange Rate Mechanism between 1992Q2 and 1992Q4.

From 1990Q1 to 1991Q2, the non-separable model has a better predictive power of in ‡ation dynamics whereas the performances are mixed during the other periods.

Interpretation

Black Wednesday refers to the events of 16 September 1992 when the British Conservative government withdrawed the pound sterling from the European Exchange Rate Mechanism. Yet other crises occurred during our period of analysis.

From 1990Q2 to 1991Q2, an oil crisis followed the …rst Gulf war2 . From 1992Q2 to 1992Q4, the Russian crisis3 and the French Real Estate crisis4 could have a¤ected the Eurozone business cycle. Figure 1 shows that during this period several parameters reach a peak.

Figure 2 shows that from 1990Q3 on the impact of money on (current and ‡exible-price) output increases and remains at a higher level until about the end of the period. This impact is higher than what [START_REF] Ireland | Money's role in the monetary business cycle[END_REF] and [START_REF] Andrés | Money in an estimated business cycle model of the Euro area[END_REF] found. The reason for this result seems mainly due to the variation of the expected money growth parameter and of the expected money growth shock parameter on output (Figure 1).

Figure 2 also indicates that, since 1992Q4, the beginning of the ERM crisis, the role of monetary policy on output and in ‡ation has decreased and reached its lowest level at the top of the crisis (1993Q3).

The RMSD errors comparison (Figure 3) and the business cycles of the period are anticorrelated, showing that the non-separable model has a better predictive power of output than the baseline model during the lower part of the cycle. Moreover, during the Black Wednesday period (after 1992Q2), and during the other crises mentioned above (from 1990Q2 to 1991Q2), the non-separable model demonstrates a better predictive power of output than over the other periods.

These …ndings con…rm the predictive abilities of the non-separable model during crisis periods, whereby the role of money on output increases.

Dot-com crisis

Parameters analysis

The following …gure presents the Bayesian estimation results of micro and macro parameters through time during the Dot-com crisis (2000Q1 to 2003Q4). Figure 4 shows that if the risk aversion parameter does not change much over the period, at least in absolute terms, it gets to a peak whenever troubles happen: around 2000Q4 when the internet bubble started to burst and in 2001Q3 around the time of the 9/11 terrorist attacks.

In absolute terms the other parameters do not change much either even though the money related parameters on output (current and its ‡exibleprice counterpart) show also a peak in 2000Q4 and remain at a somewhat higher level over the rest of the period. model is the best (the RMSD di¤erences of the in ‡ation forecasts are rather small).

Interpretation

The bursting of the Dot-com bubble occurs in the Eurozone approximately two quarters (2000Q4) after the United States (2000Q2). Even if the role of money on output before 2001Q4 is small, it increases after this date. Between 2001Q1 and 2001Q4, the core of the Dot-com crisis, the role of technology on output reaches its minimum. This result con…rms the decreasing role of technology on output dynamics during this crisis.

The percentage of the variance of output and ‡exible price-output explained by the money shock is small and close to the value found by [START_REF] Andrés | Money in an estimated business cycle model of the Euro area[END_REF]. Moreover, although the Taylor rule coe¢cients are rather constant (Figure 4), the role of monetary policy on output and in ‡ation has increased since the beginning of the period (Figure 5).

The clear dominance of the non-separable model over the baseline model in terms of output forecasting errors con…rms the predictive abilities of the non-separable model during crisis periods.

6 Subprime crisis

Parameters analysis

The following …gures present the Bayesian estimation results through time over the subprime crisis (2006Q1 to 2009Q4). Figure 7 shows that after the Lehman Brother's bankruptcy (2008Q4), the risk aversion parameter decreases, whatever the model.

The expected money growth shock parameter on output reaches its maximum in 2008Q3 whereas the other parameters of output and ‡exible-price output remain rather stable during the period.

The money growth parameter on in ‡ation also reaches its maximum in 2008Q3, but its variations are not large.

Even if the variations are small, the weights on in ‡ation and on output in the Taylor rule reach a peak in 2007Q4 and in 2008Q4, while the smoothing parameter reaches on the contrary its lowest values. Figure 8 shows that the role of the money shock on output increases in 2007 and reaches a peak in 2008Q2. This shock explains around 5% of the variance in 2006Q4, whereas the percentage increases to 12% in 2008Q2, and goes back to 4% in 2009Q4. The impact of money on the ‡exible-price output follows about the same dynamic path.

Variance decomposition

As in the other crises, and because it is insigni…cant, we don't represent the role of money on in ‡ation.

It is interesting to notice that the impact of monetary policy on output and in ‡ation follows the same pattern as with the money shock, but it gets its higher level a little earlier (2007Q1). Monetary policy explains most of the in ‡ation variance, with a maximum in 2007Q3.

Figure 8 also shows that the role of preferences on output, interest rates, and real money balances is lower during the crisis than before and after the crisis. Technology has a lower role in explaining ‡exible-price output variance at the beginning of the crisis than before and after the crisis. The role of technology on output and in ‡ation grows up signi…cantly after the crisis.

A simultaneous analysis of all the shocks indicates that the increasing role of money on output is associated with a decline in the role of monetary policy and of preferences. These declining impacts start at the beginning of the subprime crisis. Figure 9 shows that the non-separable model provides better forecasts of output than the baseline model at the core of the …nancial crisis (2007Q2 to 2008Q3). The in ‡ation RMSDs are about the same over the period.

Forecasting performances

Interpretation

The subprime crisis can be attributed to a number of factors pervasive in both housing and credit markets, factors which emerged over a number of years. For [START_REF] Cecchetti | Crisis and responses: The Federal Reserve in the early stages of the …nancial crisis[END_REF] and [START_REF] Mishkin | Over the cli¤: From the Subprime to the Global Financial Crisis[END_REF], a complete chronology of the crisis might starts in 2007Q1 when several large subprime mortgage lenders started to report losses. The real trigger of the crisis was in 2007Q3 when the French bank BNP Paribas temporarily halted redemptions from three of its funds that held assets backed by U.S. subprime mortgage debt.

As a direct consequence, credit spreads began widening, overnight interest rates in Europe shot up, and the European Central Bank immediately responded with the largest short-term liquidity injection in her nine year history. Furthermore, if the global …nancial crisis began in 2007 in the US, the Eurozone entered its …rst o¢ cial recession in 2008Q3.

The Euro Group heads of states and governments and the European Central Bank (ECB) held an extraordinary summit in October 2008 to de…ne a joint action for the Eurozone. They agreed on a bank rescue plan which would involve hundreds of billions of euros: governments would enter banks capital and guarantee interbank lending. That may explain the decrease in risk aversion after 2008Q4 (Figure 7), and the decreasing role of money on output variations after this date.

These results also suggests that at the top of the crisis, the role of money is at its highest. Contrary to [START_REF] Ireland | Money's role in the monetary business cycle[END_REF] and [START_REF] Andrés | Money in an estimated business cycle model of the Euro area[END_REF], it shows that money had a signi…cant role to play during the …nancial crisis.

To understand better the relationship between the role of money and …nancial risk, it is interesting to introduce the evolution of the interest rate spread over the period. This spread5 provides an assessment of counterparty risk from one bank lending to another, re ‡ecting both liquidity and credit risk concerns.

As Figure 10 shows, the dynamics of the role of money on output during the crisis is positively related to the widening of the spread between the Euribor and both baselines interest rates (Bubill and BTF). In the same vein, Figure 11 shows that the role of monetary policy decreases as the same time as the spread increases. If the role of monetary policy is at its maximum before the crisis starts (2007Q2), it diminishes quickly after: its impact on output is divided by four, declining from 40% to about 10%.

The RMSD analysis also reveals that the DSGE model with non-separable utility fares quite well against the baseline model after 2007Q2, that is after the beginning of the Global Financial Crisis (GFC). Given the stability of the macro parameters (Figure 7), it can be inferred that this increasing role is mainly due to micro parameters variations such as variations of the risk aversion parameter ( ) or of the percentage of …rms reoptimizing their prices ( 1).

A comparison of the three crises

To better assess the relationship between money, monetary policy and output during the crises under consideration, and to better understand the respective role of the shocks, a comparison of variance decompositions between the di¤erent crises is useful. For the Subprime crisis and the European Exchange Rate Mechanism crisis, money plays a more signi…cant role on output (more than 10%) than during the Dot-com crisis (less than 4%). These values must be compared to [START_REF] Ireland | Money's role in the monetary business cycle[END_REF], [START_REF] Andrés | Money in an estimated business cycle model of the Euro area[END_REF] and [START_REF] Andrés | Money and the natural rate of interest: Structural estimates for the United States and the Euro area[END_REF], which found that money's role in the business cycle appears limited. Money plays a stronger role during the Subprime crisis (12.5%) than during the other crises. Similarly, money plays a stronger role on ‡exible-price output at the beginning of the Subprime crisis (16.5%) than during the other crises, where the money shock contribution to the ‡exible-price output variance is about 13% in 1992Q1 (beginning of the ERM crisis) and about 5% in 2002Q1 (Dot-com crisis).

The period where the role of technology on ‡exible-price output is at its minimum seems to be at the peak of the crisis, and this for the three crises. This result means probably that technology has a lower role to play in explaining ‡exible-price output during crisis than during more normal periods where ‡exible-price output variability is completely determined by the technology shock. The decline of the role of technology on ‡exible-price output is furthermore associated with a corresponding increase of the role of money on ‡exible-price output.

Preferences seems to play a role on all variables only during the subprime crisis, and this for both models. The preference shock has a signi…cant impact on output and interest rates before the Subprime crisis, yet this impact diminishes during the crisis (divided by almost two). This behavior may be due to the importance of the role of money, especially during the Global Financial Crisis.

It is also interesting to note that over the three crisis, the impact of monetary policy on output is di¤erent. It is around 35% at the top of the Dot-com crisis whereas it reaches almost 50% at the top of the ERM and of the Subprime crisis.

The impact of monetary policy on in ‡ation is also di¤erent over the three crises. It appears to be lower during the ERM crisis and the Dot-com crisis than during the Subprime crisis.

Finally, in terms of forecasting, the non-separable model performs generally better than the separable one, as shown in Figure 3, 6 and 9.

Conclusion

The goal of this paper was to study the role of money and monetary policy during crises periods. To achieve this goal, we compared the performance of two DSGE models, one baseline model with separable preferences, as in [START_REF] Galí | Monetary Policy, In ‡ation and the business cycle: An introduction to the new Keynesian framework[END_REF], and one with non-separable preferences between consumption and real money balances, as in [START_REF] Benchimol | Money and risk in a DSGE framework: A Bayesian application to the Eurozone[END_REF]; the study is carried over three crisis periods: European ERM crisis (1992), Dot-com crisis (2001) and Subprime crisis (2007).

We tested the two models by using successive Bayesian estimations, so as to obtain empirical estimates of the evolution of parameters, variance decomposition and forecasting performances of both models over the three crises. Our analysis shows that the role of money on output variations increases during crises. Yet this role was higher during the ERM and the Subprime crises than during the Dot-com crisis. It also demonstrates that the model with non-separable preferences provides better forecasts of output than with the baseline model over these crisis periods.

Moreover, our results show that the impact of monetary policy on output variability diminishes signi…cantly during the Subprime crisis, at the same time as the impact of money increases. In ‡ation does not seem to be a¤ected directly by money variables, it is mainly explained by monetary policy over the three crises.

Our …ndings support the view that New Keynesian DSGE models with non-separability between consumption and real money balances should be preferred to separable models, as far as macroeconomic forecasting is concerned, at least during crisis periods.

Our results provide also interesting clues regarding the structural dynamics of the economy that may help inform central banks, markets and policy regulators. For example, the more signi…cant role played by real money balances than generally expected during …nancial crises.

All in all, our analysis has highlighted the importance of money during crises, and showed that the hypothesis of non-separability between money and consumption leads to better forecast during these periods than when money and consumption are taken as separable.

Appendix

A Calibration

We calibrate all parameters, excepted shocks'parameters ( k and k for k = fp; m; i; ag), the risk aversion parameter ( ), the price adjustment parameter ( ), the decreasing return parameter ( ) of the production function and the Taylor rule's parameters ( i , , x ). The monetary policy rule is an ad-hoc reaction function and completely dependent on the monetary authority.

Following standard conventions, we calibrate beta distributions for parameters that fall between zero and one, inverted gamma distributions for parameters that need to be constrained to be greater than zero, and normal distributions in other cases.

The calibration of is inspired by [START_REF] Rabanal | Comparing new Keynesian models of the business cycle: A Bayesian approach[END_REF] and by [START_REF] Casares | Monetary policy rules in a new Keynesian Euro area model[END_REF]. They choose, respectively, a risk aversion parameter of 2:5 and 1:5. In line with these values, we consider that = 2 corresponds to a standard risk aversion. We adopt the same priors in both models with the same risk aversion calibration.

As in [START_REF] Smets | Shocks and frictions in US business cycles: a Bayesian DSGE approach[END_REF], the standard errors of the innovations are assumed to follow inverse gamma distributions and we choose a beta distribution for shock persistence parameters (as well as for the backward component of the Taylor rule) that should be lesser than one.

The calibration of , , , , and " comes from [START_REF] Galí | Monetary Policy, In ‡ation and the business cycle: An introduction to the new Keynesian framework[END_REF] and [START_REF] Casares | Monetary policy rules in a new Keynesian Euro area model[END_REF]. The smoothed Taylor rule ( i , , and x ) is calibrated following Gerlach-Kristen ( 2003), analogue priors as those used by [START_REF] Smets | An Estimated Dynamic Stochastic General Equilibrium Model of the Euro Area[END_REF]. In order to take into consideration possible changes in the behavior of the central bank, we assign a higher standard error for the Taylor rule's coe¢ cients. v (the non-separability parameter) must be greater than one. i (equation 17) must be greater than one as far as this parameter depends on the elasticity of substitution of money with respect to the cost of holding money balances, as explained in [START_REF] Söderström | Targeting in ‡ation with a role for money[END_REF]; while still informative, this prior distribution is dispersed enough to allow for a wide range of possible and realistic values to be considered (i.e. > v > 1).

The calibration of the shock persistence parameters and the standard errors of the innovations follows [START_REF] Fève | In ‡ation target shocks and monetary policy inertia in the Euro area[END_REF], where a much lower mean is adopted for a . All the standard errors of shocks are assumed to be distributed according to inverted Gamma distributions, with prior means of 0.02. The latter law ensures that these parameters have a positive support. The autoregressive parameters are all assumed to follow Beta distributions. Except for technology shocks, all these distributions are centered around 0.75. We take a common standard error of 0.1 for the shock persistence parameters, as in [START_REF] Smets | An Estimated Dynamic Stochastic General Equilibrium Model of the Euro Area[END_REF].

Figure 1 :

 1 Figure 1: Parameters variations (1990Q1 to 1993Q4)

Figure 2 :

 2 Figure 2: Variance decomposition in percent (1990Q1 to 1993Q4)

Figure 3 :

 3 Figure 3: Out-of-sample forecasting errors (DSGE Forecast)

Figure 4 :

 4 Figure 4: Parameters variations (2000Q1 to 2003Q4)

Figure 6 :

 6 Figure 6: Out-of-sample forecasting errors (DSGE Forecast)

Figure 7 :

 7 Figure 7: Parameters variations (2006Q1 to 2009Q4)

Figure 8 :

 8 Figure 8: Variance decomposition in percent (2006Q1 to 2009Q4)

Figure 9 :

 9 Figure 9: Out-of-sample forecasting errors (DSGE Forecast)

Figure 10 :

 10 Figure 10: Comparison between the role of money on output (variance decomposition) and the spreads between the Bubill/BTF and the Euribor

Figure 11 :

 11 Figure 11: Comparison between the role of monetry policy on output and the spreads between Bubill/BTF and Euribor

Table 1 :

 1 Calibration for the two models

		Priors
		Law	Mean Std.
		beta	0.33	0.05
		beta	0.66	0.05
		normal	2.00	0.10
		calibrated	0.99
	v	calibrated	1.50
	b	calibrated	0.25
		calibrated	0.05
		calibrated	0.05
		calibrated	1.00
	"	calibrated	6.00
	i	beta	0.50	0.10
		normal	3.00	0.20
	x	normal	1.50	0.20
	a	beta	0.75	0.10
	i	beta	0.75	0.10
	p	beta	0.75	0.10
	m	beta	0.75	0.10
	a	invgamma	0.02	2.00
	i	invgamma	0.02	2.00
	P	invgamma	0.02	2.00
	M	invgamma	0.02	2.00

All the results can however be provided upon request.

The 1990 oil price spike occurred in response to the Iraqi invasion of Kuwait on August 2, 1990. The war lasted until February 28, 1991.

The constitutional crisis of 1993 was a political stand-o¤ between the Russian president and the Russian parliament that was resolved by using military force.

From 1992 to 1996, real estate prices declined up to 40%.

The spread is measured as the di¤erence between the 3-month Euribor and a short maturity bond. As an European bond does not exist, we choose the 3-month BTF (France) and the 1-Year Bubill (Germany) as short-term Treasury bills.

Variance decomposition

The following …gure presents the variance decomposition of variables through time during the Dot-com crisis (2000Q1 to 2003Q4). Figure 5 shows that since 2001Q2, the role of money on output and on ‡exible-price output has increased. However, this role is rather minor. As in the ERM crisis, the role of money on in ‡ation is negligible (not presented).

After the bubble bursting, i.e. mainly after 2000Q4, the role of monetary policy on in ‡ation increases whereas the change is not visible on output.

As in Figure 2, Figure 5 also shows that technology plays a lower role in explaining current and ‡exible-price outputs during the crisis.

Forecasting performances

Figure 6 shows that the non-separable model is signi…cantly better than the baseline model over the whole period (except in 2000Q2), in terms of predicting output. In terms of in ‡ation, it is di¢ cult to discriminate which

B Marginal densities

In what follows, we present all the marginal densities of our estimates. The dashed line refers to the non-separable model while the solid line refer to the baseline model. For the three crises, both models have approximately the same log marginal densities.


Pierre Grangeat

Pascal Szacherski

Laurent Gerfault

Jean-François Giovannelli

Bayesian hierarchical reconstruction of protein profiles including a digestion model

Introduction :

Mass spectrometry approaches are very attractive to detect protein panels in a sensitive and high speed way. MS can be coupled to many proteomic separation techniques. However, controlling technological variability on these analytical chains is a critical point. Adequate information processing is mandatory for data analysis to take into account the complexity of the analysed mixture, to improve the measurement reliability and to make the technology user friendly. Therefore we develop a hierarchical parametric probabilistic model of the LC-MS analytical chain including the technological variability. We introduce a Bayesian reconstruction methodology to recover the protein biomarkers content in a robust way. We will focus on the digestion step since it brings a major contribution to technological variability.

Method :

In this communication, we introduce a hierarchical model of the LC-MS analytical chain. Such a chain is a cascade of molecular events depicted by a graph structure, each node being associated to a molecular state such as protein, peptide and ion and each branch to a molecular processing such as digestion, ionisation and LC-MS separation. This molecular graph defines a hierarchical mixture model. We extend the Bayesian statistical framework we have introduced previously [START_REF] Strubel | 29th IEEE EMBS Conference[END_REF] to this hierarchical description. As an example, we will consider the digestion step. We describe the digestion process on a pair of peptides within the targeted protein as a Bernoulli random process associated with a cleavage probability controlled by the digestion kinetic law.

Preliminary data :

In order to produce simulated data, we consider the experimental framework described in [START_REF] Grangeat | 58th ASMS Conference on Mass Spectrometry[END_REF] applied to human NSE combining immunoenrichment, trypsin digestion and LC-MS analysis on an Orbitrap. PSAQ quantification is performed spiking an isotopically-labeled version of NSE [START_REF] Brun | [END_REF]. We define 5 amounts of unlabeled NSE from 0 to 400 ng/ml within 1 ml serum samples. We analyze 2 peptides assuming artificially that there exists a miscleavage delivering a molecule combining both peptides. Technological variability is introduced by considering variation of 10% on LC retention time and 30% on MS ionisation gain. Variability on digestion is induced in particular by temperature and pH [START_REF] Finehout | Bayesian hierarchical inversion, technological variability, digestion model, robust protein quantification[END_REF]. We model the digestion coefficient linking protein and peptides content as a constant yield weighted by the Bernoulli parameter p for the cleaved peptides and parameter 1-p for the miscleaved molecule. We make this parameter varying between 0.4 and 1, but we assume its value to be known. Two data processing strategies are studied. Firstly, the digestion variability is ignored and the protein content is estimated from the 2 cleaved peptides. Secondly, the miscleaved molecule is introduced and the digestion variability is monitored. Parameters are estimated within the Bayesian hierarchical reconstruction. 321 spectrograms are simulated in order to compare the performances of the two strategies. Coefficient of variation of estimated concentrations is computed for first (CV1) and second strategy (CV2). The ratio CV2/CV1 is respectively 0.8, 0.7, 0.7, 0.2, 0.05 for concentrations of 0, 50, 100, 200 and 400 ng/ml, demonstrating a significant improvement for the largest concentrations.


Blaise Genest

Hugo Gimbert

Anca Muscholl

Igor Walukiewicz

Optimal Zielonka-Type Construction of Deterministic Asynchronous Automata

Asynchronous automata are parallel compositions of finitestate processes synchronizing over shared variables. A deep theorem due to Zielonka says that every regular trace language can be represented by a deterministic asynchronous automaton. In this paper we improve the construction, in that the size of the obtained asynchronous automaton is polynomial in the size of a given DFA and simply exponential in the number of processes. We show that our construction is optimal within the class of automata produced by Zielonka-type constructions. In particular, we provide the first non trivial lower bound on the size of asynchronous automata.

Introduction

Zielonka's asynchronous automata [START_REF] Zielonka | Notes on finite asynchronous automata[END_REF] is probably one of the simplest, and yet rich, models of distributed computation. This model has a solid theoretical foundation based on the theory of Mazurkiewicz traces [START_REF] Mazurkiewicz | Concurrent Program Schemes and their Interpretations[END_REF][START_REF] Diekert | The Book of Traces[END_REF]. The key property of asynchronous automata, known as Zielonka's theorem, is that every regular trace language can be represented by a deterministic asynchronous automaton [START_REF] Zielonka | Notes on finite asynchronous automata[END_REF]. This result is one of the central results on distributed systems and has been applied in many contexts. Its complex proof has been revisited on numerous occasions (see e.g. [START_REF] Cori | Asynchronous mappings and asynchronous cellular automata[END_REF][START_REF] Diekert | Construction of asynchronous automata[END_REF][START_REF] Mukund | Gossiping, Asynchronous Automata and Zielonka's Theorem[END_REF][START_REF] Mukund | Keeping Track of the Latest Gossip in a Distributed System[END_REF][START_REF] Genest | Constructing Exponential-Size Deterministic Zielonka Automata[END_REF] for a selection of such papers). In particular some significant complexity gains have been achieved since the original construction. This paper provides yet another such improvement, and moreover it shows that the presented construction is in some sense optimal.

The asynchronous automata model is basically a parallel composition of finite-state processes synchronizing over shared (state) variables. Zielonka's theorem has many interpretations, here we would like to consider it as a result about distributed synthesis: it gives a method to construct a deterministic asynchronous automaton from a given sequential one and a distribution of the actions over the set of processes. We remark that in this context it is essential that the construction gives a deterministic asynchronous automaton: for a controller it is the behaviour and not language acceptance that is important. The result has applications beyond the asynchronous automata model, for example it can be used to synthesize communicating automata with bounded communication channels [START_REF] Mukund | Synthesizing distributed finite-state systems from MSCs[END_REF][START_REF] Henriksen | A Theory of Regular MSC Languages[END_REF] or existentially-bounded channels [START_REF] Genest | A Kleene theorem and model checking algorithms for existentially bounded communicating automata[END_REF]. Despite these achievements, from the point of view of applications, the biggest problem of constructions of asynchronous automata is considered to be their high complexity. The best constructions give either automata of size doubly exponential in the number of processes, or exponential in the size of the sequential automaton. This paper proposes an improved construction of deterministic asynchronous automata. It offers the first algorithm that gives an automaton of size polynomial in the size of the sequential automaton and exponential only in the number of processes. We show that this is optimal for Zielonka-type constructions, namely constructions where each component has complete information about its history. For this we introduce the notion of locally rejecting asynchronous automaton and remark that all Zielonka-type constructions produce this kind of automata. To be locally rejecting means that a process should reject as soon as its history tells him that there is no accepting extension. We believe that a locally rejecting behavior is quite desirable for applications, such as monitoring or control. We show that when transforming a deterministic word automaton to a deterministic locally rejecting automaton, the exponential blow-up in the number of components is unavoidable. Thus, to improve our construction one would need to produce automata that are not locally rejecting.

For the upper bound we start from a deterministic (I-diamond) word automaton. We think that this is the best point of departure for a study of the complexity of constructing asynchronous automata: considering non deterministic automata would introduce costs related to determinization. The size of the deterministic asynchronous automaton obtained is measured as the sum of the sizes of the local states sets. It means that we do not take global accepting states into account. This is reasonable in our opinion, as it is hardly practical to list these states explicitly. From a deterministic I-diamond automaton A and a distributed alphabet with process set P, we construct a deterministic asynchronous automaton of size 4 |P| 4 • |A| |P| 2 . We believe that this complexity, although exponential in the number of processes, is interesting in practice: an implementation of such a device needs only memory of size logarithmic in |A| and polynomial in |P|. We also show that computing the next state on-the-fly can be done in time polynomial in both |A| and |P|.

Related work.

Besides general constructions of Zielonka type, there are a couple of different constructions, however they either apply to subclasses of regular trace languages, or they produce non deterministic automata (or both). The first category includes [START_REF] Métivier | An algorithm for computing asynchronous automata in the case of acyclic non-commutation graph[END_REF][START_REF] Diekert | Construction of asynchronous automata[END_REF], that provide deterministic asynchronous cellular automata from a given trace homomorphism in case that the dependence alphabet is acyclic and chordal, respectively. These constructions are quite simple and only polynomial in the size of the monoid (thus still exponential in the size of a DFA). In the second category we find [START_REF] Zielonka | Safe executions of recognizable trace languages by asynchronous automata[END_REF], who gives an inductive construction for non deterministic, deadlock-free asynchronous cellular automata. (A deadlock-free variant of Zielonka's construction was proposed in [START_REF] Stefanescu | Automatic synthesis of distributed transition systems[END_REF]). The paper [START_REF] Baudru | Distributed Asynchronous Automata[END_REF] proposes a construction of asynchronous automata of size exponential only in the number of processes (and polynomial in |A|) as our construction, but it yields non deterministic asynchronous automata (inappropriate for monitoring or control). Notice that while asynchronous automata can be determinized, there are cases where the blow-up is doubly exponential in the number of processes [START_REF] Klarlund | Determinizing Asynchronous Automata[END_REF].

Preliminaries

We fix a finite set P of processes and a finite alphabet Σ. Each letter a ∈ Σ is an action associated with the set of processes dom(a) ⊆ P involved in its execution. A pair (Σ, dom) is called distributed alphabet. A deterministic automaton over the alphabet Σ is a tuple A = Q, Σ, ∆, q 0 , F with a finite set of states Q, a set of final states F , an initial state q 0 and a transition function ∆ : Q × Σ → Q. As usual we extend ∆ to words in Σ * . The automaton accepts w ∈ Σ * if ∆(q 0 , w) ∈ F . We use L(A) to denote the language accepted by A. The size |A| of A is the number of its states.

Concurrent executions of systems with shared actions given by a distributed alphabet (Σ, dom), are readily modeled by Mazurkiewicz traces [START_REF] Mazurkiewicz | Concurrent Program Schemes and their Interpretations[END_REF]. The idea is that the distribution of the alphabet defines an independence relation among actions I ⊆ Σ × Σ, by setting (a, b) ∈ I if and only if dom(a) ∩ dom(b) = ∅. We call (Σ, I) an independence alphabet. The independence relation induces a congruence ∼ on Σ * by setting u ∼ v if there exist words u 1 , . . . , u n ∈ Σ * with u 1 = u, u n = v and such that for every i < n we have u i = xaby, u i+1 = xbay for some x, y ∈ Σ * and (a, b) ∈ I. An ∼-equivalence class is simply called a (Mazurkiewicz) trace. We denote by [u] the trace associated with the word u ∈ Σ * (for simplicity we do not refer to I, neither in ∼ nor in [u], as the independence alphabet is fixed). Trace prefixes and trace factors are defined as usual, with [p] a trace prefix (trace factor, resp.) of [u] if p is a word prefix (word factor, resp.) of some v ∼ u. As usual, we write ≤ for the prefix order. For two prefixes T 1 , T 2 of T , we let T 1 ∪ T 2 denote the smallest prefix T of T such that

T i ≤ T for i = 1, 2.
For several purposes it is convenient to represent traces by (labeled) pomsets. Formally, a trace T = [a 1 • • • a n ] (a i ∈ Σ for all i) corresponds to a labeled pomset E, λ, ≤ defined as follows: E = {e 1 , . . . , e n } is a set of events (or nodes), one for each position in T . Event e i is labeled by λ(e i ) = a i , for each i. The relation ≤ is the least partial order on E with e i ≤ e j whenever (a i , a j ) / ∈ I and i ≤ j. In Figure 1 we give an example for the pomset of a trace T , depicted by its Hasse diagram. The labeling of a total order on E that is compatible with ≤ is called a linearization of T .

An automaton A is called I-diamond if for all (a, b) ∈ I, and s a state of A: ∆(s, ab) = ∆(s, ba). Note that the I-diamond property implies that the language of A is I-closed : that is, u ∈ L(A) if and only if v ∈ L(A) for every u ∼ v. This permits us to write ∆(s, T ) where T is a trace, to denote the state reached by A from s on some linearization of T . Languages of I-diamond automata are called regular trace languages. -S p is the finite set of local states of a process p ∈ P, δ a : p∈dom(a) S p → p∈dom(a) S p is the local transition function associated with an action a ∈ Σ, s 0 ∈ p∈P S p is the global initial state, -Acc ⊆ p∈P S p is a set of global accepting states.

We call p∈P S p the set of global states (whereas S p is the set of p-local states). In this paper the size of an asynchronous automaton B is the total number of local states p∈P |S p |. This definition is very conservative, as one may want to count also Acc or the transition functions (that can be exponential in |B|). We will see that our construction allows to compute both Acc and the transition functions in polynomial time.

With the asynchronous automaton B one can associate a global automaton A B = Q, Σ, ∆, q 0 , Acc where:

-The set of states is the set of global states Q = p∈P S p of B, the initial and the accepting states are as in B.

-The transition function ∆ : Q×Σ → Q is defined by ∆((s p ) p∈P , a) = (s p ) p∈P with (s p ) p∈dom(a) = δ a ((s p ) p∈dom(a) ) and s p = s p , for every p / ∈ dom(a).

Clearly A B is a finite deterministic automaton with the I-diamond property.

Definition 2. The language of an asynchronous automaton B is the language of the associated global automaton A B .

We conclude this section by introducing some basic notations on traces. For a trace T , we denote by dom(T ) = e∈E dom(λ(e)) the set of processes occurring in T . For a process p ∈ P, we denote by pref p (T ) the minimal trace prefix of T containing all events of T on process p. Hence, pref p (T ) has a unique maximal event that is the last (most recent) event of T on process p. This maximal event is denoted as last p (T ). Intuitively, pref p (T ) corresponds to the history of process p after executing T . We extend this notation to a set of processes P ⊆ P and denote by pref P (T ) the minimal trace prefix containing all events of T on processes from P . By last(T ) we denote the set of events {last p (T ) | p ∈ P}. For example, in Figure 1 we have pref p (T ) = [cbadcba] and last p (T ) is the second a of the pomset. The set last(T ) contains the second a and the third b.

Zielonka-type constructions: state of the art

All general constructions of deterministic asynchronous automata basically follow the main ideas of the original construction of Zielonka [START_REF] Zielonka | Notes on finite asynchronous automata[END_REF]. These constructions start with a regular, I-closed word language, that is given either by a homomorphism to a finite monoid, or by an I-diamond automaton. In most applications we are interested in the second case, where we start with a (possibly non deterministic) automaton. The general constructions yield either asynchronous automata as defined in the previous section, or asynchronous cellular automata, that correspond to a concurrent-read-owner-write model. Theorem 1. [START_REF] Zielonka | Notes on finite asynchronous automata[END_REF] Let A be an I-diamond automaton over the independence alphabet (Σ, I). A deterministic asynchronous automaton B can be effectively constructed with L(A) = L(B).

We now review the constructions of [START_REF] Cori | Asynchronous mappings and asynchronous cellular automata[END_REF][START_REF] Mukund | Gossiping, Asynchronous Automata and Zielonka's Theorem[END_REF][START_REF] Genest | Constructing Exponential-Size Deterministic Zielonka Automata[END_REF] and recall their complexities. It is well known that determinization of word automata requires an exponential blow-up, hence the complexity of going from a non deterministic I-diamond automaton A to a deterministic asynchronous automaton is at least exponential in |A|. In that case, [START_REF] Genest | Constructing Exponential-Size Deterministic Zielonka Automata[END_REF] gives an optimal construction as it is simply exponential in both parameters |A| and |P|. Since determinization has little to do with concurrency, we assume from now on that A is a deterministic automaton.

- [START_REF] Cori | Asynchronous mappings and asynchronous cellular automata[END_REF] introduces asynchronous mappings and constructs asynchronous cellular automata of size

|Σ| |Σ| 2 • |A| 2 |Σ| . -[12] constructs asynchronous automata of size |P| |P| 2 • |A| |A|•2 |P| .
- [START_REF] Genest | Constructing Exponential-Size Deterministic Zielonka Automata[END_REF] introduces zone decompositions and constructs asynchronous automata of size 2

3|P| 3 • |A| |A|•|P| 2 .
Comparing our present construction with previous ones, we obtain asynchronous automata of size 4 |P| 4 • |A| |P| 2 . In all these constructions, the obtained automata are such that every process knows the state reached by A on its history. We abstract this property below, and show in the following section that our construction is optimal in this case. Definition 3. A deterministic asynchronous automaton B is called locally rejecting if for every process p, there is a set of states R p ⊆ S p such that for every trace T :

pref p (T ) / ∈ pref(L(B)) iff the p-local state reached by B on T is in R p .
Notice that R p is a trap: if B reaches R p on trace T , then so it does on every extension T of T . Obviously, no reachable accepting global state of B has a component in R p . For these reasons we call states of R p rejecting.

Our interest in locally rejecting automata is motivated by observing that all general constructions [START_REF] Zielonka | Notes on finite asynchronous automata[END_REF][START_REF] Cori | Asynchronous mappings and asynchronous cellular automata[END_REF][START_REF] Diekert | Construction of asynchronous automata[END_REF][START_REF] Mukund | Keeping Track of the Latest Gossip in a Distributed System[END_REF][START_REF] Mukund | Gossiping, Asynchronous Automata and Zielonka's Theorem[END_REF][START_REF] Genest | Constructing Exponential-Size Deterministic Zielonka Automata[END_REF] of deterministic asynchronous automata produce such automata. Suppose that A is a (possibly non deterministic) Idiamond automaton, and B a deterministic asynchronous automaton produced by one of the constructions in [START_REF] Zielonka | Notes on finite asynchronous automata[END_REF][START_REF] Mukund | Keeping Track of the Latest Gossip in a Distributed System[END_REF][START_REF] Mukund | Gossiping, Asynchronous Automata and Zielonka's Theorem[END_REF][START_REF] Genest | Constructing Exponential-Size Deterministic Zielonka Automata[END_REF] (a similar statement applies to the asynchronous cellular automata in [START_REF] Cori | Asynchronous mappings and asynchronous cellular automata[END_REF][START_REF] Diekert | Construction of asynchronous automata[END_REF]). Then the local p-state s p reached by B after processing the trace T determines the set of states reached by A on pref p (T ), for every process p. Thus, if no state in this set can reach a final state of A, then we put s p in R p . This makes B locally rejecting.

An exponential lower bound

In this section we present our lower bound result. We show that transforming an I-diamond deterministic automaton into a locally rejecting asynchronous automaton may induce an exponential blow-up in the number of processes. For this we define a family of languages Path n , such that the minimal sequential automaton for Path n has size O(n 2 ) but every locally rejecting asynchronous automaton recognizing Path n is of size at least 2 n/4 .

Let P = {1, . . . , n} be the set of processes. The letters of our alphabet are pairs of processes, two letters are dependent if they have a process in common. Formally, the distributed alphabet is Σ = P 2 with dom({p, q}) = {p, q}. The language Path n is the set of traces [x 1 • • • x k ] such that every two consecutive letters have a process in common:

x i ∩ x i+1 = ∅ for i = 1, . . . , k -1.
Observe that a deterministic sequential automaton recognizing this language simply needs to remember the last letter it has read. So it has less than |P| 2 states.

Theorem 2. Every locally rejecting asynchronous automaton recognizing Path n is of size at least 2 n/4 . Proof. Take a locally rejecting automaton recognizing Path n . Without loss of generality we suppose that n = 4k. To get a contradiction we suppose that process n of this automaton has less than 2 k (local) states.

We define for every integer 0 ≤ m < k two traces: a m = {4m, 4m + 1}{4m + 1, 4m+2}{4m+2, 4m+4} and b m = {4m, 4m+1}{4m, 4m+3}{4m+3, 4m+4}. To get some intuition, the reader may depict traces a 0 and b 0 and see that both a 0 and b 0 form a path from process 0 to process 4, the difference is that trace a 0 goes through process 2 while trace b 0 goes through process 3.

Consider the language L defined by the regular expression (a

0 + b 0 )(a 1 + b 1 ) • • • (a k-1 + b k-1 ).
Clearly, language L is included in Path n and contains 2 k = 2 n/4 different traces. As we have assumed that process n has less than 2 k states, there are two different traces t 1 , t 2 from L such that process n is in the same state after t 1 and t 2 . For simplicity of presentation we assume that t 1 and t 2 differ on the first factor: t 1 starts with a 0 , and t 2 with b 0 .

We can remark that processes 0 and n are in the same state after reading t 1 {0, 3} and t 2 . For process 0 it is clear as in both cases it sees the same trace {0, 1}{0, 3}. By our hypothesis, process n is in the same local state after traces t 1 and t 2 , therefore also after traces t 1 {0, 3} and t 2 .

Consider now the state s n reached by n after reading t 2 {0, n}. Since t 2 {0, n} ∈ Path n , the state s n is not in R n . By the above, the same state s n is also reached after reading t 1 {0, 3}{0, n}. Trace t 1 starts with a 0 = {0, 1}{1, 2}{2, 4} and continues with processes whose numbers are greater than 4, so {0, 3} commutes with all letters of t 1 except {0, 1}. Hence t 1 {0, 3} ∈ pref(Path n ). Since trace t 1 ends with an action of process n, we have pref n (t 1 {0, 3}{0, n}) = t 1 {0, 3}{0, n} / ∈ pref(Path n ). Since we have assumed that the automaton is locally rejecting, we should have s n ∈ R n . A contradiction. 2

A matching upper bound

Our goal is to modify the construction from [START_REF] Genest | Constructing Exponential-Size Deterministic Zielonka Automata[END_REF] in order to make it polynomial with respect to the size of the sequential automaton. We give an overview of the new construction, first describing the objects the asynchronous automaton manipulates. Some details of the mechanics of the automaton will follow. Overall, although described in a different way, the present construction follows closely [START_REF] Genest | Constructing Exponential-Size Deterministic Zielonka Automata[END_REF].

The main difference is the state information computed on the zone decomposition of a trace. This state information becomes polynomial (instead of exponential), but its update is much more involved than in [START_REF] Genest | Constructing Exponential-Size Deterministic Zielonka Automata[END_REF].

We fix a set of processes P and a distributed alphabet (Σ, dom). Let A = Q, Σ, ∆, q 0 , F be a deterministic I-diamond automaton. A candidate for an equivalent asynchronous automaton B = (S p ) p∈P , (δ a ) a∈Σ , s 0 , Acc has a set of states for each process and a local transition function. The goal is to make B calculate the state reached by A after reading a linearization of a trace T . Let us examine how B can accomplish this task. After reading a trace T the local state of a component p of B depends only on pref p (T ). Hence, B can try to calculate the state reached by A after reading (some linearization of ) pref p (T ). When a next action, say a, is executed, processes in dom(a) can see each others' states and make the changes accordingly. Intuitively, this means that these processes can now compose their information in order to calculate the state reached by A on pref dom(a) (T ) a. To do so they will need some information about the structure of the trace.

As usual, the tricky part of this process is to reconstruct the common view of pref dom(a) (T ) from separate views of each process: pref p (T ) for p ∈ dom(a). For the sake of example suppose that dom(a) = {p, q, r}, and we know the states s p , s q and s r , reached by A after reading pref p (T ), pref q (T ) and pref r (T ), resp. We would like to know the state of A after reading pref {p,q,r} (T ). This is possible if we can compute the contributions of pref q (T )\pref p (T ) and pref r (T )\ pref {p,q} (T ). The automaton B should be able to do this by looking at s p , s q , and s r , only. This remark points out the challenge of the construction: find the type information that allows to deduce the behaviour of A, and that at the same time is updatable by an asynchronous automaton.

General structure

Before introducing formal definitions it may be worth to say what is the general structure of the states of the automaton B. Every local state will be a triple (ts, ZO, ∆), where ts will be a time stamping information as in all general constructions of asynchronous automata; -ZO will be a zone order, a bounded size partial order on a partition of the trace; -∆ will be state information, recording the behavior of A on the partition given by ZO.

Roughly, we will use time stamping to compute zone orders, and zone orders to compute state information. The latter provides all the necessary information about the behaviour of A on (a linearization of) the trace.

Time stamping:

The goal of the time stamping function [START_REF] Zielonka | Notes on finite asynchronous automata[END_REF] is to determine for a set of processes P and a process q the set last(pref P (T )) ∩ last(pref q (T )). This set uniquely determines the intersection of pref P (T ) and pref q (T ) (for details see e.g. [START_REF] Mukund | Keeping Track of the Latest Gossip in a Distributed System[END_REF]). Computing such intersections is essential when composing information about pref p (T ) for every p ∈ dom(a) into information about pref dom(a) (T ). The main point is that there exists a deterministic asynchronous automaton that can accomplish this task: Theorem 3. [START_REF] Mukund | Keeping Track of the Latest Gossip in a Distributed System[END_REF] There exists a deterministic asynchronous automaton A TS = (S p ) p∈P , (∆ a ) a∈Σ , s 0 such that for every trace T and state s = ∆(s 0 , T ) reached by A TS after reading T : for every P ⊆ P and q, r, r ∈ P, the set of local states {s p | p ∈ P ∪ {q}} allows to determine if last r (pref P (T )) = last r (pref q (T )).

Moreover, such an automaton can be effectively computed and its local states can be described using O(|P| 2 log(|P|)) bits.

For instance, if a new b is executed after T = [cbadcbad] in Figure 2, process r and processes p, q can determine that the intersection of their last-sets consists of the second b. Indeed, last(pref p,q (T )) is made of the second a (for last p = last q ) and the second b (for last r ). Also, last(pref r (T )) is made of the second d (for last r ), the second b (for last q ) and the first a (for last p ).

Zone orders: Recall that one of our objectives is to calculate, for every p ∈ P, the state reached by A on pref p (T ). As the discussion on page 7 pointed out, for this we may need to recover the transition function of A associated with pref q (T ) \ pref P (T ) for a process q and a set of processes P . Hence we need to store information about the behaviour of A on some relevant factors of T that are not prefixes. Zones are such relevant factors. They are defined in such a way that there is a bound on the number of zones in a trace. The other crucial property of zones is that for every extension T of T and every P ⊆ P, q ∈ P, if a zone of T intersects pref q (T ) \ pref P (T ) then it is entirely in this set. A zone order is an abstract representation of the decomposition of a trace into zones. There is a useful partial order on zones that we define now. Let Z, Z be two zones of some trace T . We write Z Z if Z = Z and e < e for some events e ∈ Z, e ∈ Z . It is easy to see that Z Z implies that L(Z ) L(Z). Thanks to this property we can define the order on zones, denoted Z ≤ Z , as the smallest partial order containing the relation.

Lemma 1. A trace is partitioned in at most |P| 2 zones.
The lemma above gives a slightly better bound than [START_REF] Genest | Constructing Exponential-Size Deterministic Zielonka Automata[END_REF]. Moreover, it can be shown that its bound is asymptotically optimal. Figure 2 Definition 5. A zone order is a labeled partial order ZO = V, ≤, ξ : V → 2 P , where every element is labeled by a set of processes. We require that every two elements whose labels have non empty intersection are comparable:

ξ(v)∩ξ(v ) = ∅ ⇒ (v ≤ v ∨ v ≤ v).
We say that such a zone order is the zone order of a trace T , if there is a bijection µ from V to zones of T preserving the order and satisfying ξ(v) = dom(µ(v)).

Lemma 2. The zone order of a trace can be stored in |P| 2 (|P| 2 + |P|) space. So there are at most 2 O(|P| 4 ) zone orders.

State information:

We describe now the state information for each zone of the trace. Let ZO = V, ≤, ξ : V → 2 P be the zone order of some trace T , via a bijection µ. For an element v ∈ V we denote by T v the factor of T consisting of zones up to µ(v): that is, the factor covering µ(v ) for all v ≤ v. Observe that T v is a prefix of T . For instance, in Figure 2 the zone order of pref r (T ) contains three vertices v 1 < v 2 < v 3 , and T v2 is the trace [bcadb]. Definition 6. We say that a function ∆ : V → Q is state information for the zone order ZO of a trace T if for every v we have ∆(v) = ∆(q 0 , T v ), namely the state of A reached on a linearization of T v .

Observe that a zone order for a trace of the form pref p (T ) has one maximal element v p : it corresponds to the last action of p. If ∆ is the state information for T , then the state reached by A on reading a linearization of pref p (T ) is ∆(v p ).

The construction of the asynchronous automaton

Let us come back to the description of the asynchronous automaton B. For every p ∈ P, a local state in S p will have the form (ts p , ZO p , ∆ p ). The automaton will be defined in such a way that after reading a trace T the state s p reached at the component p will satisfy:

ts p is the time stamping information; -ZO p is the zone order of pref p (T ); -∆ p is the state information for ZO p .

By [START_REF] Mukund | Keeping Track of the Latest Gossip in a Distributed System[END_REF] we know that B can update the ts p component. The proposition below says that B can update the ZO p and ∆ p components. Proposition 1. Let T be a trace and a ∈ Σ an action. Suppose that for every p ∈ dom(a) we have the time stamping information ts p and the zone order with state information (ZO p , ∆ p ) of pref p (T ). We can then calculate the zone order and the state information of pref p (T a), for every p ∈ dom(a).

We also need to define the sets of rejecting states R p and the global accepting states Acc of B. Observe that by Proposition 1, from the local state s p we can calculate ∆(q 0 , pref p (T )), namely the state of A reached after reading a linearization of pref p (T ). This state is exactly the state associated to the unique maximal element of the zone order in s p . Hence, B can be made locally rejecting by letting s p ∈ R p if ∆(q 0 , pref p (T )) is not productive in A, i.e., no final state can be reached from it.

To define accepting tuples of states of B we use the following proposition:

Proposition 2. Let T be a trace. Given for every p ∈ P the time stamping ts p , and the zone order ZO p with state information ∆ p of pref p (T ), we can calculate ∆(q 0 , T ), the state reached by A on a linearization of T .

In the light of Proposition 2, a tuple of states of B is accepting if the state ∆(q 0 , T ) of A is accepting. The two propositions give us: Theorem 4. Let A be a deterministic I-diamond automaton over the distributed alphabet (Σ, dom). We can construct an equivalent deterministic, locally rejecting asynchronous automaton B with at most 4 |P| 4 • |A| |P| 2 states.

We now describe informally the main ingredients of the proof of Proposition 1 (Proposition 2 is proved along similar lines). The zone order ZO of pref P ∪{q} (T ) is built in two steps from ZO P and ZO q : first we construct a so-called prezone order ZO by adding to ZO P the zones from pref q (T ) \ pref P (T ) [START_REF] Genest | Constructing Exponential-Size Deterministic Zielonka Automata[END_REF]. Then we quotient ZO in order to obtain ZO. The quotient operation amounts to merge zones. The difficulty compared to [START_REF] Genest | Constructing Exponential-Size Deterministic Zielonka Automata[END_REF] is posed by the update of the state information. Since the state information for the pre-zone ZO is inconsistent due to the merge, the crucial step is to compute this information on downward closed sets of zones: Lemma 3. Let ZO = V, ≤, ξ , ∆ be the zone order and state information for a trace T (via the bijection µ). For every downward closed B ⊆ V we can compute the state reached by A on a linearization of T B = {T v | v ∈ B}, using only ZO and ∆.

The proof of the lemma above is based on a nice observation about I-diamond automata A, taken from [START_REF] Cori | Asynchronous mappings and asynchronous cellular automata[END_REF]. It says that for every three traces T 0 , T 1 , T 2 with dom(T 1 ) ∩ dom(T 2 ) = ∅, the state reached by A on a linearization of T 0 T 1 T 2 can be computed from dom(T 1 ) and the states reached on (linearizations of) T 0 , T 0 T 1 , T 0 T 2 , respectively.

We now sketch the proof of the lemma. We first choose some linearization v

1 , . . . , v n of B. For each i, k with i ≤ k, let B i,k = {v 1 , . . . , v i } ∪ {v j | j > i, v j ≤ v k }.
For instance, if there are four zones v 1 , v 2 , v 3 , v 4 with v 1 < v 2 < v 4 , v 1 < v 3 < v 4 , and ξ(v 2 ) ∩ ξ(v 3 ) = ∅, then B 1,2 = {v 1 , v 2 }, B 1,3 = {v 1 , v 3 }, and B 2,3 = {v 1 , v 2 , v 3 }.

We show now how to compute inductively ∆(q 0 , T B i,k ). Notice that the base case is trivial, as B 0,k = ∆(v k ) for all k. Let i ≤ n. Suppose that for all k ≥ i -1, we know ∆(q 0 , T B i-1,k ). In particular, note that the states q i-1 , q i reached on µ(v 1 • • • v i-1 ) and µ(v 1 • • • v i ), respectively, are known (cases k = i -1 and k = i). We compute now ∆(q 0 , T B i,k ), for all k > i. Two cases arise. If v i < v k then we apply the observation of [START_REF] Cori | Asynchronous mappings and asynchronous cellular automata[END_REF] to q i-1 , q i , ∆(q 0 , T B i-1,k ), ξ(v i ), which yields ∆(q 0 , T B i,k ). If v i < v k , then B i-1,k = B i,k and the state ∆(q 0 , T B i,k ) is already known. At the end of this polynomial time procedure, we have computed ∆(q 0 , T B ) = ∆(q 0 , T Bn,n ).

Remark 1. The automaton B of Theorem 4 can be constructed on-the-fly, i.e., given the action a ∈ Σ and the local states s p of B, p ∈ dom(a), one can compute the successor states δ a ((s p ) p∈dom(a) ). The question is now how much time we need for this computation. The update of the time stamping and the update of zone orders take time polynomial in |P|. The update of state information can be done in time polynomial in |P| and linear in the number of transitions of |A|. So overall, we can compute transitions on-the-fly in polynomial time. Similarly, we can decide whether a global state is accepting in polynomial time.

Conclusion

In this paper we have presented an improved construction of asynchronous automata. Starting from a zone construction of [START_REF] Genest | Constructing Exponential-Size Deterministic Zielonka Automata[END_REF], we have shown how to keep just one state per zone instead of a transition table. This allows to obtain the first construction that is polynomial in the size of the sequential automaton and exponential only in the number of processes.

It is tempting to conjecture that our construction is optimal. Unfortunately, it is very difficult to provide lower bounds on sizes of asynchronous automata. We have given a matching lower bound for the subclass of locally rejecting automata. It is worth to recall that all general constructions in the literature produce automata of this kind. Moreover the concept of locally rejecting automaton is interesting on its own from the point of view of applications.

We conjecture that the translation from deterministic word automata to asynchronous automata must be exponential in the number of processes (where the size means the total number of local states).

Definition 1 .Fig. 1 .

 11 Fig. 1. The pomset associated with the trace T = [c b a d c b a d b], with dom(a) = {p, q}, dom(b) = {q, r}, dom(c) = {p}, dom(d) = {r}.

Definition 4 .Fig. 2 .

 42 Fig. 2. The three zones of pref r (T ) (darker) are marked with solid lines. The two zones of pref {p,q} (T ) (lighter) are represented by dotted lines.

  depicts the trace T = [cbadcbad]. Recall that last(pref r (T )) consists of the first a, the second b and the second d. There are three zones in pref r (T ): Z 1 contains the first a, b and c, Z 2 the first d and the second b, and Z 3 the second d. We have Z 1 < Z 2 < Z 3 .