Irina Bunda
email: irina.bunda@univ-orleans.fr

Jean-Baptiste Desquilbet
email: jean-baptiste.desquilbet@univ-orleans.fr

BANK LIQUIDITY and EXCHANGE RATE REGIMES

Keywords: Bank liquidity, exchange rate regimes, currency boards, emerging countries. JEL classification: F33, G21

Combining panel data on bank liquidity at the individual level and data on their macroeconomic environment, for a sample of commercial banks in emerging countries between 1995 and 2000, we show that their exists a "bank liquidity smile across exchange rate regimes". In extreme regimes at both ends of the line, i.e. for pure floating exchange rate regimes at one end and currency boards and dollarized economies at the other end, bank assets are more liquid than in intermediate regimes.

1-Introduction

The aim of the paper is to explore how the liquidity of commercial bank assets is affected by the exchange rate regime of the country in which they operate.

Many papers have been written on twin crises, and the relationship between exchange rate (or balance of payment) and bank fragility1 . In particular, [START_REF] Chang | Financial Fragility and the Exchange Rate Regime[END_REF], using an open economy extension of the famous [START_REF] Diamond | Bank runs, deposit insurance, and liquidity[END_REF] model, study how the "mixture" of exchange rate regime and presence or lack of a lender of last resort affects the potential for bank (liquidity) crises and balance of payment crises, either simultaneously or in isolation. They show that fixed exchange rate regimes where the central bank does not act as a lender of last resort, in particular currency boards, are more vulnerable to liquidity crises, whereas the combination of flexible exchange rates and a central bank that serves as lender of last resort eliminates selffulfilling runs. Therefore, according to their model, the potential for a bank run is not independent of the exchange rate regime.

The aim of this paper to confront with facts the following corollary of that idea: if the potential for a bank liquidity crisis indeed depends on the exchange rate regime, banks should behave accordingly. Some kind of self-protection response should induce banks to keep more or less liquid assets, depending, ceteris paribus, on the exchange rate regime.

Combining panel data on bank liquidity at the individual level and data on their macroeconomic environment, for a sample of commercial banks in emerging countries between 1995 and 2000, we identify a particular configuration: in extreme regimes at both ends of the line, i.e. for pure floating exchange rate regimes at one end and currency boards and dollarized economies at the other end, bank assets are more liquid than in intermediate regimes. This results seems to be very robust to changes in the definition of liquidity (we used different liquidity ratios), or the difference between official and de facto exchange rate regimes.

After a review of some measurable determinants of bank liquidity (section 2), we set out the data (section 3) and the regression results (section 4).

2-The model

Several phenomena affect the liquidity of bank assets, such as bank specialization, ability in risk management, banking regulation and supervision, interest rate margins and their variability, information asymmetries in the credit market, macroeconomic environment. Among these many phenomena, we want to emphasize the role of the exchange rate regime.

Since the perspective of this paper is basically empirical, and oriented towards emerging economies, we take into account variables for which available data exist and are easily obtained.

Individual bank data was provided by the Bankscope ® database (see below). Since the behaviour of banks may depend on its "type", we retained commercial banks only 2 .

We test the following relationship:

Liquidity ratio = α 0 + α 1 total assets + α 2 equity to asset ratio We interpret this relationship as follows.

+
The higher the liquidity ratio is, the more liquid the bank assets will be. It is assumed to depend on individual behaviour of banks, their market and macroeconomic environment as well as the exchange rate regime.

A first set of variables are representative of individual characteristics of commercial banks.

1-Total assets are a measure of the size of the bank. It should capture differences in asset liquidity according to the size of the bank. If big banks were seeing themselves as "too big to fail", we would observe a negative coefficient (the bigger the bank, the less liquid) 3 . This effect may be reinforced if larger banks have stronger political connections and support than smaller banks, as may be the case in some emerging countries.

2-

The ratio of equity to assets may have opposite effects on liquidity, as shown by the debate on minimum capital adequacy requirements in emerging markets. On the one hand, the effect may be negative. The higher the equity ratio, the smaller the amount of liquid assets required for sound banking practice, in order to keep liquid liabilities and liquid assets in balance. [START_REF] Kim | Risk in Banking and Capital Regulation[END_REF] show that in general the solvency regulation will entail a recomposition of the risky part of the bank's portfolio in such a way that its risk is increased. According to [START_REF] Dewatripont | La réglementation prudentielle des banques[END_REF], shareholders are much more inclined to involve the bank into risky investment projects than ordinary creditors. Therefore the bank may reduce its "unprofitable" liquid assets in order to maintain or to increase the overall return on bank's equity. On the other hand, information asymmetries in the credit market may bring about credit rationing phenomena, reflecting the fact that banks do not necessarily increase profitability by lending more. Thus, a higher ratio of equity to assets may be compatible with higher asset liquidity (see e.g. [START_REF] Thakor | The design of financial systems: An overview[END_REF].

We take these two variables as exogenous to liquidity, and we do not include other variables that are more or less codetermined with asset liquidity and asset portfolio choice, such as the net interest margin, or measures of return (ROAE, ROAA).

A second set of variables relates liquidity to banking activities at a "market" level.

3-The presence of prudential regulation should show through on bank liquidity. In emerging economies, prudential regulations were adopted progressively through the 1990's after the various financial crises. At first sight, they can be considered as an obligation for banks to be liquid enough, but also as an incentive mechanism for banks to enforce a more efficient liquidity management. It is also implemented within a general improvement of bank supervision. In an environment such as emerging markets, with poor lending opportunities, the introduction of prudential regulation can explain an increase in liquidity if banks tended 3 However, this would be better captured by a relative rather than absolute measure of the bank size.

to lend too much, but also a decrease in liquidity whenever banks tended to be too cautious in their lending policy.

4-

The lending interest rate is taken into account as a measure of lending profitability at market level, so that higher interest rates could be naively interpreted as an explanation for lower bank liquidity. However, it is well known that portfolio choices of banks depend on both interest rates and risk controllability. In a credit market with asymmetric information, i.e.

poor risk controllability, adverse selection can lead to credit rationing, as shown e.g. by [START_REF] Stiglitz | Credit rationing with imperfect information[END_REF], so that high interest rates may well be associated with high bank liquidity.

A third set of variables relates liquidity to the macroeconomic environment.

5-Public expenditures/GDP are included to take into account supply side factors in the market for liquid assets: large public expenditures reflect substantial supply of government securities, which are usually computed as liquid assets. It also represent the potential for government inference in banking activities: in emerging countries, in which capital market development is in process, the government often relies on banks to finance its expenditures.

6-The rate of inflation measures another incentive for banks to hold liquid assets: when banks give more importance to customer relations and increase long term lending, they make the nominal value of their assets more sticky, and thus become more vulnerable to rises in inflation.

7-The rate of growth, on the contrary, is taken as indicating better perspectives for borrowers, and more profitable lending by banks, thus reducing their asset liquidity.

8-At last, we take into account the fact that the realisation of a financial crisis must have a negative link with bank liquidity. First, a financial crisis may be due to poor bank liquidity, which can result from a lending boom (see e.g. [START_REF] Tirole | Financial Crises, Liquidity, and the International Monetary System[END_REF]. Second, a financial crisis purges the financial system from unhealthy (illiquid) banks, induces banks to curtail lending, spills over to the real sector and prompts a decrease in the demand for loans, so that the aftermath of the crisis should be associated with higher liquidity.

The last set of variables are dummy variables that reflect the type of exchange rate regime, which is the raison d'être of this paper, as explained in introduction. Many emerging economies went through noticeable changes in their exchange rate regimes during the second half of the 1990's, after confronting severe financial crises. We have to bear in mind that, for a subset of emerging countries, changes in exchange rate regime, realisation of a financial crisis and changes in prudential regulation were concomitant.

3-The data

3.1-Individual bank data:

Individual bank data (liquidity ratios, total assets, equity ratio) come from Bankscope ® . We used data available on a sample of 1107 commercial banks in 36 emerging economies 4 for years 1995 to 2000. Table 1 reports data availability on the main items of the banks' balance sheet in Bankscope.

Total Liabilities & Equity

In brackets: percentage of available data in the Bankscope sample.

We use five different measures of bank asset liquidity.

1. Liquid Assets / Total Assets (computed from Bankscope data).

"Liquid assets" are the sum of "Cash and Due from Banks", "Deposits with Banks", "Due from Central Banks", "Due from Other Banks", "Due from Other Credit Institutions", "Treasury Bills", "Other Bills", "Government Securities", "Trading Securities", "CDs".

4 Countries in the sample were selected according to the IMF classification of emerging countries (see the IMF World Economic Outlook) and taking into account data availability in the Bankscope database. They are in Africa (Morocco, Tunisia, South Africa), in Asia (China, India, Indonesia, Malaysia, Philippines, South Korea, Thailand, Vietnam), in the Middle East (Egypt, Israel, Lebanon), in the Western Hemisphere (Argentina, Brazil, Chile, Colombia, Ecuador, Mexico, Peru, Venezuela), in the Commonwealth of Independent States (Belarus, Kazakhstan, Russia, Ukraine) and E.U. accession candidates (Bulgaria, Czech Republic, Estonia, Hungary, Latvia, Lithuania, Poland, Romania, Slovak Republic, Turkey). 5 No information is given on whether assets and liabilities are in home or in foreign currency, so that no conclusion can be inferred regarding the "dollarization" of assets and or liabilities.

Net Loans / Total Assets (provided by Bankscope)

This ratio indicates what percentage of the assets of the bank are tied up in loans. The higher this ratio the less liquid the bank will be.

Liquid Assets / Customer & Short Term Funding (provided by Bankscope)

This is a deposit run off ratio and shows what percentage of customer and short term funds could be met if they were withdrawn suddenly. The higher this percentage, the more liquid the bank and the less vulnerable to a classic run.

Liquid Assets / Total Deposits & Borrowing (provided by Bankscope)

This ratio is similar to the previous one, but indicates the amount of liquid assets available to borrower as well as depositors.

5. Interbank Ratio, computed as the ratio of "due from banks" over "due to banks" (provided by Bankscope)

This ratio is a measure of interbank liquidity. If money lent to other banks divided by money borrowed from other banks is greater than 100%, then it indicates the bank is net placer rather than a borrower of funds in the market place, and therefore more liquid.

The first and second ratios assess some kind of "absolute" asset liquidity, since they consider liquid (or illiquid) assets relative to total assets. The third and forth ratios measure some kind of "relative" asset liquidity, since they relate liquid assets to liquid liabilities. The fifth ratio measures liquidity in the interbank market.

3.2-Market and macroeconomic data:

Most market and macroeconomic data were retrieved from various publications of the International Monetary Fund.

• lending interest rate: line 60p

• public expenditures/GDB: line 91f/ line 99b

• rate of inflation: computed from the Consumer Price Index given in line 64

• rate of growth: computed from real GDP given in line 99bvp except for Lebanon: data provided by EIU and the national bank (Banque du Liban).

• presence of prudential regulation (dummy)

This dummy variable in order to catch the regulatory framework indicates whether the country adopted the bank minimum capital requirements as recommended by the 1988 Capital Accord proposed by the Basel Committee on Banking Supervision. As [START_REF] Chiuri | The Macroeconomic Impact of Bank Capital Requirements in Emerging Economies: Past Evidence to Assess the Future[END_REF] point out, the non G10 countries adopted the Basel 1988 Capital Accord on a voluntary basis and therefore without any predefined time schedule. Moreover, several non G10 countries have relatively weak regulatory and supervisory structures and therefore the simple introduction of new capital requirements cannot be considered equivalent to their enforcement.

For these reasons, there is an element of judgement in the definition of the exact date when the New Basel capital requirements were effectively adopted by the emerging countries of our sample as well as the proper date where capital requirements were enforced. We employ the assessment made by [START_REF] Chiuri | The Macroeconomic Impact of Bank Capital Requirements in Emerging Economies: Past Evidence to Assess the Future[END_REF] for 15 countries of our sample (Argentina, Brazil, Hungary, Korea, Malaysia, Mexico, Morocco, Thailand, Turkey, South Africa, Venezuela, Chile, India, Israel, and Poland). As for the other 21 countries of our sample, we extended their analysis with a view of being consistent. We identified the years of Capital requirements enforcement by surveying the IMF Reports on the Observance of Standards and Codes (ROSCs). We focused on banking supervision as one of the 11 areas6 studied by the Fund and the World Bank.

The computation of our dummy variable for prudential regulation is summed up in table 2. • realization of a crisis (dummy)

We identified the countries and the years where a financial and/or a currency crisis took place through an extensive survey of the IMF World Economic Outlook for the specified time span.

Furthermore, useful information was provided by the IMF Country Reports for the 36 countries of our sample. The dummy variable is also introduced with a one-year lag, to capture the expected opposite effects of both the onset and the aftermath of the crisis on bank liquidity.

3.3-Exchange rate regimes:

Table 3: exchange rate regime classification We then group some classes together, and keep five different types of regime (see table 3). The group "soft pegs" consists of economies with exchange rates within crawling bands, crawling pegs and pegged exchange rates within horizontal bands. The group "conventional fix" consists of economies with other conventional fixed peg arrangements (against a single currency, against composite as well as de facto peg arrangements under managed floating). The extreme solutions consist of either hard pegs (that is currency boards arrangements and formal dollarization) or independently floating. Therefore we treat managed float with no specified central rate as an intermediate exchange rate regime rather than an extreme one. Careful study of sample data on the realization of a financial crisis, the introduction of prudential regulation and changes in exchange rate regimes shows that (see table 4): (1) there is no systematic link between exchange rate regime switches and financial crises;

(2) a (local) crisis is neither a systematic nor the only trigger of the introduction of prudential regulation. We will thus use the dummy variables for the realization of a financial crisis, the presence of prudential regulation and the type of exchange rate regimes as separate variables in the regressions, instead of building dummies that would catch cross effects.

4-The results:

We estimate the following type of relationship : R(i, t) = ( )

9 k 1 , k k x i t α = ∑ + ( ) 4 k 1 , k k i t δ β = ∑ + u(i, t)
where :

-R(i, t) denotes the liquidity ratio, δ k are the dummy variables for the exchange rate regime (with "managed floating" used as reference for official regimes, and "soft peg" for de facto regimes) 7 , u(i, t) is the error term.

-x k (i,
i denotes an individual bank, t is the time index.

We use the SAS ® TSCSREG procedure which is appropriate for regressions on unbalanced panel data, after deleting all banks in the sample reporting a null equity ratio, a null total assets, and/or less than two years for all the variables. We estimate the relationships as two-way random effect models, applying the "RanTwo" option of the SAS ® TSCSREG procedure, i.e. we assume that the 7 The references were chosen according to the size of the underlying samples. Since the sample used for each regression changes, due to missing and/or deleted data, the reference could have been different. It turns out they are not.

error term depends on both the cross section and the time series to which the observation belongs:

u(i, t) = v(i) + e(t) + ε(i, t).
where v(i) is the cross section component of the error term, e(t) its time component, and ε(i, t) is a classical error term with zero mean and a homoscedastic covariance matrix.

Although we think that using the de facto classification for exchange rate arrangements is more appropriate, we report regression results using both official and de facto taxonomies in table 5 andtable 6. Two general, and not surprising, comments apply, before a more detailed review of the results. Firstly, there are no major differences in results if we use one exchange rate regime classification or the other. Secondly, however, results are somewhat different in the regressions of the "interbank ratio", which measures relative liquidity in the interbank market, rather than asset liquidity.

"Total assets" are generally statistically insignificant (except but the regression of the ratio of "Liquid Assets to Total deposit and borrowing", where it is significant at a 10% level). The size effect, which we identified with "total assets", thus does not look robust.

The coefficient on the "equity to asset ratio" is significant and positive in regressions for all liquidity ratios except the "interbank ratio" (where it is not significant), whether the exchange rate classification is official or de facto. These results support the view that a higher ratio of equity to assets is concomitant with higher asset liquidity.

The "lending rate" parameter estimate is significant and positive (except for the "interbank ratio", and "Liquid Assets to customer and ST funding"), which is consistent with the "credit rationing" phenomenon: higher lending rates do not encourage banks to lend more.

The ratio "Public expenditures to GDP" is significant and with the expected (positive) sign in all the regressions. We interpret this result as evidence of a liquid asset supply effect.

The "rate of inflation" and the "rate of growth" enter with the expect sign, whenever they are significant at standard levels of confidence. We note that the rate of inflation is not significant (or at best at a 10% level of confidence in one case) in the four regressions of the "relative liquidity" ratios. Since banks can protect their balance sheets from the negative effect of inflation by matching liquid assets and liabilities, the influence of inflation on observed ratios of liquid assets to liquid liabilities need not be monotonous. The dummy for the "presence of prudential regulation" enters with positive or negative signs in the different regressions, depending on the liquidity ratio, which may seem a bit confusing at the first sight.

The impact of regulation is insignificant when liquidity is measured according to the "Interbank Ratio". The impact on "absolute liquidity" is positive, as shown in regressions of "Liquid Assets/Total Assets" and "Net Loans/Total Assets", whatever the exchange rate taxonomy. It is negative on "relative liquidity", as shown in regressions of the "Liquid Assets/ Total Deposit and

Borrowing" and "Liquid Assets/ Customer and Short Term Funding" (although not different from 0 at a 10% confidence level in the latter case with the de facto classification of exchange rate regimes). Therefore, it seems that the impact of prudential regulation is to increase the "absolute liquidity" of liabilities faster than the "absolute liquidity" of assets8 . It may be that the introduction of prudential regulation increases confidence in the banking sector, so that banks can collect more deposits, thus increasing liquid liabilities, while, at the same time but to a lesser extent, investing more in illiquid projects. As expected, the "realization of a crisis" has a significant negative impact on both "absolute" and "relative" liquidity (although the estimate of the parameter is not significantly different from zero in the regression of the "Liquid Assets/ Total Deposit and Borrowing" ratio using the official exchange rate classification). The impact on interbank liquidity is significantly negative only when we use the de facto taxonomy.

As to the lagged impact of the crisis, it has a positive effect on "absolute liquidity" (whatever the exchange rate classification), as expected. The effect on "relative liquidity" is not significant under the de facto exchange rate classification, and significant at a 10% level in one case under the official classification. The aftermath of the crisis is characterized by a surge in absolute liquidity, but no significant effect on relative liquidity.

The nature of the exchange rate regime has an interesting effect on bank liquidity. In extreme regimes at both ends of the line, i.e. in the independently floating exchange rate regime at one end and hard pegs at the other end, bank assets are more liquid than in intermediate regimes, especially when liquidity is measured in absolute terms. We call this phenomenon a "bank liquidity smile across exchange rate regimes", as suggested by figure 2 for de facto regimes.

Under "hard pegs", observed high bank liquidity complies with the theoretical model put forward by [START_REF] Chang | Financial Fragility and the Exchange Rate Regime[END_REF] 9 : lender of last resort operations are severely limited, so that bank runs and financial panics are not easily prevented, unless bank themselves keep a sufficient amount of liquid assets.

The higher liquidity under "independently floating" exchange rates is not as obviously explained in their model as under "hard pegs". Nevertheless, they point out that deposit dollarization, i.e. the fact that bank accounts may be denominated in foreign currency, impedes dramatically the potential role of the central bank as a lender of last resort: "the central bank can print pesos, but not dollars needed to honor the dollar claims of impatient depositors… flexible exchange rates cannot help prevent bank runs" (Chang and Velasco 2000, page 27). We could not check this potential explanation since Bankscope does not give data on deposit dollarization, and aggregated data, which could be used as an indicator, is not published for all countries. Another way to consider the "liquidity smile" is to emphasize the relative lack of bank liquidity in intermediary regimes. This phenomenon has been underlined by studies on the Asian crisis (see eg. [START_REF] Tirole | Financial Crises, Liquidity, and the International Monetary System[END_REF], Feldstein 2003). Intermediary regimes in the mid 1990s created an illusion of stability and lowered the cost of borrowing in international markets by blurring currency and country risk: banks could borrow underpriced liquidity if need be, and kept a relatively low amount of liquid assets.

5-Conclusion

Using panel data on bank liquidity in emerging countries between 1995 and 2000, we find that in hard pegs and in pure floats, commercial banks are more liquid than in intermediary regimes. We call it a "bank liquidity smile".

We accounted for the fact that many emerging countries were hit by financial and/or currency crises during that period, as well as the changes of prudential regulation they operated.

We take the "bank liquidity smile" as a stylised fact to be reinforced or dispelled by further empirical research. Empirical developments of our analysis should include banks in more advanced countries, in order to check whether the liquidity smile is specific to emerging markets or a more general phenomenon. It should also take into account liability dollarization and the currency mismatch of bank balance sheets as much as possible.

  International Financial Statistics Yearbok (2001) definitions for official exchange rate regimes, and[START_REF] Bubula | The Evolution of Exchange Rate Regimes Since 1990: Evidence From De Facto Policies[END_REF] for de facto regimes. The basic official IMF Exchange Rate Arrangements (i.e. the declared commitments of the Central Banks) are identified by a number from 8 (independent floating) to 1 (dollarization).[START_REF] Bubula | The Evolution of Exchange Rate Regimes Since 1990: Evidence From De Facto Policies[END_REF] split de facto regimes into 13 categories. However, for comparison purposes, we reorganized the latter to use the same taxonomy as for official regimes.

FigureFigure 1

 1 Figure 1: De facto exchange rate arrangements

Figure

  Figure 2: bank liquidity across de facto exchange rate arrangements

Table 1 :

 1 Bank balance sheet items and data availability 5

	Loans (68.0%)	Customer & Short Term Funding (68.4%)
	Other Earning Assets (68.9%)	Other Funding
	Total Earning Assets (69.0%)	Other (Non Interest Bearing)
	Fixed Assets (68.4%)	Loan Loss Reserves (52.8%)
	Non-Earning Assets (69.0%)	Other Reserves
		Equity (69.0%)
	Total Assets (69.0%)

Table 2 : "prudential regulation" by year Prudential regulation 1995 1996 1997 1998 1999 2000 Total

 2

	NO	23	21	16	10	10	7	87
	% by year	63.89	58.33	44.44	27.78	27.78	19.44
	YES	13	15	20	26	26	29 129
	% by year	36.11	41.67	55.56	72.22	72.22	80.56
	Total	36	36	36	36	36	36

Table 4 :

 4 financial crisis, exchange rate regime switch and prudential regulation

	Number of countries	1995	1996	1997	1998	1999	2000
	realization of a financial crisis	4	2	7	8	7	1
	exchange rate regime* switch		9	12	9	11	8
	exchange rate regime* switch same year as a crisis year		1	7	3	4	0
	exchange rate regime* switch one year after a crisis year		2	1	2	4	1
	prudential regulation introduced		2	5	6	0	3
	prudential regulation introduced same year as a crisis year		0	2	2	0	0
	prudential regulation introduced one year after a crisis year		0	2	2	0	1
	*de facto, 8 classes.

Table 5 : Bank liquidity and official exchange rate regimes Dependent Variable

 5

		Liquid Assets	Net Loans	Liquid Assets	Liquid Assets	Interbank
		Total Assets	Total Assets	Cust & Sh.Term	Dep & Borrowing	Ratio
	Intercept	25.63766*** (<.0001)	59.74652*** (<.0001)	13.17182*** (0.0019)	13.33102*** (0.0012)	102.6992*** (<.0001)
	Total assets	-1.36E-6 (0.3047)	1.568E-6 (0.1980)	2.178E-6 (0.4336)	-2.91E-6 (0.2899)	-0.00002 (0.1658)
	equity to asset	0.039931**	-0.21036***	1.510442***	1.345849***	0.305106
	ratio	(0.0436)	(<.0001)	(<.0001)	(<.0001)	(0.4211)
	presence of prudential	2.052218*** (0.0043)	-1.61571** (0.0154)	-3.81709* (0.0675)	-5.28401*** (0.0065)	-11.104 (0.2374)
	regulation
	Lending rate	0.024513*** (0.0064)	-0.03734*** (<.0001)	0.018426 (0.5157)	0.060794** (0.0140)	0.019999 (0.8644)
	public	0.612127***	-0.52401***	0.499218***	0.593273***	3.803034***
	expenditures/GDP	(<.0001)	(<.0001)	(0.0066)	(0.0007)	(0.0001)
	rate of inflation	0.010895*** (0.0011)	-0.01079*** (0.0004)	0.015836* (0.0988)	0.006563 (0.3421)	0.071823 (0.1090)
	rate of growth	-0.11428** (0.0363)	0.276829*** (<.0001)	-0.83131*** (0.0007)	-0.72716*** (0.0020)	1.482873** (0.0411)
	realisation of a	-3.17001***	3.286887***	-5.76108**	-2.38877	-7.47819
	financial crisis	(<.0001)	(<.0001)	(0.0333)	(0.3503)	(0.4322)
	Lag of financial	2.846108***	-4.05153***	2.791148	4.668843*	29.46061***
	crisis	(<.0001)	(<.0001)	(0.2810)	(0.0558)	(0.0038)
	Independently	3.768529***	-4.1257***	14.42666***	16.05551***	48.68543***
	floating (official)	(<.0001)	(<.0001)	(<.0001)	(<.0001)	(<.0001)
	Soft Peg (official)	-3.68665*** (0.0010)	1.469475 (0.1715)	3.715822 (0.2597)	-3.84577 (0.2171)	-7.57154 (0.5648)
	Conventional fix	-0.25467	0.294396	3.694469	8.493383***	23.94733**
	(official)	(0.7851)	(0.7341)	(0.2251)	(0.0034)	(0.0451)
	Hard Peg	-0.86027	-3.39687**	13.63542**	17.12244***	111.1351***
	(official)	(0.5726)	(0.0152)	(0.0261)	(0.0033)	(<.0001)
	Number of Cross Sections	1016	973	696	396	776
	Series Length	6	6	6	6	6
	Haussman Test
	for Random	<.0001	<.0001	<.0001	<.0001	<.0001
	effects
	*** indicates significance at 1% level; ** indicates significance at 5% level; * indicates significance at 10% level;
	Significance level of Student statistics are in brackets.

Table 6 : Bank liquidity and de facto exchange rate regimes Dependent Variable

 6

		Liquid Assets	Net Loans	Liquid Assets	Liquid Assets	Interbank
		Total Assets	Total Assets	Cust & Sh.Term	Dep & Borrowing	Ratio
	Intercept	24.38215*** (<.0001)	59.68794*** (<.0001)	11.3588** (0.0101)	8.90899** (0.0387)	101.744*** (<.0001)
	Total assets	-1.71E-6 (0.1993)	1.911E-6 (0.1186)	1.566E-6 (0.5783)	-4.8E-6* (0.0826)	-0.00002 (0.2010)
	equity to asset	0.03575*	-0.20917***	1.483763***	1.333603***	0.478406
	ratio	(0.0721)	(<.0001)	(<.0001)	(<.0001)	(0.2199)
	presence of prudential	1.552667** (0.0307)	-1.36912** (0.0412)	-3.42881 (0.1036)	-6.85674*** (0.0008)	-8.17888 (0.4288)
	regulation
	Lending rate	0.026511*** (0.0034)	-0.03517*** (<.0001)	0.027274 (0.3421)	0.085416*** (0.0006)	-0.01541 (0.8997)
	public	0.679519***	-0.57022***	0.713421***	0.876599***	4.482071***
	expenditures/GDP	(<.0001)	(<.0001)	(<.0001)	(<.0001)	(<.0001)
	rate of inflation	0.008147** (0.0159)	-0.00833*** (0.0074)	0.009483 (0.3305)	0.002642 (0.7064)	0.010681 (0.8132)
	rate of growth	-0.07332 (0.1657)	0.278092*** (<.0001)	-0.58886** (0.0179)	-0.49066** (0.0386)	0.666137 (0.3516)
	realisation of a	-3.23195***	4.113413***	-9.46356***	-9.85611***	-19.8736**
	financial crisis	(<.0001)	(<.0001)	(0.0007)	(0.0004)	(0.0480)
	Lag of financial	3.275862***	-3.90833***	2.168562	3.056438	27.80246***
	crisis	(<.0001)	(<.0001)	(0.4106)	(0.2240)	(0.0078)

Independently floating 2.068342** (0.0272) -2.49055*** (0.0042) 12.88086*** (<.0001) 15.2697*** (<.0001) -12.3878 (0.3549) Managed 1.011312 (0.2869) -0.98663 (0.2738) 7.140021*** (0.0078) 12.47381*** (<.0001) 57.11853*** (<.0001) Conventional fix

		1.096032	-0.2	2.33338	8.597666***	-2.00915
		(0.1967)	(0.8003)	(0.3656)	(0.0004)	(0.8738)
	Hard Peg	4.273856** (0.0102)	-2.62795* (0.0888)	15.44732*** (0.0096)	26.65302*** (<.0001)	46.34848** (0.0263)
	Number of Cross Sections	1016	973	696	396	776
	Series Length	6	6	6	6	6
	Haussman Test
	for Random	<.0001	<.0001	.0001	<.0001	<0.0001
	effects
	*** indicates significance at 1% level; ** indicates significance at 5% level; * indicates significance at 10% level;
	Significance level of Student statistics are in brackets.

See Feldstein (2003), among others, and in addition to[START_REF] Chang | Financial Fragility and the Exchange Rate Regime[END_REF].

The other areas are monetary and financial policy transparency; fiscal transparency; securities; insurance; payments systems; corporate governance; accounting; auditing; and insolvency and creditor rights.

Writing the bank balance sheet as: Liquid Assets (LA) + Loans = Liquid Liabilities (LL) + Equity + Other Liabilities, and denoting Total Assets by TA, Total Liabilities and Equity by TLE (with of course: TA=TLE), a simultaneous increase in LA/TA and decrease in LA/LL imply an increase in LL/TLE.

e.g. their corollary 3.4, page 12, states that "equilibrium bank runs may occur in a currency board regime".


Jérôme Gallard
email: jerome.gallard@inria.fr

Kget+ : An efficient tool for managing VM image snapshots

Keywords: Virtualization, Grid Resource Management, Efficient VM Image Copy, Kget+

Virtualization technologies have recently gained a lot of interest in Grid computing as they allow flexible resource management. However, designing and implementing a complete framework to build VM images, to deploy and configure them automatically and to manage them (with migration and snapshotting operations) remains a real challenge. In this paper, after enumerating these challenges, we focus on the VM image snapshot management issue and present our tool, called Kget+, able to manage VM image snapshots in a very efficient way.

Introduction

Virtualization technologies provide flexible and powerful execution environments, offering isolation and security mechanisms, customization and encapsulation of entire application environments. Moreover, thanks to their suspend/resume and migration capabilities, they allow the bare hardware to be strongly decoupled from the system software, which is a predominant feature in the context of distributed architectures such as grids, which are exploited concurrently by multiple users. In this particular context, VMs can be exploited to encapsulate jobs and then make grid resource management easier. The challenge of managing applications on grids is moved to the problem of managing VMs on grids. The rest of this paper is organized as follows : Section 2 introduces issues implied by the use of VM technologies in grids and presents more precisely the problem of VM snapshot management. In Section 3 we present Kget+, a tool able to manage VM image snapshots in an efficient way. Section 4 concludes and gives some perspectives of work.

Issues implied by the use of VM technologies in grids

Designing and implementing a framework able to manage user jobs in VMs at grid level requires to consider each step of a common job submission in a grid context : (i) VM image creation, (ii) VM image management (iii) job submission, VM deployment and job starting, (iv) VM/job life cycle (VM migration, suspend/resume, snapshots, . . . ) and finally (v) job completion and VM shutdown. In this document, we focus on the VM storage management issue and more precisely, on the VM image snapshot issue by proposing a tool, called Kget+, able to copy efficiently VM image snapshots from n nodes to one frontend (more information about the other issues could be found in [1]).

The VM image snapshot management issue

One drawback of the use of VMs in grids and clusters relates to the VM image snapshot management. There are several methods to manage VM images (on each local node, on a remote server, ...), each method having their own good and bad points. In this paper we focus on the remote server method at cluster level by considering the copy of n VM image snapshots from n physical nodes to a frontend which implies a network bottleneck at the frontend side. To solve this problem, we have designed and implemented Kget+, which is presented in the next Section.

Kget+ : Design and Experiments

Kget+ is our prototype allowing to copy VM image snapshots from n nodes to one frontend in an efficient way. It follows two principles : (i) to regulate the network bandwidth from the frontend point of view, (ii) to free a large part of the set of nodes in a minimum of time. To do this, Kget+ makes sure that at all times one and only one node sends a VM image to the frontend (principle (i)). Parallelly, other nodes coordinate among themselves to group all VM images on a smaller number of nodes (principle (ii)). In this way, the network between all the nodes is used parallelly and the result is that several nodes are freed very quickly and the frontend network is never saturated. Of course this solution assumes that there is enough available disk space on the nodes to make the copies. -the destination node is already sending or receiving a VM snapshot, -the destination node has less VM snapshots than the sender node, -the sender node is already sending or receiving a VM snapshot. After implementing this algorithm, we made some evaluations of it on the Paravent cluster from Rennes Grid'5000 site3 [2]. In our experiments we launch a job composed of 64 VM images on 64 physical nodes and we measure the time needed to copy the VM image snapshots from all nodes to the frontend with multiple simultaneous scp, with Kaget4 and with our tool Kget+. The size of one VM image snapshot is approximately 512MBytes. Figure 1 presents the percentage of nodes freed (Yaxis) according to the elapsed time (X-axis). This figure shows that, thanks to Kget+, a good scheduling of the copies gives very efficient results. Indeed, with Kget+ all nodes are freed in less than 15 minutes whereas with multiple scp and Kaget all nodes are freed in less than 18 and 34 minutes respectively. In addition, with Kget+ 80% of the nodes are freed in less than 2 minutes (6% of the wall time).

Conclusion and Future Work

In this paper we present the design of Kget+, our prototype able to copy VM image snapshots from n physical nodes to one frontend in an efficient way. In addition we give results of preliminary experiments. This tool is able to schedule the copy of all the VM image snapshots from all the nodes to one frontend with the goal of : (i) regulating the network bandwidth from the frontend point of view, (ii) freeing a large part of the set of nodes in a minimum of time. This tool should be integrated with VMdeploy5 our VM management prototype able to deploy and manage VMs at grid level. This one needs improvements, however, it is a good framework to study one by one, all the issues implied by the use of VMs in grids which, from our point of view, will pave the way to scientific clouds.

  Bibliographie 1. Jérôme Gallard et al. VMdeploy, Improving Best-Effort Job Management in Grid5000. Technical Report RR-6764, INRIA, December 2008. 2. Raphaël Bolze et al. Grid'5000 : A Large Scale and Highly Reconfigurable Experimental Grid Testbed. International Journal of High Performance Computing Applications, 20(4) :481-494, 2006.

This could be easily extended to consider the whole size of VMs instead of the number.

https ://www.grid5000.fr

http ://taktuk.gforge.inria.fr/kanif/

https ://www.grid5000.fr/mediawiki/index.php/VMdeploy

The INRIA team carries out this research work in the framework of the XtreemOS project partially funded by the European Commission under contract #FP6-033576.


Omer Landry

Nguena Timo

A Decidable Timed µ-calculus for Event-Recording Automata

The Logic WTµ is considered. We show decidability of the satisfiability checking problem for a fragment of WTµ called C-WTµ. WTµ is an extension of the modal µ-calculus with event-recording clocks. C-WTµ is more expressive than Event-Recording logic, another EXPTIME complete decidable extension of the modal µ-calculus with event-recording clocks. Based on the techniques for deciding untimed µ-calculus, we present a set of rules for constructing tableaux for formulas of C-WTµ. The decidability problem is shown to be EXPTIME complete. We construct a witness event-recording automaton that satisfies a given C-WTµ formula.

Introduction

Formal methods need "good" and efficient formalisms to describe and specify models of systems. In this context, temporal and modal logics allow elegant and succinct representations for specifications. Decidability of satisfiability checking problem together with construction of witness models are important for logics. The satisfiability checking problem for a logic is to check whether a given formula has a model. In this paper, we consider the satisfiability checking problem for an interesting fragment of WT µ with respect to event-recording automata.

WT µ [START_REF] Landry | The logic wt µ[END_REF] is a "weak" timed extension of the standard µ-calculus [START_REF] Kozen | Results on the propositional µ-calculus[END_REF] for Event-Recording Automata [START_REF] Alur | Event-clock automata: A determinizable class of timed automata[END_REF]. The syntax of WT µ extends the syntax of the µ-calculus with two modal operators indexed with clock constraints. The existential modal operator indexed with a clock constraint ( g ) allows to describe a behaviour in a future time instant at which the clock constraint g is satisfied.

The universal modal operator indexed with a clock constraint ([g]) allows to describe all behaviours in all future time instants at which the constraint g is satisfied. Formulas of WT µ are boolean combinations of fixpoint formulas and formulas starting with modal operators. C-WT µ is a fragment of WT µ . When formulas are viewed as trees, C-WT µ requires that every modal quantification over events to be directly preceded by a modal quantification over delays; Additionally universal quantification over events must not be directly preceded by an existential quantification over delays. Models for WT µ and C-WT µ are Event-Recording Automata (ERA) [START_REF] Alur | Event-clock automata: A determinizable class of timed automata[END_REF]. ERA are finite graphs. Transitions in ERA are labelled with couples made of a clock constraint and an event. A clock constraint is just a conjunction of comparisons of clocks with constants. A transition can be fired when values of clocks satisfy its constraints; and when a transition is fired the unique clock associated to the event of the transition is reset. In ERA, Each clock refers to a single event. ERA are closed under boolean operations [START_REF] Alur | A theory of timed automata[END_REF].

The main contribution of this paper is an EXPTIME-Complete decision procedure for the satisfiability checking problem of C-WT µ . The procedure does not require limit on constants of models; it also constructs witness models. We briefly address relations between WT µ , C-WT µ and other timed extensions of the standard µ-calculus like the logic L ν [START_REF] Laroussinie | Compositional model checking of real time systems[END_REF] and Event-Recording Logic [START_REF] Sorea | A decidable fixpoint logic for time-outs[END_REF] (ERL). Modal operators ERL can be translated into equivalent modal operator of WT µ and modal operators of WT µ can be translated into equivalent modal operator of L ν . C-WT µ is more expressive than Event-Recording logic, another EXPTIME-Complete timed µ-calculus for event-recording automata. C-WT µ allows to characterise event-recording automata up to timed bisimulation and timed simulation [START_REF] Landry | On Characteristic Formulae for Event-Recording Automata[END_REF]. We also present a method to reduce the modelchecking problem of WT µ to the model-checking problem of the standard µcalculus which is the same as the problem of checking winning strategies in two player parity game [START_REF] Zielonka | Infinite games on finitely coloured graphs with applications to automata on infinite trees[END_REF]. The reduction leads to and EXPTIME algorithm.

For the satisfiability problem of C-WT µ , we use similar techniques to the satisfiability problem for the µ-calculus [START_REF] Streett | An automata theoretic decision procedure for the propositional mu-calculus[END_REF][START_REF] Niwiński | Games for the µ-calculus[END_REF] and ERL [START_REF] Sorea | A decidable fixpoint logic for time-outs[END_REF]. We present a set of reduction rules for constructing tableaux for WT µ formulas. We show that a formula is satisfiable if and only if its tableau contains a pre-model. From premodels we construct witness models. Pre-models are parts of tableaux. To keep track of the actual values of the clocks, premises and conclusions in our tableaux rules uses timing contexts. Timing contexts are well known equivalence classes of valuations of clocks called regions [START_REF] Alur | A theory of timed automata[END_REF]. Applying a rule not only reduces the formula but also changes the values of the clocks, by performing operations such as time elapse and clock reset. There will be finitely many labels for nodes of tableaux (this is because there is finitely many regions), and nodes of tableaux will be the states of witness models. Our tableau rules can not handle the satisfiability checking problem for formulas like h a > 1 a tt ∧ h a > 1 [a]ff as we will need to introduce new constants in models. The latter formula is not a C-WT µ formula; it requires that after one time unit delay, there exists a future time instant at which a can be fired and there exists another future time instant at which a can not be fired.

Related results. Event-Recording Automata (ERA) [START_REF] Alur | Event-clock automata: A determinizable class of timed automata[END_REF] is a restricted class of timed automata [START_REF] Alur | A theory of timed automata[END_REF]. TML [START_REF] Holmer | Deciding properties of regular real timed processes[END_REF], L t µ [START_REF] Sokolsky | Local model checking for real-time systems (extended abstract)[END_REF], T µ [START_REF] Henzinger | Symbolic Model Checking for Real-Time Systems[END_REF] and L ν [START_REF] Laroussinie | Compositional model checking of real time systems[END_REF] are timed logics for for timed automata. T µ is a timed extension of the µ-calculus. L ν is a fragment of T µ and it does not have the least fixpoint operator. L ν allows to characterise timed simulation and timed bisimulation between timed automata [START_REF] Aceto | Characteristic formulae for timed automata[END_REF]. The model-checking of L ν is EXPTIME Complete and the satisfiability checking problem for L ν have been left open [START_REF] Laroussinie | Compositional model checking of real time systems[END_REF]. The number of clocks in the models cannot be deduced from the number of clocks in a L ν formula. But, the satisfiability problem for L ν , with a restrictive bound assumption on clocks and constants in models, is decidable [START_REF] Laroussinie | Compositional model checking of real time systems[END_REF]. The satisfiability problem for ERL, without any bound assumption on constants in models, is EXPTIME Complete [START_REF] Sorea | A decidable fixpoint logic for time-outs[END_REF] and the construction of witness model is effective. ERL is more expressive than the event-recording part of timed linear-time logic EventClockTL [START_REF] Raskin | The logic of event clocks -decidability, complexity and expressiveness[END_REF]. WT µ is expressive enough for characterising timed simulation and timed bisimulation relations between ERA [START_REF] Landry | On Characteristic Formulae for Event-Recording Automata[END_REF]. One can check that characteristic formulas in [START_REF] Landry | On Characteristic Formulae for Event-Recording Automata[END_REF] belong to C-WT µ . They have also shown that ERL is a fragment of WT µ . D'Sousa [START_REF] Deepak | A logical characterisation of event recording automata[END_REF] gives a logical characterisation of ERA with a monadic second order logic, MSO er , interpreted over linear models.

Organisation of the paper. in the next section, we present Event-Recording Automata. In Section 3, we define WT µ , and C-WT µ ; we briefly compare WT µ , C-WT µ with ERL and L ν . We also present a µ-calculus based algorithm for the model-checking problem of WT µ . In Section 4, we consider the satisfiability problem of C-WT µ . We show that a formula is satisfiable if and only if its tableau contains a pre-model. At the end of Section 4, we discuss about the satisfiability checking problem of WT µ .

Event-Recording automata

The sets N, R + , are respectively the sets of natural and non-negative real numbers. We consider a finite set H of variables, called clocks. A clock valuation over H is a mapping v : H → R + that assigns to each clock a time value. The set of all clock valuations over H is denoted V H . Let t ∈ R + , the valuation v + t is defined by (v + t)(h) = v(h) + t, ∀h ∈ H. For a clock h ∈ H, we denote by v[h := 0] the valuation such that (v[h := 0])(h) = 0 and for every h

= h ′ (v[h := 0])(h ′ ) = v(h ′ ).
Finally, v 0 is the valuation that maps every clock on 0.

Given a set of clocks H, the set of clock constraints over H is defined by the grammar "g ::= h ∼ c | g ∧ g | true" where h ∈ H, c ∈ N, ∼ ∈ {≤, <, >, ≥} and true stands for true. We write v |= g (or v ∈ [[g]]) when the clock valuation v satisfies the clock constraint g. A M -rectangular constraint is a constraint of the form h∈H e h where e h is an equation of the form c ≤ h ≤ c, c < h < c + 1, M ≤ h ≤ M , or h > M with c < M . The bound M g of a constraint g is the maximal constant that occurs in g. It should be obvious that for every M ≥ M g , a constraint g can be decomposed into a finite set Rect M (g

) of M -rectangular constraints such that v |= g iff ∃g ′ ∈ Rect M (g) s.t v |= g ′ .
Given a constant M ∈ N, a set of clock H, the set V H can be partitioned into a finite set, denoted by Reg(M ), of equivalence classes called regions [START_REF] Alur | A theory of timed automata[END_REF]. For a given M , the number of regions is bounded by |H|!.2 |H| .(2.M + 2) |H| . It is standard that any region r from Reg(M ) can be represented by an atomic clock constraint that additionally uses equations of the form hh ′ ∼ c. For a valuation v, [v] M (or [v] when it is clear from the context) denotes the region that contains v. We also define r 0 = [v 0 ], v ↑= {v + t | t ∈ R + }; and given a region r, we define r ↑= {[v + t] | t ∈ R + and v ∈ r}.

In the context of event-recording automata, each clock refers to a specific event. Then, we associate clocks with letters of an alphabet. Given an alphabet Σ, we then denote by H Σ the set of clocks {h a | a ∈ Σ}. Sets of valuations, constraints, and M-rectangular constraints are denoted by V Σ , Gds Σ , and Agds Σ (M ).

Definition 1 An event-recording automaton (ERA) is a tuple P = P, Σ, p 0 , ∆ P where, P is a finite set of locations, p 0 ∈ P is the initial location,

∆ P ⊆ P × Gds Σ × Σ × P is a transition relation. The ERA is deterministic if [[g 1 ∧ g 2 ]] = ∅ whenever (p, g 1 , a, p 1 ) ∈ ∆ P and (p, g 2 , a, p 2 ) ∈ ∆ P .
The bound of an ERA P, M P is the maximal constant that occurs in its constraints. Given a constant M , we say an ERA is M -bounded iff its bound is smaller than M . The semantics of ERA are labelled transition systems.

A state of an event-recording automaton P as above defined, is a pair (p, v) where p is a location and v is a valuation over H Σ . The initial state of P is (p 0 , v 0 ) where v 0 maps all clocks in H Σ to 0. The semantics of an event-recording automaton P as above is the (Σ ∪ V Σ )-labelled transition system (LTS)

[[P]] = P ×V Σ , Σ∪V Σ , (p 0 , v 0 ), → where →⊆ (P ×V Σ )×(Σ∪R + )×(P ×V Σ ) is defined by: (p, v) v+t -→ (p, v + t) for every t ≥ 0; and (p, v) a -→ (p ′ , v[h a := 0]) if and only if there is p g,a
-→ p ′ ∈ ∆ P such that v |= g. Each clock of an event-recording automata records the amount of time elapsed since the last occurrence of its corresponding event. It is common to label continuous transition with delays in R + instead of valuations as above. The two representations are equivalent; the benefit of our representation will appear later in Sect. 3.

Let us present two abstractions for the semantics. The M -action abstraction is obtained from the semantics by replacing valuations on delay-transitions with M -rectangular constraints they satisfy.

Definition 2

The M -action abstraction of an ERA P, as above defined, is the

(Σ ∪ Agds Σ (M ))-LTS [P] M = P × V Σ , Σ ∪ Agds Σ (M ), (s 0 , v 0 ), ∆ v where, ∆ v ⊆ (P × V Σ ) × (Σ ∪ Agds Σ (M )) × (P × V Σ ) is defined by: (p, v) g ′ -→ (p, v + t) for any t ∈ R + s.t v + t |= g ′ with g ′ ∈ Agds(M ); and (p, v) a -→ (p ′ , v[h a := 0]) if there is (p, g, a, p ′ ) ∈ ∆ P with v |= g.
One can check that for every M ∈ N, [[P]] and [P] M are isomorphic.

Definition 3 The M -region abstraction of P is [P] M r = P × Reg(M ), Σ ∪ Agds(M ), (p 0 , r 0 ), ∆ r where, v 0 ∈ r 0 , ∆ r ⊆ (P × Reg(M )) × (Σ ∪ Agds Σ (M )) × (P × Reg(M )) is given by: (p, r) g ′ -→ (p, r ′ ) with r ′ ⊆ r ↑ and r ′ ⊆ g ′ ; and (p, r) a -→ (p ′ , r[h a := 0]) if there is (p, g, a, p ′ ) ∈ ∆ P with r ⊆ g. Proposition 4 Let P be an ERA. ∀M ≥ M P : [P] M is bisimilar 1 to [P] M r .
3 The Logic WT µ

We want a modal logic for semantics of ERA. Modalities of that logics should allow to quantify delay or discrete successors of semantics of ERA. The logic in [START_REF] Sorea | A decidable fixpoint logic for time-outs[END_REF] allows quantification on successions of a delay with an event. That kind of quantification is "weak" as for example they do not allows to characterise event-recording automata up to some behavioural relations [START_REF] Landry | On Characteristic Formulae for Event-Recording Automata[END_REF]. We introduced the logic WT µ [START_REF] Landry | The logic wt µ[END_REF].

Syntax and Semantics of WT µ

The syntax of WT µ [START_REF] Landry | The logic wt µ[END_REF] is the syntax of the standard µ-calculus [START_REF] Kozen | Results on the propositional µ-calculus[END_REF] augmented with two dual modalities indexed with constraints: the existential modality g and the universal modality [g].

Definition 5 Formulas of WT µ over an alphabet Σ, a finite set of variables Var = {X, Y, . . .} and Gds Σ are defined by the following grammar:

ϕ ::= tt | ff | X | ϕ ∧ ϕ | ϕ ∨ ϕ | a ϕ | g ϕ | [a]ϕ | [g]ϕ | µX.ϕ | νX.ϕ
where g ∈ Gds Σ ; the symbols tt and ff denote "true" and "false" formulas.

The following definitions are taken from [START_REF] Niwiński | Games for the µ-calculus[END_REF] and they are used in the context of WT µ . A variable X is bound in a formula ϕ if there is a sub formula σX.ψ(X) of ϕ with σ ∈ {µ, ν}. A well named formula is such that an expression µX.ϕ(X) (or νX.ϕ(X)) occurs at most once for each variable X. By renaming variables if necessary, every formula can be translated into an equivalent well named formula. In what follows, w.l.o.g we assume that formulas are well named. The binding definition of a bound variable X in a well named formula ϕ, Bd ϕ (X) is the unique sub formula of ϕ of the form σX.ψ(X); we call X a µ-variable when σ = µ, otherwise we call X a ν-variable. We will omit subscript ϕ when it causes no ambiguity. The dependency order over the bound variables of a formula ϕ, is the least partial order such that X is older than Y (and we write

X ≤ ϕ Y ) if X occurs in Bd ϕ (Y ) (and Bd ϕ (Y ) is a sub formula of Bd ϕ (X)). Given ϕ, Bd ϕ , and ψ a sub formula of ϕ, the expansion Exp Bdϕ (ψ) of ψ w.r.t Bd ϕ is defined by Exp Bdϕ (ψ) = ψ[Bd ϕ (X n )/X n ] • • • [Bd ϕ (X 1 )/X 1 ], where {X 1 , X 2 , • • • , X n } is an increasing chain of bound variables of ϕ with respect to ≤ ϕ .
WT µ is interpreted over (Σ∪V Σ )-LTS that may represent semantics of ERA.

Definition 6 For a (Σ ∪ V Σ )-LTS S = S, Σ ∪ V Σ , s 0 , ∆ S and an assignment V al : Var → 2 S , the set of states in which a formula ϕ is true, [[ϕ]] S V al is defined
inductively as follows:

[[X]] S V al := V al(X) [[ϕ 1 ∨ ϕ 2 ]] S V al := [[ϕ 1 ]] S V al ∪ [[ϕ 2 ]] S V al [[ϕ 1 ∧ ϕ 2 ]] S V al := [[ϕ 1 ]] S V al ∩ [[ϕ 2 ]] S V al [[ a ϕ]] S V al := {s | ∃s a -→ s ′ and s ′ ∈ [[ϕ]] S V al } [[ g ϕ]] S V al := {s | ∃s v -→ s ′ s.t v ∈ [[g]] and s ′ ∈ [[ϕ]] S V al } [[[a]ϕ]] S V al := {s | ∀s a -→ s ′ . s ′ ∈ [[ϕ]] S V al } [[[g]ϕ]] S V al := {s | ∀s v -→ s ′ s.t v ∈ [[g]]. s ′ ∈ [[ϕ]] S V al } [[µX.ϕ(X)]] S V al := {T ⊆ S | [[ϕ(X)]] S V al[X/T ] ⊆ T } [[νX.ϕ(X)]] S V al := {T ⊆ S | T ⊆ [[ϕ(X)]] S V al[X/T ] }
where for a set of states T ⊆ S, the assignment

V al[X/T ] is such that Y ∈ Var, V al[X/T ](Y ) = T if Y = X and V al[X/T ](Y ) = V al(Y ) otherwise.
We will omit V al when ϕ is a sentence.

Definition 7 Let P = P, Σ, p 0 , ∆ P be an ERA and V al : Var → 2 P ×VΣ be an assignment. P is a model of ϕ with respect to

V al iff (p 0 , v 0 ) ∈ [[ϕ]] [[P]] V al . In example, the formula ϕ = 0 < h a < 1 (( b tt ∧ [a]ff) ∨ c tt) is
such that events a, b and c are in the scope of the modality 0 < h a < 1 . The formula ϕ says that there is a time at which 0 < h a < 1 holds and at that time, the event c or b can be completed and the event a can not be completed.

M -rectangular formulas are formulas that only use M -rectangular constraints from Agds(M ). The M -rectangular formula associated to a formula ϕ is the formula Rect M (ϕ) defined inductively as follows:

• Rect M (ff) = ff, Rect M (tt) = tt, Rect M (X) = X, • Rect M (ϕ ∧ ψ) = Rect M (ϕ) ∧ Rect M (ψ), • Rect M (ϕ ∨ ψ) = Rect M (ϕ) ∨ Rect M (ψ), • Rect M ( a ϕ) = a Rect M (ϕ), Rect M ([a]ϕ) = [a]Rect M (ϕ), • Rect M ( g ϕ) = g ′ ∈Rect M (g) g ′ Rect M (ϕ), • Rect M ([g]ϕ) = g ′ ∈Rect M (g) [g ′ ]Rect M (ϕ), • Rect M (σX.ϕ(X)) = σX.Rect M (ϕ(X)) where σ is one of {µ, ν}. Let g, g 1 , g 2 , . . . , g n such that [[g]] = i=1..n [[g i ]]
. One can show that g ϕ is equivalent to i=1..n g i ϕ, and [g]ϕ is equivalent to i=1..n [g i ]ϕ; and then one can show the following result.

Proposition 8 Given a formula ϕ, a (Σ ∪ V Σ )-LTS S, for every M ≥ M ϕ , s ∈ [[ϕ]] S V al iff s ∈ [[Rect M (ϕ)]] S V al .
Modal operators are monotonic. As usual the Knaster-Tarski theorem allows to approximate fixpoints by iterative computations as follows:

• s ∈ [[µX.ϕ(X)]] S V al iff s ∈ λ [[µ λ X.ϕ(X)]] S V al and s ∈ [[νX.ϕ(X)]] S V al iff s ∈ λ [[µ λ X.ϕ(X)]] S
V al where λ is an ordinal and:

-s ∈ [[µ 0 X.ϕ(X)]] S V al and s ∈ [[ν 0 X.ϕ(X)]] S V al -s ∈ [[σ λ+1 X.ϕ(X)]] S V al iff s ∈ [[ϕ(X)]] S V al[X/σ λ X.ϕ(X)] (regeneration step). -When β is a limit ordinal, s ∈ [[µ β X.ϕ(X)]] S V al iff s ∈ λ<β [[µ λ X.ϕ(X)]] S V al and s ∈ [[ν β X.ϕ(X)]] S V al iff s ∈ λ<β [[µ λ X.ϕ(X)]] S V al .
Expressiveness and relations with L ν and ERL. The fragment of WT µ without the least fixpoint operator is a fragment of L ν for ERA. The inclusion is a consequence of that the modal operators [g]ϕ, g ϕ, [a]ϕ and a ϕ of WT µ are respectively equivalent to [δ](g → ϕ), δ (g ∧ ϕ), [a](h a in ϕ) and a (h a in ϕ) of L ν . As L ν is a fragment of T µ without the least fixpoint operator, we get that WT µ is a fragment of T µ . ERL is a fragment of C-WT µ . One can check that the proof in [START_REF] Landry | On Characteristic Formulae for Event-Recording Automata[END_REF] for the inclusion of ERLto WT µ works for C-WT µ . Moreover characteristic formulas in [START_REF] Landry | On Characteristic Formulae for Event-Recording Automata[END_REF] also belong to C-WT µ .The time-liveliness property requires an ERA to be able to fire an event e, in all states and in all future time instants (this is an important property in control theory [START_REF] Arnold | Nondeterministic controllers of nondeterministic processes[END_REF][START_REF] Bouyer | Modal logics for timed control[END_REF]). The property can be describe with the C-WT µ formula ϕ := νX.[tt] e X.

Model-Checking

The model-checking problem for WT µ is to check whether a given ERA is a model of a given formula. This section provides a new proof for the EXPTIME-Complete membership of the model-checking problem of WT µ . Another proof of this result appeared in [START_REF] Landry | On Characteristic Formulae for Event-Recording Automata[END_REF]. The original idea is to reduce the model-checking problem of WT µ to the model-checking problem of the standard µ-calculus.

First, we present an inductive procedure for checking whether a formula ϕ is true in a state s of a (Σ ∪ V Σ )-LTS:

• If ϕ is ff then return "no" • If ϕ is tt then return "yes" • If ϕ is ϕ 1 ∨ ϕ 2 then check if ϕ 1 is true in s or check if ϕ 2 is true in s • If ϕ is ϕ 1 ∧ ϕ 2 then check if ϕ 1 is true in s and check if ϕ 2 is true in s • If ϕ is a ϕ 1 then check whether ϕ 1 is
true in some a successor of s or return "no" if s does not have an a-successor

• If ϕ is [a]ϕ 1
then check whether ϕ 1 is true in every a-successor of s or return "yes" if s does not have an a-successor

• If ϕ is g ϕ 1 then check whether ϕ 1 is true in some v-successor of s such that v ∈ [[g]] or return "no" if s does not have an v-successor such that v ∈ [[g]] • If ϕ is [g]ϕ 1 then check whether ϕ 1 is true in every v-successor of s such that v ∈ [[g]] or return "yes" if s does not have an v-successor such that v ∈ [[g]] • If ϕ is µX.ϕ 1 (X) then check if µ λ X.ϕ 1 (X) is true at s for some ordinal λ • If ϕ is νX.ϕ 1 (X) then check if ν λ X.ϕ 1 (X) is true at s for every ordinal λ
The last two rules follows the Knaster-Tarski fixpoint computation rules. In the rule for the least fixpoint, one guesses a number for computation steps for showing that s ∈ [[µX.ϕ 1 (X)]]. In the rule for the greatest fixpoint operator, there is no guess and one must ensure that νX.ϕ 1 (X) is true in s at every computation step. In the rules for the operators ∨, a , g and µX., one chooses (or guesses) sub formulas, successors or ordinals.

A formula ϕ is true in a state s if some choices can be made in the above procedure to return "yes". If the procedure return "yes", it also assigns a set of true formulas to every state of the LTS meaning that every state of the LTS is an abstraction of the set of formulas assigned to it. Every step of the procedure makes a relation between a formula to verify and a next formula. A path in the procedure shows a trace of that relation. It is worth noticing that, according to the Knaster-Tarski fixpoint computation method, a trace that starts with a least fixpoint formula always ends while a trace that starts with a greatest fixpoint formulas may not. Additionally, traces that do not contains fixpoint formulas are necessarily finite, as each step reduces the size of the formula. Finite traces may ends with tt, ff or a formula of one of the forms a ϕ 1 , [a]ϕ 1 , g ϕ 1 , [g]ϕ 1 .

For the model-checking of WT µ with respect to ERA, an effective procedure may work on finite structures. But semantics of ERA are infinite structures. We use the region representation of semantics and we reduce the model-checking problem for WT µ with respect to ERA to the model-checking problem of the standard µ-calculus. For that purpose, we define the abstract semantics [ϕ] S V al for a WT µ formula ϕ over a (Σ ∪ Gds Σ )-LTS S and a valuation V al : Var → 2 S . The abstract semantics for all the operators but the modal operators indexed with constraints are obvious:

[ g ϕ] P V al := {p | ∃p g -→ p ′ s.t p ′ ∈ [ϕ] P V al } [[g]ϕ] P V al := {p | ∀p g -→ p ′ . p ′ ∈ [ϕ] P V al }
The abstract semantics of WT µ is very close to the semantics of the µ-calculus; equality tests are performed between labels of transitions and indexes in modal operators. The two non standard steps of an abstract model-checking procedure work as follows: if ϕ is g ϕ 1 then check whether ϕ 1 is true in some g-successor of s or return "no" if s does not have a g-successor

such that v ∈ [[g]]. If ϕ is [g]ϕ 1
then check whether ϕ 1 is true in every g-successor of s or return "yes" if

s does not have an v-successor such that v ∈ [[g]].
Proposition 9 For any ERA P, any sentence ϕ, for every

M ≥ max(M ϕ , M P ), (p, v) ∈ [[ϕ]] [[P]] iff (p, [v] M ) ∈ [[Rect M (ϕ)]] [P] M r , .
Our proof for Proposition 9 will use Proposition 4 and Proposition 8. It follows that model-checking algorithms for the µ-calculus [START_REF] Kozen | Results on the propositional µ-calculus[END_REF] can be easily adapted for the model-checking of WT µ .

Theorem 10 The model-checking problem for WT µ is EXPTIME Complete.

The lower bound comes from that ERL is a fragment of WT µ and the modelchecking of ERL is EXPTIME Complete [START_REF] Sorea | A decidable fixpoint logic for time-outs[END_REF]. The EXPTIME membership (see [START_REF] Landry | The logic wt µ[END_REF] for more details) is a consequence of the EXPTIME membership of the model-checking problem of the standard µ-calculus [START_REF] Emerson | Tree automata, µ-calculus and determinacy[END_REF] in relation with the problem of checking the existence of winning strategy in a two player parity game [START_REF] Zielonka | Infinite games on finitely coloured graphs with applications to automata on infinite trees[END_REF]. The use of regions does not change the complexity.

Satisfiability of C-WT µ

The satisfiability problem is to check whether a given formula has a model. Model for formulas are event-recording automata or more precisely (R + ∪ Σ)-LTS that may represent the semantics of event-recording automata. It is worth noticing that the satisfiability problem is somehow related to the model-checking problem. Here, the exercise is to guess ERA from formulas. Consider the WT µ formula ϕ := h a > 1 [a]ff∧ h a > 1 a tt. The formula ϕ requires that there are one time instant satisfying h a > 1 at which event a must occur and one time instant satisfying h a > 1 at which event a never occurs. The union of the semantics of constraints on the outgoing transitions from the initial state of a model of ϕ should be strictly contained in the semantics of h a > 1. For instance the constraint on the transition of a model with a single must have one of the forms n < h a or m 1 < h a < m 2 where n > 1 and m 2 are new constants. Procedure for the satisfiability checking problem of WT µ must be able to introduce constants that do not appears in formulas. Such a procedure (if it exists) may become very sophisticated for formulas with fixpoints operators.

In this section we consider the satisfiability checking problem of C-WT µ . C-WT µ is a fragment of WT µ . Formulas of C-WT µ are such that if we look at a formula as a tree, then the modalities indexed with constraints and with events must alternate on each path. C-WT µ also requires that in the tree representation of a modality [a] must not follow a modality g .

Definition 11

Formulas ϕ of C-WT µ (WT µ for control) over an alphabet Σ, a finite set of variables Var and Gds Σ are defined by the following grammar:

ϕ ::= tt | ff | X | ϕ ∧ ϕ | ϕ ∨ ϕ | g ψ e | [g]ϕ e | νX.ϕ | µX.ϕ
where X ∈ Var, g ∈ Gds Σ , ϕ e is a boolean combination of formula of the forms a ϕ or [a]ϕ and ψ e is a boolean combination of formulas of the form a ϕ.

The formula ϕ just above is not from C-WT µ because the formula [a]ff appears in the scope of 0 < h a < 1 . We stress that C-WT µ is an interesting fragment of WT µ . It allows to characterise ERA up to behavioural relation such as timed bisimulation and timed simulation. Indeed one can check that characteristic formulas in [START_REF] Landry | On Characteristic Formulae for Event-Recording Automata[END_REF] conform to the syntax C-WT µ . C-WT µ allows to describe basic requirement for controllers of event-recording automata.

Our method for the satisfiability checking problem use tableaux-based methods like in [START_REF] Streett | An automata theoretic decision procedure for the propositional mu-calculus[END_REF][START_REF] Niwiński | Games for the µ-calculus[END_REF][START_REF] Sorea | A decidable fixpoint logic for time-outs[END_REF]. W.l.o.g we consider rectangular formulas.

Tableau, Trace and Pre-model

Tableaux are built using the system of tableau rules. A rule is of the form T1 T2 ...Tn T

where T and T i for every i = 1..n are sequent made of a set of formulas (satisfiability objectives) and a region (timing context). The tuples over the lines of a rules (T i for every i = 1..n) are the premises and the tuple T below the line of a rule is the conclusion. A rule as above is interpreted as follows: verifying whether the formulas in the conclusion are satisfiable from the timing context is reduced to checking if the formulas in all (some) hypothesis are satisfiable in their corresponding timing context. Definition 12 Let a ϕ be a C-WT µ formula and let Bd ϕ be its binding function. We define the system of tableau rules SR ϕ c parametrised by ϕ, its binding function and the set of regions Reg(M ):

{ff}; ∅ {ϕ, Γ}; ∅ (ff r ) {ϕ 1 , Γ}; r {ϕ 2 , Γ}; r {ϕ 1 ∨ ϕ 2 , Γ}; r (∨) {ϕ 1 , ϕ 2 , Γ}; r {ϕ 1 ∧ ϕ 2 , Γ}; r (∧) {ff}; ∅ { g ϕ, Γ}; r s.t [[g]] ∩ r ↑= ∅ (fte) {Γ}; r {[g]ϕ, Γ}; r s.t [[g]] ∩ r ↑= ∅ (wtt) {ϕ(X), Γ}; r {νX.ϕ(X), Γ}; r (ν) {ϕ(X), Γ}; r {X, Γ}; r (reg) Bd ϕ (X) = σX.ϕ(X) {ϕ(X), Γ}; r {µX.ϕ(X), Γ}; r (µ) {ϕ | (g)ϕ ∈ Γ ri }; r i ∀r i ∈ r ↑ Γ; r (delay) ϕ ∪ {ψ | [a]ψ ∈ Γ}; r[h a := 0] for each a ϕ ∈ Γ Γ; r (mod)
where Γ ri is the set of formulas in Γ of the of form g ϕ or

[g]ϕ s.t r i ⊆ [[g]].
The system of rules above has ten rules; almost as many rules as in the model checking procedure in the previous subsection. Formulas can not be satisfied from an empty timing context and then the rule ff r replaces formulas in the conclusion by the formula ff. The rule fte is applied when a formula in the conclusion ( g ϕ) requires that the future of the timing context in conclusion satisfies a constraint whereas it is not possible. The rule wtt discards formulas that start with universal modality indexed with a constraint which can not be satisfied by the future of the timing context in the conclusion. When applying the rule (delay) we require that every formula in the conclusion should be one of the forms ff, tt, g ψ or [g]ψ with g ∩ r ↑ = ∅; in this case the satisfiability checking of the conclusion is reduced to the satisfiability checking of formulas behind the modal operators in the appropriate timing context. When applying the rule (mod) we require the form of every formula in conclusions to be one of ff, tt, a ψ or [a]ψ; as we are trying to build a model, a reduction with the rule (mod) is done as soon as conclusions contain a formula of the form a ψ. Definition 13 A tableau for a formula ϕ from a region r 0 is a tree T ϕ = N, E, L where N is the set of nodes, E is the set of edges, and L is a labeling function such that:

1. The root n 0 of T ϕ is labeled by {ϕ}; r 0 2. The sons of any node n are created and labeled according to the rules of systems SR ϕ . It is required the rules (mod) and (delay) are applied only when no other rule is applicable.

Remark that a conclusion in a tableau never contains at the same time a formula starting with a modality indexed with a guard and a formula starting with a modality indexed with an event. The formula part of timed sequents on which no rule is applicable never contain formulas of the forms a ψ, g ψ and [g]ψ.

Given a node n of a tableau with L(n) = Γ; r, L 1 (n) = Γ and L 2 (n) = r denotes respectively the formula and the timing part of L(n). A L(n) is satisfiable iff every formula ϕ in L 1 (n) is satisfiable from the timing context L 2 (n). The construction of a tableau for a formula can be seen as a procedure for checking, for every node n whether every formula ϕ ∈ L 1 (n) is satisfiable from L 2 (n). This procedure is inductive; therefore there are links between formulas in the conclusion and formulas in premises. How we get a path in the (abstract) model-checking procedure is very similar to how we get a path in the tableau. But paths of the (abstract) model-checking procedure contains links between formulas while paths in tableaux do not. This is because formula part of sequents are sets of formulas.

Definition 14 Given a path π of T ϕ = N, E, L , a trace on π will be a function Tr that assigns a tuple made of a formula and a region to each node in some initial segment of π, according to the rules applied for the construction of π. Tr 1 and Tr 2 denotes the formula part and the timing part of Tr(n). Tr satisfies the following conditions:

1. If Tr(n) is defined then Tr 1 (n) ∈ L 1 (n) and Tr 1 (n) = L 1 (n).
2. If the rule applied at the node m is not directed (ordered) by Tr(m) then the son n ∈ π of m is such that Tr(m) = Tr(n).

3. If the rule applied at the node m differs from (mod), then the tuple Tr(n) of the son n ∈ π of m is one of the results of the application.

4. If the rule (delay) is applied at the node m and the son n ∈ π of m is labeled by {ϕ | (g)ϕ ∈ Γ ri }; r i then:

• Tr(n) is equal to ϕ; r i if Tr(m) = (g)ϕ; r • Otherwise Tr(n) is undefined.
5. If the rule (mod) is applied at m and the son n ∈ π of m is labeled by

ϕ ∪ {ψ | [a]ϕ ∈ Γ}; r[h a := 0]
for some a ϕ ∈ Γ then:

• Tr(n) = ϕ; r[h a := 0] if Tr(m) = a ϕ; r • Tr(n) = ψ; r[h a := 0] if Tr(m) = [a]ψ; r
• Otherwise Tr(n) is undefined and Tr(m) is the last element of the trace.

The notion of traces in paths of tableaux links formulas in premises with formulas in conclusion. By this way, we are able to handle computational steps for fixpoint formulas. We recall that in the rules above computational steps are given by the rules (reg) and (σ).

A variable X is regenerated on a trace Tr of some path if and only if for some m and its son n on the path Tr 1 (m) = X and Tr 1 (n) = ψ(X) with Bd ϕ (X) = σX.ψ(X). A µ-trace is a infinite trace on which the oldest variable regenerated infinitely often is a µ-variable; or a maximal finite trace, ending with a tuple the formula part of which contains ff. A pre-model Prem is a part of a tableau T ϕ satisfying the four conditions: the root of T ϕ belongs to Prem; if a disjunctive node belongs to Prem, then only one of its son belongs to Prem; for all other kinds of nodes, if a node belongs to Prem then all its successors too; there is no path with a µ-trace in Prem.

Formulas part of sequents are set of formulas and we need to count computational steps for every fixpoint formulas in sequents. A signature sig = (α 1 , α 2 , . . . , α n ) is a sequence of ordinals value of which depends on a state. We distinguish µ-signature from ν-signature that we simply call signature when it is clear from the context.

Let S = S, Σ ∪ V Σ , s 0 , ∆ S be a (Σ ∪ V Σ )-LTS. Let ψ be a sentence. If s ∈ [[Exp Bdϕ (ψ)]] S then, ψ has the µ-signature µ sig(ψ, s) = (α 1 , . . . α d µ ) in s if µ sig(s, ψ) is the least (in lexicographical order) sequence of ordinals such that s ∈ [[Exp Bd ′ ϕ (ψ)]] S where Bd ′ ϕ is obtained from the binding function Bd ϕ by changing definitions of X i (for i = 1, . . . , d µ ) from Bd ϕ (X i ) = µX i .ϕ i (X i ) to Bd ′ ϕ (X i ) = µ αi X i .ϕ i (X i ). If s ∈ [[Exp Bdϕ (ψ)]] S then, ψ has the ν-signature ν sig(ψ, s) = (α 1 , . . . α d ν ) in
We need some definition for the construction of witness model. From the definition of the tableau system of rules, applying a rule different from (mod), (delay) and (∨) to a node of a tableau generates a unique successor. In a pre-model we choose only one son of a disjunctive node and all the sons of a modal or a delay node. It follows that in a symbolic pre-model, the nodes with more that one successor are modal or delay nodes. Given a node n of Prem we denote des α (n) the closest descendant of n or n itself in Prem that is either a delay node, a modal node, or a leaf. Observe that, if n is the root of Prem or n is a successor of a modal node of Prem, then des α (n) is a delay node or a leaf; if n is a successor of a delay node of Prem, then des α (n) is a modal node. Given a pre-model Prem for a formula ϕ, the model based on Prem is the ERA P = P, Σ, p 0 , ∆ P such that: p 0 = des α (n 0 ) where n 0 is the root of Prem; P consists of all the leaves and delay nodes of Prem; (p, g, a, des α (n ′ )) ∈ ∆ P if there is in Prem a successor n of p obtained by reducing a region r i ⊆ g with g ∈ Agds(M ϕ ) and a successor n ′ of des α (n) obtained by reducing an action a. In Consequence, the maximal constant in the model constructed from a premodel and the maximal constant in the formula are equal; constraints in the model are rectangular.

A detailed proof for Proposition 17 can be found in Appendix.

Proposition 17 A formula ϕ is satisfiable iff T ϕ contains a pre-model.

The Proof of Proposition 17 is decomposed into the proof of Lemma 18 for the "if" part and the proof of Lemma 19 for the "only if" part.

Lemma 18 Given a formula ϕ, ϕ is satisfiable if there is a pre-model in T ϕ Proof If ϕ is satisfiable then there exists an ERA model of ϕ, and by definition (p 0 , v 0 ) ∈ [[ϕ]] [[P]] . Without the loss of generality we can assume that ϕ is rectangular. By Proposition 9, for every M ≥ max(M P , M ϕ ), we have that (p 0 , [v 0 ] M ) ∈ [ϕ] P M reg . Consider T ϕ the tableau for ϕ; then we choose the nodes of T ϕ that we include in the pre-model Prem accordingly to a marking relation M : N → 2 P ×Reg(M ) S. It will be defined in such a way that (1): (p, r) ∈ M (n) if and only if (p, r) ∈ [ϕ] P M reg for every ϕ ∈ L 1 (n). First, we put (p 0 , [v 0 ] M ) in M (n 0 ) with n 0 being the root of T ϕ . This is consistent as P is a model of ϕ and then

(p 0 , [v 0 ] M ) ∈ [ϕ] [P] M reg .
Let us denote by s n a state (p, r) of [P] M reg assigned to a node n of the tableau.

Then, if we assume that the node n has been included in the pre-model Prem with s n ∈ M (n), we choose the next node to include in the tableau using the following rules:

• The only son n ′ of some node n, marked with s n , on which an unary rule (ff r , f te, wtt, ∧, reg, µ, or ν) was applied is included in Prem and we set s n ∈ M (n ′ ).

• If n is a disjunctive node, then s n is put into the marking of the son for which it has the least µ-signature. By Lemma 15, such a son exists.

• If n is a delay node, then we add all the sons of n in Prem. Each son n ′ of n is the result of the reduction of a set of formulas of the form g ψ or [g]ψ with respect to a region r i . Then, we set s n ′ ∈ M (n ′ ) where s n ′ is the unique state such that s n g -→ s n ′ .

• If n is a modal node, then we add all the sons of n in Prem. Each son n ′ of n is the result of the reduction of a formula of the form a ψ. Then, we set s n ′ ∈ M (n ′ ) where s n ′ is a state such that s n a -→ s n ′ and µ sig( a ϕ, s n ) ≥ µ sig(ϕ, s n ′ ). By Lemma 15, such a son exists.

By Property (1) above, it is obvious that every leaf of Prem does not contain ff. It remains to show that the tree we have constructed does not have an infinite with a µ-trace. Now, assume that there is an infinite path π that has a µ-trace on it. Then, there is an oldest µ-variable X i infinitely often regenerated along the trace. According to Lemma 15, from the point when no variable older that X i is regenerated µ-signatures of formulas on that trace never increase on position 1, . . . , i -1. Then maximal signature of formulas on the trace considered up to position i never increases and decreases every time X i is regenerated. In the other words, µ-signature decreases infinitely often in position i. This is a contradiction because sequences of ordinals of bounded length are well-ordered.

Lemma 19 Given a formula ϕ, if there is a pre-model in T ϕ , then ϕ is satisfiable.

Proof

The proof is dual to the proof of Lemma 18. Assume that ϕ has a symbolic pre-model Prem and ϕ is not satisfiable. Let M = M ϕ . Consider P, the model associated to Prem. From the remark above,

M P = M ϕ . If (p 0 , v) ∈ [[ϕ]] [[P]] ,
then by Proposition 9 we get that, (p

0 , [v] M ) ∈ [ϕ] [P] M
reg . Now, we show that Prem contains a path π with a µ-trace Tr = {ϕ m ; r m } m∈π . The path π and the trace Tr are built in the following way:

• π starts at m 0 and ϕ m0 = ϕ.

• Assume that, we built Tr up to the tuple ϕ m ; r m with, ϕ m ∈ L 1 (m) and r m ∈ L 2 (m), such that (des α (m), r m ) ∈ [Exp bdϕ (ϕ m )] [P] M reg . The formula of the next tuple (the timing part is obvious) is selected as follows:

1. If m is not a delay nor a modal node, then the only son m ′ of m is such that

-L 2 (m) = L 2 (m ′
) and there are equal to r m .

ϕ m ′ = ϕ m if ϕ m was not reduced by the rule.

-

ϕ m ′ = ϕ 1 with ϕ m = ϕ 1 ∧ ϕ 2 , if ν sig(ϕ m , (des α (m), r)) ≥ ν sig(ϕ 1 , (des α (m), r)); otherwise ϕ m ′ = ϕ 2 . -ϕ m ′ is the formula that occurs in L 1 (m ′ ) if ϕ m = ϕ 1 ∨ ϕ 2 .
We remark that, the choice in this case is directed by Prem. -In the other sub cases i.e (ff, f te, wtt, µ, ν or reg), we just take the resulting formula as the one for the next tuple of the trace.

2. If m is a delay node and ϕ m is of the form g ψ or [g]ψ and there is a son m ′ of m the formula part of which contains ψ, then we take

ϕ m ′ = ψ. The region part of m ′ is a region r ′ ∈ r m ↑. Of course, des α (m ′ ) is a modal node.
3. If m is a modal node, it is necessarily the closest descendant of a successor n ′ (with respect to some region r m ) of some delay node n; then,

if ϕ m = a ψ, there is a son m ′ of m the formula part of which was obtained by reducing ϕ m , and the timing part of which is r m [h a := 0]. We take ϕ m ′ = ψ.

-if ϕ m = [a]ψ, then because (des α (m), r m ) ∈ [ϕ m ] [P] M reg , there exists a state p ′ , g such that des α n g,a -→ p ′ is in P and ν sig([a]ψ, (des α (n), r m )) = ν sig(ψ, (p ′ , r m [h a := 0]) with r m ∈ g and g ∈ Agds(M ϕ ). We take ϕ m ′ = ψ and r m ′ = r m [h a := 0]
We remark that Tr is a valid trace of Prem and we distinguish two cases:

1. The trace is finite;

• If the trace ends with the formula ff, then we get a contradiction with that P derived from Prem; Indeed a trace of Prem never ends with ff.

• If the trace ends at the node m with the formula ϕ m = tt, then m is a leaf or delay node and obviously, (des α (m), r m ) ∈ [tt] [P] M reg , leading to a contradiction with the hypothesis.

• If the trace ends with a formula of form [g]ϕ, then the region at node m can never reached g meaning that [g]ϕ is satisfied at m. We also get a contradiction with our hypothesis.

• Assume that the trace ends at the node m with a formula of the form [a]ϕ. There is a unique ancestor n of node m which is a delay node such that no delay node occurs between n and m. The selected formula at the node n that occurs in the trace is of the form (g)ψ and ψ is a boolean combination of formulas containing [a]ϕ. Let p be the state in P that corresponds to the node n. Such a state exits because n is a delay node. Let r be the region at the node m and r ′ be region at the node n. Because m is a son of n, we have that r ∈ r ′ ↑. Additionally, by hypothesis, (p, r ′ ) ∈ [(g)ψ]

[P] M reg . Because the trace is maximal, there is no transition from p labelled with (g, a)

for the unique constraint g ∈ Agds(M ) such that r ⊆ g. It follows that in [P] M reg there a unique outgoing transition (p, r ′ ) g -→ (p, r) and there is no outgoing transition from (p, r) labelled with a, involving that (p, r) ∈ [[a]ϕ] [P] M reg . This leads to a contradiction with that in the trace ν sig((g)ψ, (p, r ′ )) = ν sig([a]ϕ, (p, r)). Indeed, remember that the trace has been built by choosing at every node, the formula and the configuration with the least ν-signature.

2. If the trace is infinite, then because the ν-signature decreases along the trace and the formula is of finite length, there is necessarily a µ-variable X that is infinitely often regenerated and no older variable than X is infinitely often regenerated. This is a contradiction with that Prem does not contain such a trace.

Let us discuss the complexity of the satisfiability problem for C-WT µ . The satisfiability problem for C-WT µ is EXPTIME Complete in the size of the formula, in the size of the alphabet, and in the size of the encoding of the maximal constant appearing in constraints of the formula. The EXPTIME hardness follows from ERL is included in C-WT µ and the satisfiability problem of ERL is EXPTIME hard [START_REF] Sorea | A decidable fixpoint logic for time-outs[END_REF]. Arguments for the EXPTIME membership are the same as arguments for the EXPTIME membership for the satisfiability procedure for ERL [START_REF] Sorea | A decidable fixpoint logic for time-outs[END_REF] and the µ-calculus [START_REF] Streett | An automata theoretic decision procedure for the propositional mu-calculus[END_REF][START_REF] Niwiński | Games for the µ-calculus[END_REF]. Indeed, One can construct is a finite Rabin tree-automaton over a single alphabet, with n = 0(2 |ϕ| × |Reg(M ϕ )|) states and m = |ϕ| pairs2 , which recognises pre-models for a formula ϕ. We recall that |Reg(M ϕ )| ∈ O(2 HΣ × 2 C Mϕ ) where C Mϕ is the length of the binary encoding of M ϕ . It have been shown [START_REF] Emerson | Automata, tableaux and temporal logics (extended abstract)[END_REF] that for a Rabin tree-automaton over a single alphabet that have an accepting run, there is a graph with states of the automaton as nodes which unwinds to an accepting run of the automaton. The test of the emptiness of the graph obtained from the pre-model and the Rabin-tree automaton is in O((mn) 3m ). In consequence we get the EXPTIME membership.

On the Satisfiability of WT µ

The procedure above can not work for the satisfiability problems of WT µ . This is because models may need constants that are strictly greater than the maximal constant occurring in formulas. We can also consider a situation when we impose a maximal constant with which the clocks can be compared in the models. Such a constant can be greater than the maximal constant occurring in the formula. Under such an assumption, the satisfiability problems (non deterministic and deterministic model) for WT µ are decidable and the construction of witness model is also effective.

Conclusion and Perspectives

We presented WT µ as a timed µ-calculus for Event-Recording Automata. We presented an EXPTIME Complete decidable fragment of WT µ called C-WT µ . The decision procedure for the satisfiability problem of C-WT µ does not need limit assumption on constants the models and it constructs witness models. C-WT µ is more expressive than Event-Recording Logic and it allows to characterise event-recording automata up to timed simulation and timed bisimulation relations whereas ERL does not. The complexity for the satisfiability checking problems for C-WT µ and ERL are the same. Relation between modalities of C-WT µ and L ν , and results in [START_REF] Bouyer | Modal logics for timed control[END_REF] let us believe the existence of an interesting decidable fragment of L ν (with timed automata) without limit assumption on constants of models, but with a bound assumption on the clocks in the models. Work in progress apply the decidability result for the satisfiability checking problem of C-WT µ to the synthesis of event-recording automata based controller. Future works include the satisfiability checking problem of full WT µ .

One considers the timed-abstract bisimilarity relation between [[P]] and [P]M r[START_REF] Alur | A theory of timed automata[END_REF].

The construction of pairs follows the relation order between fixpoint variables in formulas.

s if ν sig(s, ψ) is the least (in lexicographical order) sequence of ordinals such that s ∈ [[Exp Bd ′ ϕ (ψ)]] S where Bd ′ ϕ is obtained from the binding function Bd ϕ by changing definitions of

The proof of Lemma 15 is standard from the proof a similar Lemma in [START_REF] Niwiński | Games for the µ-calculus[END_REF].

Lemma 15 Let µ sig(ϕ, s) the signature of ϕ at s, it is true that:

Proof

Considering the last cases, we suppose that S, s |= Exp Bdϕ (X i ) with Bd ϕ (X i ) = µX i .ψ i (X i ). X j occurs in ψ i (X i ) implies that X i ≤ ϕ X j and X j is free ψ i (X i ). Let µ sig(X i , s) = (α 1 , α 2 , . . . , α n ) and Bd ′ obtained from Bd ϕ by changing definitions of

It follows from the definition of the signature that S, s |= µ αi X i .ψ(X i ). Since α i should be a finite ordinal, it follows that S, s |= ψ(µ αi-1 X.ψ(X i )), which means that the signature of ψ(µ αi-1 X i .ψ(X i )) at s is (α 1 , . . . , α i-1 , α i -1, α ′ i+1 , . . . , α ′ d µ ) and is lower than sig(W i , s). The difference occurs at the position i.

Observe that Lemma 15 translates to ν-signature after interchanging µ with ν, with [], ∨ with ∧.

Satisfiability Results

Now we will sketch a proof for the following theorem.

Theorem 16 There is an EXPTIME Complete decision procedure in the size of the formula that checks if a formula ϕ is satisfiable. The construction of a witness model is effective.