Tim Xiao
email: tim.xiao@bmo.com

A New Model for Pricing Collateralized Financial Derivatives

Keywords: collateralization, asset pricing, plumbing of financial system, swap premium spread, CVA, VaR, interaction between market and credit risk

This paper presents a new model for pricing financial derivatives subject to collateralization. It allows for collateral arrangements adhering to bankruptcy laws. As such, the model can back out the market price of a collateralized contract. This framework is very useful for valuing outstanding derivatives. Using a unique dataset, we find empirical evidence that credit risk alone is not overly important in determining credit-related spreads. Only accounting for both collateral posting and credit risk can sufficiently explain unsecured credit costs. This finding suggests that failure to properly account for collateralization may result in significant mispricing of derivatives. We also empirically gauge the impact of collateral agreements on risk measurements. Our findings indicate that there are important interactions between market and credit risk.

Unlike generic mid-market swap rates, swap premia are determined in a competitive market according to the basic principles of supply and demand. A swap client first contacts a number of swap dealers for a quotation and then chooses the most competitive one. If a premium is too low, the dealer may lose money. If a premium is too high, the dealer may lose the competitive advantage.

Unfortunately, we do not know the detailed allocation of a swap premium, i.e., what percentage of the adjustment is charged for each factor. Thus, a direct empirical assessment of the impact of collateralization on swap rate is impossible.

To circumvent this difficulty, this article uses an indirect empirical approach. We define a swap premium spread as the premium difference between two swap contracts that have exactly the same terms and conditions but are traded with different CSA counterparties. We reasonably believe that if two contracts are identical except counterparties, the swap premium spread should reflect counterparty credit risk only, as all other risks/costs are identical.

Empirically, we obtain a unique proprietary dataset from an investment bank. We use these data and a statistical measurement 2 R to examine whether credit risk and collateralization, alone or in combination, are sufficient to explain market swap premium spreads. We first study the marginal impact of credit risk. Since credit default swap (CDS) premium theoretically reflects the credit risk of a firm, we use the market swap premium spreads as the response variable and the CDS premium differences between two counterparties as the explanatory variable. The estimation result shows that the adjusted 2 R is 0.7472, implying that approximately 75% of market spreads can be explained by counterparty credit risk. In other words, counterparty risk alone can provide a good but not overwhelming prediction on spreads.

We then assess the joint effect. Because implied or model-generated spreads take into account both counterparty risk and collateralization, we assign the model-implied spreads as the explanatory variable and the market spreads as the response variable. The new adjusted 2 R is 0.9906, suggesting that counterparty risk and collateralization together have high explanatory power on premium spreads. The finding leads to practical implications, such as collateralization modeling allows forecasting credit spread.

Second, how does collateralization affect counterparty credit risk? Credit value adjustment (CVA) is the most prominent measurement in counterparty credit risk. We select all the CSA counterparty portfolios in the dataset and then compute their CVAs. We find that the CVA of a collateralized counterparty portfolio is always smaller than the one of the same portfolio without collateralization. We also find that credit risk is negatively correlated with collateralization as an increase in collateralization causes a decrease in credit risk. The empirical tests corroborate our theoretical conclusions that collateralization can reduce CVA charges and mitigate counterparty risk.

Finally, how do collateralization and credit risk, either alone or in combination, impact market risk? How do they interact with each other? Value at risk (VaR) is the regulatory measurement for market risk We compute VaR in three different cases -VaR without taking credit risk into account, VaR with credit risk, and VaR with both credit risk and collateralization. We find that there is a positive correlation between market risk and credit risk as VaR increases after considering counterparty credit risk. We also find that collateralization and market risk have a negative correlation, i.e., collateral posting can actually reduce VaR. This finding contradicts the prevailing belief in the market that collateralization would increase market risk (see Collateral Management -Wikipedia).

The rest of this article is organized as follows: First we present a new model for pricing collateralized financial derivatives. Then we discuss empirical evidences. Finally, the conclusions and discussion are provided. All proofs and detailed derivations are contained in the appendices.

Pricing Collateralized Financial Derivatives

A CSA is a legal document that regulates collateral posting. It specifies a variety of terms including threshold, independent amount, and minimum transfer amount (MTA). A threshold is the unsecured credit exposure that a party is willing to bear. A MTA is used to avoid the workload associated with a frequent transfer of insignificant collateral amounts. An independent amount plays the same role as an initial margin or haircut. We define the effective collateral threshold as the threshold plus the MTA.

Collateral is called as soon as the mark-to-market (MTM) value rises above the effective threshold.

There are three types of collateralization: partial, over or full. A positive effective threshold corresponds to partial-collateralization where the posting of collateral is less than the MTM value. A negative effective threshold represents over-collateralization where the posting of collateral is greater than the MTM value. A zero-value effective threshold equates with full-collateralization where the posting of collateral is equal to the MTM value. Our generic model is applicable to all the types.

Since the only reason for taking collateral is to reduce/eliminate credit risk, collateral analysis should be closely related to credit risk modeling. There are two primary types of models that attempt to describe default processes in the literature: structural models and reduced-form models. Many practitioners in the market have tended to gravitate toward the reduced-from models given their mathematical tractability and market consistency.

We consider a filtered probability space (  , F ,   0  t t F , P ) satisfying the usual conditions, where  denotes a sample space, F denotes a  -algebra, P denotes a probability measure, and

  0  t t F
denotes a filtration. In the reduced-form framework, the stopping or default time  of a firm is modeled as a Cox arrival process whose first jump occurs at default and is defined by,

       t s ds s h t 0 ) , ( : inf  (1)
where ) (t h or ) , ( t t h  denotes the stochastic hazard rate dependent on an exogenous common state t  , and  is a unit exponential random variable independent of t  .

It is well-known that the survival probability from time t to s in this framework is defined by

            s t du u h t s P s t p ) ( exp ) | ( : ) , (   (2a)
The default probability for the period (t, s) is given by

               s t du u h s t p t s P s t q ) ( exp 1 ) , ( 1 ) | ( : ) , (   (2b)
Let valuation date be t. Consider a financial contract that promises to pay a 0  T X at maturity date t T  , and nothing before the time.

The binomial default rule considers only two possible states: default or survival. For a discrete one-payment period (t, T ) economy, at time T the contract either defaults with the default probability ) , ( T t q or survives with the survival probability ) , ( T t p

. The survival payoff is equal to T X and the default payoff is a fraction of T X :

T X  , where  is the recovery rate. The value of this defaultable contract at time t is the discounted expectation of all the possible payoffs and is given by

      t t F F T T N X T t I T t D E X T t q T T t p T t D E t V ) , ( ) , ( ) , ( ) ( ) , ( ) , ( ) (     (3) where   t E F  is the expectation conditional on t F , ) , ( T t D
denotes the risk-free discount factor at time t for maturity T and

  ) , ( ) ( ) , ( ) , ( T t q T T t p T t I   
can be regarded as a risk-adjusted discount ratio.

Suppose that there is a CSA agreement between a bank and a counterparty in which the counterparty is required to deliver collateral when the mark-to-market (MTM) value arises over the effective threshold H.

The choice of modeling assumptions for collateralization should be based on the legal structure of CSA. According to the Bankruptcy Law, if the demand for default payment exceeds the collateral value, the balance of the demand will be treated as an unsecured claim and subject to its pro rata distribution under the Bankruptcy Code's priority scheme (see [START_REF] Garlson | Secured creditors and the eely character of bankruptcy valuations[END_REF], [START_REF] Routh | Default interest payable to oversecured creditor subject to reasonableness limitation[END_REF], and [START_REF] Edwards | Derivatives and the bankruptcy code: why the special treatment?[END_REF]). The default payment under a CSA can be mathematically expressed as

  )) ( 1 )( ( ) ( ) ( ) ( ) ( ) ( T T C X T T C X T T C T P T T D          (4) where ) (T C is the collateral amount at T.
It is worth noting that the default payment in equation ( 4) is always greater than the original recovery, i.e.,

T D X T T P ) ( ) (   because ) (T



is always less than 1. Said differently, the default payoff of a collateralized contract is always greater than the default payoff of the same contract without a CSA.

That is why the major benefit of collateralization should be viewed as an improved recovery in the event of a default.

According to CSA, if the contract value

) (t V C
is less than the effective threshold ) (t H , no collateral is posted; otherwise, the required collateral is equal to the difference between the contract value and the effective threshold. The collateral amount posted at time t can be expressed mathematically as For a discrete one-payment period (t, T) economy, at time T, if the contract survives, the survival value is the promised payoff T X and the collateral taker returns the collateral to the provider. If the contract defaults, the default payment is defined in (4) where the future value of the collateral is

) 0 ), ( ) ( max( ) ( t H t V t C C   (
) , ( / ) ( ) ( T t D t C T C  .
Since the most predominant form of collateral is cash according to ISDA [2013], it is reasonable to consider the time value of money only for collateral assets. The large use of cash means that collateral is both liquid and not subject to large fluctuations in value. The above collateral rule tells us that collateral does not have any bearing on survival payoffs; instead, it takes effect on default payments only. The value of the CSA contract is the discounted expectation of all the payoffs and is given by

      t F T T C X T t p T C X T T C T t q T t D E t V ) , ( )) ( )( ( ) ( ) , ( ) , ( ) (      (6)
After some simple mathematics, we have the following proposition Proposition 1: The value of a collateralized single-payment contract is given by

  ) , ( ) , ( ) ( T t G X T t F E t V T C   t F (7a) where   ) , ( ) , ( ) , ( / 1 1 ) , ( ) ( ) ( ) ( ) ( T t D T t I T t I T t F t H t V t H t V N N     (7b)   ) , ( / ) ( 1 ) , ( ) ( 1 ) , ( ) ( ) ( T t I T T t q t H T t G t H t V N     (7c) where   t F ) , ( ) , ( T t I E T t I  . ) ,
) ( ) ( t V t V F C  where   t F T F X T t D E t V ) , ( ) ( 
is the risk-free value. That is to say: the value of a fully-collateralized contract is equal to the risk-free value. This conclusion is in line with the results of [START_REF] Johannes | The impact of collateralization on swap rates[END_REF], [START_REF] Fuijii | Collateralized credit default swaps and default dependence: Implications for the central counterparties[END_REF], and [START_REF] Piterbarg | Funding beyond discounting: collateral agreements and derivatives pricing[END_REF].

Proposition 1 can be easily extended from single payment to multiple payments. Suppose that a defaultable contract has m cash flows represented as i X with payment dates i T , where i = 1,…,m. We derive the following proposition:

Proposition 2: The value of a collateralized multiple-payment contract is given by

                        1 0 1 1 0 1 1 1 0 1 ) , ( ) , ( ) , ( ) ( m i i i i j j j m i i i j j j C T T G T T F E X T T F E t V t t F F ( 8a
)
2 Moody's Investor's Service [2000] presents statistics that suggest that the correlations between interest rates, default probabilities and recovery rates are very small and provides a reasonable comfort level for the uncorrelated assumption.

where

  ) , ( ) , ( ) , ( / 1 1 ) , ( 1 1 1 ) ( ) , ( ) ( ) , ( 1 1 1           j j j j j j T H T T J T H T T J j j T T D T T I T T I T T F j j j j j j (8b)   ) , ( / ) ( 1 ) , ( ) ( 1 ) , ( 1 1 1 ) ( ) , ( 1 1         j j j j j j T H T T J j j T T I T T T q T H T T G j j j  (8c)                j T F 1 1 1 1 1 ) ( ) , ( ) , ( ) , ( j j C j j j j j j X T V T T I T T D E T T J (8d) where      1 0 1 1 ) , (
m m T T J  , ) , ( 1 m m T T F  and ) , ( 1 m m T T G 
are revealed. This type of problem can be best solved by working backward in time, with the later value feeding into the earlier ones, so that the process builds on itself in a recursive fashion, which is referred to as backward induction. The most popular backward induction algorithms are lattice/tree and regression-based Monte Carlo, i.e., Longstaff-Schwartz approach.

Empirical Results

Impact of collateralization on swap rate

In this subsection, we choose interest rate swaps for our empirical study. Ultimately, it is the objective of this subsection to test if counterparty credit risk and collateralization are sufficient to explain market swap premium spreads. We choose a statistical measurement 2 R to determine how much market spreads can be interpreted by model-implied spreads that take counterparty risk and collateralization into account.

Swap rate is the fixed rate that sets the market value of a swap at initiation to zero. ISDAFIX provides average mid-market swap rates based on a mid-day polling from a panel of dealers. In practice, the mid-market swap rates are generally not the actual swap rates transacted with counterparties, but are instead the benchmarks against which the actual swap rates are set. A swap dealer that arranges a contract and provides liquidity to the market involves costs. Therefore, it is necessary to adjust the mid-market swap rate to cover various transacting expenses and also to provide a profit margin to the dealer. As a result, the actual price agreed for a transaction is not zero but a positive amount to the dealer.

Unlike the generic benchmark swap rates, swap premia are determined according to the basic principles of supply and demand. The swap market is highly competitive. In a competitive market, prices are determined by the impersonal forces of demand and supply, but not by the manipulations of powerful buyers or sellers.

Prior research has primarily focused on the generic mid-market swap rates and results appear puzzling. [START_REF] Sorensen | Pricing swap default risk[END_REF] believe that swap spreads are partially determined by counterparty default risk. Whereas [START_REF] Huang | Swap rates and credit quality[END_REF], [START_REF] Minton | An Empirical Examination of Basic Valuation Models for Plain Vanilla U.S. Interest Rate Swaps[END_REF] and [START_REF] Grinblatt | An analytic solution for interest rate swap spreads[END_REF] find weak or no evidence of the impact of counterparty credit risk on swap spreads. Collin-Dufresne and Solnik [2001] and [START_REF] He | Modeling Term Structures of Swap Spreads[END_REF] further argue that many credit enhancement devices, e.g., collateralization, have essentially rendered swap contracts risk-free. Meanwhile, [START_REF] Duffie | Modeling term structure of defaultable bonds[END_REF], and [START_REF] Liu | The Market Price of Risk in Interest Rate Swaps: The Roles of Default and Liquidity Risks[END_REF] conclude that both credit and liquidity risks have an impact on swap spreads. Moreover, [START_REF] Feldhutter | Decomposing swap spreads[END_REF] find that the liquidity factor is the largest component of swap spreads. It seems that there is no clear-cut answer yet regarding the relative contribution of various factors.

In contrast to previous research, this subsection mainly studies swap adjustments/premia related to credit risk and collateralization. It empirically measures the effect of collateralization on pricing and compares it with model-implied prices.

A swap premium is supposed to cover the expected profit and all the expenses, including the cost of bearing unsecured credit risk. Unfortunately, however, we do not know what percentage of the market swap premium is allocated to the unsecured credit risk, which makes a direct verification impossible.

To circumvent this difficulty, we design an indirect verification process in which we select some CSA swap pairs such that the two contracts in each pair have exactly the same terms and conditions but are traded with different counterparties under different collateral agreements. It is reasonable to believe that the difference between the two contracts in each pair is solely attributed to collateralized counterparty credit risk, as all the other risks/costs are identical. Therefore, by accounting for credit risk and collateralization, we can efficiently compare the implied spreads with the market spreads for these pairs.

We obtain a unique proprietary dataset from an investment bank. The dataset contains derivative contract data, counterparty data (including collateral agreements, recovery rates, etc), and market data.

The trading dates are from May 6, 2005 to May 11, 2012. We find a total of 1002 swap pairs in the dataset, where the two contracts in each pair have the same terms and conditions but are traded with different CSA counterparties. We arbitrarily select one pair shown in Exhibit 1.

Exhibit 1: A pair of 20-year swap contracts

This exhibit displays the terms and conditions of two swap contracts that have different counterparties but are otherwise the same. We hide the counterparty names according to the security policy of the investment bank while everything else is authentic. As the payoffs of an interest rate swap are determined by interest rates, we need to model the evolution of floating rates. Interest rate models are based on evolving either short rates, instantaneous forward rates, or market forward rates. Since both short rates and instantaneous forward rates are not directly observable in the market, the models based on these rates have difficulties in expressing market views and quotes, and lack agreement with market valuation formulas for basic derivatives. On the other hand, the object modeled under the Libor Market Model (LMM) is market-observable. It is also consistent with the market standard approach for pricing caps/floors using Black's formula. They are generally considered to have more desirable theoretical calibration properties than short rate or instantaneous forward rate models. Therefore, we choose the LMM lattice proposed by [START_REF] Xiao | An efficient lattice algorithm for the LIBOR market model[END_REF] for pricing collateralized swaps.

According to Proposition 2, we also need counterparty-related information, such as recovery rates, hazard rates and collateral thresholds. The CDS premia and recovery rates are given in Exhibit 3 and the collateral thresholds and MTAs of the CSA agreements are displayed in Exhibit 4. We can compute the hazard rates via a standard calibration process (see J.P. [START_REF] Morgan | Par credit default swap spread approximation from default probabilities[END_REF]).

Exhibit 3: CDS premia and recovery rates

This exhibit displays the closing CDS premia as of September 15, 2005 and recovery rates Given the above information, we are able to compute the collateralized swap rates. We first use the LMM to evolve the interest rates and then determine the associated CSA-adjusted discount factors as well as the cost of bearing unsecured credit risk according to Proposition 2. Finally, we calculate the collateralized swap rates via a backward induction method. The results are given in Exhibit 5.

Exhibit 5: Swap rate results

This exhibit presents the model-implied swap rates and premia as well as the dealer-quoted market swap rates and premia, where Swap premium (in bps) = Swap rate -Generic swap rate, and Premium spread = Premium of swap 2 -Premium of swap 1. By accounting for both credit risk and collateralization, we calculate the model-implied swap rates as 0.048780 and 0.048790 shown in Exhibit 5. Consequently, the model-implied swap premia are 0.09 bps and 0.19 bps. The results imply that only a small portion of a swap premium is attributed to unsecured credit risk. Intuitively the small impact of credit risk and collateral posting on a swap premium is mainly due to 1) only the swap coupons rather than the national amount are exposed to counterparty risk; 2) the initial swap rate sets the contract value close to zero and there is only 50% chance to develop counterpart risk; 3) collateralization mitigates credit risk. This would certainly not be the case for other derivatives. The result is in line with the findings of [START_REF] Huang | Swap rates and credit quality[END_REF], [START_REF] Duffie | Modeling term structure of defaultable bonds[END_REF], and [START_REF] Minton | An Empirical Examination of Basic Valuation Models for Plain Vanilla U.S. Interest Rate Swaps[END_REF].

Exhibit 5 shows that the model-implied spread is quite close to the dealer-quoted spread, suggesting that the model is fairly accurate in pricing collateralized financial instruments.

Repeating this exercise for the remaining pairs, we find that the model-implied spreads fluctuate randomly around the market spreads. We refer to the differences between the model-implied premium Next, we examine the effects of credit risk and collateralization, alone or combined, on swap premium spreads. First, we study the marginal effect of credit risk. For each swap pair, we obtain the counterparty CDS premia. Presumably, the differences in CDS premia should mainly represent the differences in counterparty risk. To determine the strength of the statistical relationship between market premium spreads and counterparty risk, we present the estimate of the following regression model.

    bX a Y (9)
where Y is the market swap premium spread, X is the difference between the counterparty CDS premia, a is the intercept, b is the slope, and  is the regression residual.

The results of this regression are shown in Exhibit 7. It can be seen that the adjusted 2 R is 0.7472, implying that approximately 74% of market premium spreads can be explained by credit risk alone. We provide empirical evidence that counterparty credit risk alone plays a significant but not overwhelming role in determining credit-related spreads when contracts are under collateral agreements. Moreover, the slope is 0.0127, suggesting that a CDS spread of about 100 bps translates into a swap spread of about 1.27 bps. Finally the small p-value indicates that the changes in CDS premia are closely related to the changes in market premium spreads.

Exhibit 7: Marginal credit risk regression results

This exhibit presents the regression results for the following regression model:

MarketSwapPremiumSpreads = a + b * DifferencesBetweenCounterpartyCDSs + ε
where the market swap premium spreads are used as the dependent variable and the differences between the counterparty CDS premia as the explanatory variable.

Slope

Exhibit 8: Credit risk and collateralization combined regression results

This exhibit presents the regression results for the following regression model:

MarketSwapPremiumSpreads = a + b * ImpliedSwapPremiumSpreads + ε
where the market swap premium spreads are used as the dependent variable and the model-implied swap premium spreads as the explanatory variable. Exhibit 8 shows that the adjusted 2 R value is 0.9906, implying that approximately 99% of the market spreads can be explained by the implied spreads. Also the small p-value suggests that the changes in implied spreads are strongly related to the changes in market spreads.

The empirical results shed light on the economic and statistical significance of collateralization.

The increase in the explanatory power of swap premium spreads bears an interesting finding: It seems that credit risk alone has a modest explanatory power on premium spreads. Only the combination of credit risk and collateralization can sufficiently explain them.

Impact of collateralization on credit risk

In this subsection, we study how collateralization affects credit risk by measuring CVA changes due to collateral posting. CVA is the market price of counterparty credit risk that has become a central part of counterparty credit risk management.

From the same dataset above, we find that there are a total of 3052 counterparties having live trades as of May 11, 2012. 516 increase in collateralization causes a decrease in CVA charge and vice-versa. These findings improve our understanding of the relationship between collateralization and CVA.

Impact of collateralization on market risk

We study how collateralization impacts market risk by gauging VaR changes due to collateral arrangements. VaR is the regulatory measurement for assessing market risk. It is defined as the maximum loss likely to be suffered on a portfolio for a given probability defined as a confidence level over a given period time. In its most popular form, VaR measures 10-day 99 th percentile of potential loss that can be incurred.

There For monitoring market risk, many organizations segment portfolios in some manner. They may do so by traders and trading desks. Typically, a market risk portfolio contains derivatives across multiple counterparties, while a counterparty portfolio comprises transactions among different traders and trading desks. We arbitrarily select a trading portfolio and then partition it into single-counterparty sub-portfolios.

One sub-portfolio contains 172 interest rate swaps, 68 caps and floors, 25 European swaptions and 17 cancelable swaps.

First, we compute the VaR of the sub-portfolio without considering credit risk. The calculated result as of May 11, 2012 is -386,570. Here the VaR is a negative value by definition. However, the industry convention is to report VaR as a positive number that is the amount of money one can lose. Thus, people in the market usually say that the VaR is 386,570 in this case. This convention can be confusing in places. If one says that VaR increases, the numbers actually become smaller or move into the left tail.

For many reasons, both historical and practical, market and credit risk have often been treated as if they are unrelated source of risk: the risk types have been measured separately, managed separately, and economic capital against each risk type has been assessed separately.

However, market risk and credit risk actually reinforce each other. Default-induced credit losses can be driven by market price changes. At the same time, the changes in prices depend on the rating migration or increase in the default perception of the firm. The Basel Committee on Banking Supervision (see [START_REF] Bcbs | Findings on the interaction of market and credit risk[END_REF]) also finds that those banks that were more severely affected in the global financial crisis measured their market and credit risk separately, whereas banks that used an integrated approach to market and credit risk measurement were much less impacted. Measuring market risk without considering credit risk may mask the significant impact of credit risk and often leads to underestimation of risk. -386,570 -398,235 -404,401 -410,756 -418,950 Exhibit 10 tells us that collateral posting actually can reduce VaR. The results show that market risk exposure rises as collateral threshold increases. In particular, VaR reaches the maximum when the threshold is infinite representing no collateral arrangement. We come to the same conclusion after repeating this test for other portfolios.

VaR

Our findings suggest that there are important interactions between market and credit risk. We find a positive correlation between market and credit risk as they increase or decrease together. We also find that collateralization is actually negatively correlated with market risk, i.e., an increase in collateralization causes a drop in market risk. Said differently, collateral posting can reduce market risk. Our research contributes to the understanding of the interaction between market and credit risk.

Conclusion

This article addresses an important topic of the impact of collateralization on valuation and risk.

We present a new model for pricing collateralized financial contracts based on the fundamental principal and legal structure of CSA. The model can back out market prices. This is very useful for pricing outstanding collateralized derivatives.

Empirically, we use a unique proprietary dataset to measure the effect of collateralization on pricing and compare it with model-implied prices. The empirical results show that the model-implied prices are quite close to the market-quoted prices, suggesting that the model is fairly accurate on pricing collateralized derivatives.

We find strong evidence that counterparty credit risk alone plays a significant but not overwhelming role in determining credit-related spreads. Only the joint effect of collateralization and credit risk has high explanatory power on unsecured credit costs. This finding suggests that failure to properly account for collateralization may result in significant mispricing of derivatives.

    ) , ( ) ( ) , ( ) ( 1 0 1 1 1 0 T T G T V X T T F E t V C C    t F (
                                    1 0 1 1 0 1 2 1 0 1 2 1 1 0 1 1 0 1 1 1 0 ) , ( ) , ( ) ( ) , ( ) , ( ) , ( ) ( ) , ( ) ( i i i i j j j C j j j i i i j j j C C T T G T T F E T V T T F E X T T F E T T G T V X T T F E t V t t t t F F F F (A8)
By recursively deriving from 2 T forward over m T , where

m m C X T V  ) (
, we obtain

                        1 0 1 1 0 1 1 1 0 1 ) , ( ) , ( ) , ( ) ( m i i i i j j j m i i i j j j C T T G T T F E X T T F E t V

.

  Empty product allows for a much shorter mathematical presentation of many subjects. The valuation in Proposition 2 has a backward nature. The intermediate values are vital to determine the final price. For a payment period, the current price has a dependence on the future price. Only on the final payment date m T , the value of the contract and the maximum amount of information needed to determine ) , ( 1

  spreads and the market quoted premium spreads as the model-market premium spread differentials. The summary statistics of the market spreads, the model-implied spreads, and the model-market spread differentials are presented in Exhibit 6. It shows that the average of the model-market spread differentials is only -0.03 bps, which can be partly attributed to noise. The results indicate prima facie that the model performs quite well. The empirical tests corroborate the theoretical prediction on premium spreads. Exhibit 6: Summary statistics of model-implied swap premium spreads, market swap premium spreads and model-market swap premium spread differentials All values are displayed in bps. Model-market swap premium spread differential = Model-implied swap premium spread -Market-quoted swap premium spread.

  Margin Survey[START_REF] Isda | ISDA margin survey 2013[END_REF], 73.7% of OTC derivatives are subject to collateral agreements. For large firms, the figure is 80.7%. Accounting for collateralization has become increasingly important in pricing OTC derivatives. Since the implied spreads generated by our model take into account both credit risk and collateralization, the statistical relationship between the market spreads and the model-implied spreads should refer to the joint effect of counterparty credit risk and collateralization on market spreads. Thus, we present another regression model where the market spreads are regressed on the implied spreads. The regression results are shown in Exhibit 8.

  are three commonly used methodologies to calculate VaR -parametric, historical simulation and Monte Carlo simulation. Parametric model estimates VaR directly from the standard deviation of portfolio returns typically assuming returns are normally distributed. Historical simulation calculates VaR from the distribution of actual historical returns. Whilst Monte Carlo simulation computes VaR from a distribution constructed from random outcomes. In this paper, we calculate historical VaR.

F

  -measurable. According to the taking out what is known and tower properties of conditional expectation, we have

  Proposition 1 tells us that the value of a collateralized contract is equal to the present value of the payoff discounted by the CSA-adjusted discount factor minus the cost of taking unsecured counterparty credit risk. This proposition theoretically demonstrates that collateral posting

					I	( T t		and	V N	(t	)	are defined in (3).
	Proof: See the Appendix.
	We may think of	F	( t	,	T	)	as the CSA-adjusted discount factor and	G	( t	,	T	)	as the cost of bearing
	unsecured credit risk. changes valuation.
	The pricing in Proposition 1 is relatively straightforward. We first compute	V N	(t	)	and then test
	whether its value is greater than	H	(t	)	. After that, the calculations of	F	( t	,	T	)	,	G	( t	,	T	)	and	V C	(t	)	are
	easily obtained.
	We discuss a special case where	) (  t	0

H corresponding to full-collateralization. Suppose that default probabilities are uncorrelated with interest rates and payoffs 2 . From Proposition 1, we can easily obtain

Swap 1 Swap 2 Fixed leg Floating leg Fixed leg Floating leg

	Currency	USD	USD	USD 4.4213%	USD
	Pay/receive	Bank receives 6 year swap rate Party X receives	Bank receives 4.4679%	Party Y receives
	Floating index	-7 year swap rate 3 month LIBOR	-4.5120%	3 month LIBOR
	Floating spread	-8 year swap rate	0	-4.5561%	0
	Floating reset	-9 year swap rate Quarterly	-4.5952%	Quarterly
		10 year swap rate		4.6368%
		12 year swap rate		4.7089%
	An interest rate curve is the term structure of interest rates, derived from observed market 15 year swap rate 4.7957%
	instruments that represent the most liquid and dominant interest rate products for certain time horizons. 20 year swap rate 4.8771%
		25 year swap rate		4.9135%
		Instrument Name		Price
		September 21 2005 LIBOR	3.6067%
		September 2005 Eurodollar 3 month	96.1050
	Counterparty	X December 2005 Eurodollar 3 month	95.9100	Y
	Effective date	15/09/2005 March 2006 Eurodollar 3 month 15/09/2005	15/09/2005 95.8100	15/09/2005
	Maturity date	15/09/2025 June 2006 Eurodollar 3 month 15/09/2025	15/09/2025 95.7500	15/09/2025
	Day count	30/360 September 2006 Eurodollar 3 month ACT/360	30/360 95.7150	ACT/360
	Payment frequency	Semi-annually December 2006 Eurodollar 3 month Quarterly	Semi-annually 95.6800	Quarterly
	Swap rate	4.9042% 2 year swap rate	-	4.9053% 4.2778%	-
	Roll over	Mod_follow 3 year swap rate Mod_follow	Mod_follow 4.3327%	Mod_follow
	Principal	25,000,000 4 year swap rate 25,000,000	25,000,000 4.3770%	25,000,000

Normally the curve is divided into three parts. The short end of the term structure is determined using LIBOR rates. The middle part of the curve is constructed using Eurodollar futures. The far end is derived using mid swap rates. The LIBOR-future-swap curve is presented in Exhibit 2. After bootstrapping the curve, we get the continuously compounded zero rates.

Exhibit 2: USD LIBOR-future-swap curve

This exhibit displays the closing mid prices as of

September 15, 2005

  This exhibit provides the collateral thresholds and MTAs under the CSA agreements.

	Counterparty name	Bank	Company X	Company Y
	6 month CDS spread	0.00031	0.000489	0.000808
	1 year CDS spread	0.000333	0.00056	0.001017
	2 year CDS spread	0.000516	0.000866	0.00154
	3 year CDS spread	0.000664	0.001147	0.002114
	4 year CDS spread	0.000848	0.00147	0.002768
	5 year CDS spread	0.001012	0.001783	0.003439
	7 year CDS spread	0.001334	0.002289	0.004283
	10 year CDS spread	0.001727	0.002952	0.005281
	15 year CDS spread	0.001907	0.003283	0.005814
	20 year CDS spread	0.002023	0.003266	0.006064
	30 year CDS spread	0.002021	0.00336	0.006461
	Recovery rate	0.39213	0.35847	0.33872
		Exhibit 4: CSA agreement
	CSA agreement	1		2
	Counterparty name	Bank	Company X	Bank	Company Y
	Threshold	0	0	0	0
	MTA	500000	500000	500000	500000

  of them have CSA agreements. We randomly select one counterparty portfolio that contains 476 interest rate swaps, 36 interest rate swaptions and 223 interest rate caps/floors.

Impact of Collateralization on VaR

  Therefore, we further calculate VaR by taking credit risk into account. Let us first assume that there is no CSA agreement. Each trade is valued by the risky model developed by[START_REF] Xiao | An accurate solution for credit value adjustment (CVA) and wrong way risk[END_REF]. The VaR with credit risk is computed as -418,948. It can be seen that VaR has increased from 386,570 to 418,948 after accounting for credit risk. The above empirical results show that market fluctuation has a larger impact on VaR when credit risk is taken into account. Our research highlights the linkage between market and credit risk.Next, we measure VaR again by considering both counterparty credit risk and collateralization.

	Assume that there is a CSA arrangement. The VaR values under different effective collateral thresholds
	are displayed in Exhibit 10.
	This exhibit shows that VaR increases with collateral threshold. The infinite collateral threshold is
	equivalent to no collateral agreement and the zero-value collateral threshold corresponds to full
	collateralization.
	Effective Threshold	0	2.1 Million	4.1 Million	6.1 Mil	Infinite (  )

Exhibit 10.

  denote the CSA value of the contract excluding the current cash flow 1 X . According to Proposition 1, the CSA value of the contract at t is given by

	V	C	( t	)		1 V	N	(	t	)		H	(	t	)	V	N	( t	)		1 V	N	(	t	)		H	(	t	)	 V	N	( t	)		/	I	( t	,	T	)		H	( t	)	q	( t	,	T	 1 )			( T	)		/	I	( t	,	T	)		(A4)
	or
																								V		C	( t	)				E	 F	( t	,	T	)	X	T	t F			G	( t	,	T	)	(A5a)
	where
													F	( t	,	T	)			 1 V	N	(	t	)		H	(	t	)				1 V	N		(	t	)		H	(	t	)	/	I	( t	,	T	)	 I	( t	,	T	)	( t D	,	T	)	(A5b)
																	G	( t	,	T	)			1 V N	(	t	)		H	(	t	)	H	( t	)	q	( t	,	T	 1 )			( T	)		/	I	( t	,	T	)	(A5c)
	Proof of Proposition 2: Let		0 T t  . On the first payment day 1 T , let	V C	( 1 T	)

We also find evidence that there is a strong linkage between market and credit risk. Our research results suggest that banks and regulators need to think about an integrated framework to capture material interactions of these two types of risk. This requires all profits and losses are gauged in a consistent way across risk types as they tend to be driven by the same economic factors. Our finding leads to an improved understanding of the interaction between market and credit risk and how this interaction is related to risk measurement and management.

First, we compute the risk-free value 702 , 737 , 2  F V that is relatively straightforward as the risk-free portfolio value is what trading systems or pricing models normally report.

Second, we assume that there is counterparty credit risk but no collateral agreement. Based on the pricing model proposed by [START_REF] Xiao | An accurate solution for credit value adjustment (CVA) and wrong way risk[END_REF], we compute the risky value of the portfolio as

Exhibit 9. Impact of Collateralization on CVA

This exhibit shows that CVA increases with collateral threshold. The infinite collateral threshold is equivalent no collateral agreement and the zero-value collateral threshold corresponds to full collateralization. An increase in collateral threshold leads to a decrease in collateralization.

. The value of this collateralized contract is the discounted expectation of all the payoffs and is given by

The collateral posted at time t is defined in (5). The value of the collateral at time T becomes

, where we consider the time value of money only for collateral assets.


Student Member, IEEE Mattia Mattioni
email: mattia.mattioni@uniroma1.it.

Fellow, IEEE Salvatore Monaco
email: salvatore.monaco@uniroma1.it.

IEEE Normand-Cyrot Fellow

D Normand-Cyrot

Reduction of discrete-time two-channel delayed systems

Keywords: Delay systems, Sampled-data control, Stability of nonlinear systems I

In this paper, the reduction method is extended to time-delay systems affected by two mismatched input delays. To this end, the intrinsic feedback structure of the retarded dynamics is exploited to deduce a reduced dynamics which is free of delays. Moreover, among other possibilities, an Immersion and Invariance feedback over the reduced dynamics is designed for achieving stabilization of the original dynamics. A chained sampled-data dynamics is used to show the effectiveness of the proposed control strategy through simulations.

{mattioni,cyrot}@l2s.centralesupelec.fr one that is equivalent (from the point of view of stability) to the original one [START_REF]Sampled-data reduction of nonlinear input-delayed dynamics[END_REF]. Since reduction implicitly relies upon prediction, stabilization of the reduced dynamics implies stabilization of the delayed one. However, an interesting feature of reduction stands in the simplification of the design because the reduced dynamics is by construction free of delays. Moreover, contrarily to prediction dynamics, the reduced model is not a delay-free copy of the system dynamics but differs in the controlled vector fields that come to be explicitly parametrized by the delay-length so leaving space for a further redesign.

Up to now, the discussion has been referring to single-input dynamics though extensions to the case of multiple inputs is straightforward whenever the input channels are uniformly delayed (i.e., affected by the same delay) as developed in [START_REF]Nonlinear discrete-time systems with delayed control: A reduction[END_REF]. In continuous time, predictor-based techniques for multi-input linear time-invariant systems affected by distinct input delays have been proposed in [START_REF] Tsubakino | Exact predictor feedbacks for multi-input LTI systems with distinct input delays[END_REF]- [START_REF] Watanabe | An observer for linear feedback control laws of multivariable systems with multiple delays in controls and outputs[END_REF] with extensions to nonlinear dynamics in [START_REF] Bekiaris-Liberis | Predictor-feedback stabilization of multi-input nonlinear systems[END_REF].

The aim of this paper is to address this problem in the nonlinear context when considering dynamics affected by two distinct input delays. The contribution relies upon the possibility of extending the reduction method [START_REF]Nonlinear discrete-time systems with delayed control: A reduction[END_REF] to this class of dynamics by taking advantage of the feedback structure underlying the evolutions of the retarded system. First, a state augmentation is used to make the delayed dynamics uniform in the action of the delays (i.e., the extended system is affected by the same delay); then, a modified reduction variable is exhibited so to transform the input-delayed dynamics into a delay-free one over the extended state-space. Finally, among other possibilities, an I&I design procedure is worked out for stabilizing the reduced dynamics. The cascade structure allows to conclude that stabilization of the reduced dynamics implies stabilization of the input-delayed one.

The paper is organized as follows. In Section II, recalls on the discrete-time reduction method are provided when the inputs are affected by the same delay. The case of two-channel time delays systems is studied in Section III by exhibiting a reduced dynamics which is free of delays. An I&I-based design procedure over the reduced model is then presented in Section IV. In Section V, the case of a chained dynamics is considered as a case of study while Section VI concludes the paper.

Notations: 0 i× j denotes the i × j-dimensional matrix whose entries are zero, I N stands for the N dimensional identity matrix while 1 j the column vector whose entries are all ones. Maps and vector fields are assumed smooth. Given i, j ∈ N such that j < i, u [k-i,k-j[ denotes the history of the discrete variable u over the window [ki, kj[ (i.e., u [k-i,k-j[ = {u(ki), . . . , u(kj -1)}). The symbol "•" denotes the composition of functions. I and Id denote respectively the identity matrix and the identity operator. Given a vector field f , L f denotes the Lie derivative operator,

L f = ∑ n i=1 f i (•)∇ x i with ∇ x i := ∂ ∂ x i while ∇ = (∇ x 1 , . . . , ∇ x n
). e L f Id denotes the associated Lie series operator, e L f := Id + ∑ i≥1

L i f i!

II. RECALLS ON DISCRETE-TIME REDUCTION

Consider the nonlinear discrete-time system

x(k + 1) =F(x(k), u(k -N)) (1)
with x ∈ R n , u ∈ R p , possessing an equilibrium at the origin and affected by a discrete delay N ≥ 0 uniformly acting over each input channel. Invertibility of the function F 0 (•) = F(•, 0) with respect to the state vector x is assumed.

In [START_REF]Nonlinear discrete-time systems with delayed control: A reduction[END_REF], it was proven that the problem of finding a stabilizer for (1) can be settled over a new dynamics that is equivalent to the original one as far as stability properties are concerned. For, we introduce the so-called reduction variable

η(k) := F -N 0 (•) • F N (x(k), u [k-N,k[ ) (2)
where u [k-N,k[ denotes the history of the control signal and

F N 0 (x) = F 0 (•) • • • • • F 0 (x) N times , F -N 0 (x) = F -1 0 (•) • • • • • F -1 0 (x)
N times represent the usual N-times composition of the drift term and the corresponding inverse. Composing N steps ahead the full dynamics (1), one computes for N ≥ 1

F N (x(k), u [k-N,k[ ) :=F N-1 (•, u [k-N+1,k[ ) • F(x(k), u(k -N)) :=F(•, u(k -1)) • • • • • F(x(k), u(k -N)) with F 1 (x(k), u [k-1,k[ ) := F(x(k), u(k -1)).
It is a matter of computations to verify that (2) evolves according to the reduced dynamics

η(k + 1) =F r (η(k), u(k)) (3)
with 3) is delay free with the same drift as (1) but modified controlled vector field. More precisely, when assuming p = 1 for the sake of simplicity, (3) rewrites as the N-depending dynamics

F r (η, u) := F -N 0 (•) • F(•, u) • F N 0 (η). The reduced dynamics (
η(k + 1) =F 0 (η(k)) (4)
+ u(k) 0 ∇ u F -N 0 (•) • F(•, u) • F N 0 (η(k)))du.
Hence, the problem stands in finding a feedback u(k) = α(η(k)) stabilizing the equilibrium of (3) so getting in turn stabilization of (1) in closed loop as, by construction,

x(k + N) = F N 0 (η(k)).
In fact, one gets in closed loop the cascade

x(k + 1) =F N 0 (η 1 (k)) η 1 (k + 1) =η 2 (k), . . . , η N-1 (k + 1) = η(k) η(k + 1) =F r (η(k), α(η(k))) with η 1 (k) = F(x(k), α(F -N 0 (x(k)))).
Several strategies aimed at computing the reduction-based feedback have been discussed in [START_REF]Nonlinear discrete-time systems with delayed control: A reduction[END_REF] by exploiting the properties of the time-delay system (1) in free evolution.

III. TWO-CHANNEL TIME-DELAY SYSTEMS

In the sequel we address the problem of stabilizing the timedelay system

x(k + 1) =F(x(k), u 1 (k -N 1 ), u 2 (k -N 2 )) (5)
whose input channels u i ∈ R p i , i = 1, 2 with p = p 1 + p 2 , are affected by different time delays verifying, after possible index sorting,

N 2 -N 1 = N > 0; F 0 (•) := F(•, 0, 0) is assumed to be invertible over R n .
The design we propose is based on three steps: first, we introduce a dynamical extension over the control u 2 so to compensate the mismatch among the two input delays; then, we extend the reduction method as recalled in Section II over the extended dynamics; finally, we design one possible reduction-based feedback based on Immersion and Invariance.

Remark 3.1: The presented results apply to sampled-data systems affected by entire delays; namely, one considers continuous-time dynamics of the form

ẋ(t) = f (x(t)) + g 1 (x(t))u 1 (t -τ 1 ) + g 2 (x(t))u 2 (t -τ 2 )
with u i (t) = u i (kδ ) = u i (k) for t ∈ [kδ , (k + 1)δ [ and τ i = N i δ for some N i ∈ N (i = 1, 2). In that case, for x(k) = x(kδ ), the discrete-time equivalent model gets the δ -dependent form

x(k + 1) =F δ (x(k), u 1 (k -N 1 ), u 2 (k -N 2 )) = e δ (L f +L g 1 u 1 (k-N 1 ) +L g 2 u 2 (k-N 2 ) ) x x(k) .

A. The dynamical extension

Let us introduce the new state ξ := (ξ 1 , . . . , ξ N ) ∈ R p 2 N (with N = N 2 -N 1 being the mismatch between the two delays) evolving as the linear dynamics

ξ (k + 1) =Aξ (k) + Bu 2 (k) with ξ i (k) = u 2 (k -N + i -1) for i = 1, . . . , N and A = 0 p 2 (N-1)×p 2 I p 2 (N-1) 0 p 2 ×p 2 0 p 2 (N-1)×p 2 , B = 0 p 2 (N-1)×p 2 I p 2 .
Accordingly, the extended delayed system exhibits a cascade structure affected by both state and input delays of the same length N 1 ; i.e., when setting ξ 1 (k

-N 1 ) = u 2 (k -N 2 ) x(k + 1) =F(x(k), u 1 (k -N 1 ), ξ 1 (k -N 1 )) (6a) ξ (k + 1) =Aξ (k) + Bu 2 (k) (6b) with ξ N (k + 1) = ξ 1 (k + N) = u 2 (k) for k ≥ 0.

B. The reduced dynamics

Because of the cascade structure of (6), we introduce the extended reduction variable η e = (η , ξ ) composed of two components: the usual one defined for the x-dynamics (6a) over the N 1 -steps delay; a mere copy of the state extension ξ . Accordingly, one gets

η(k) :=F -N 1 0 (•) • F N 1 (x(k), u 1[k-N 1 ,k[ , ξ 1[k-N 1 ,k[ ) =F -N 1 0 (•) • F(•, u 1 (k -1), ξ 1 (k -1)) • . . . • F(x(k), u 1 (k -N 1 ), ξ 1 (k -N 1 )).
By construction, the η e -dynamics is delay free with respect to the control variables u = (u 1 , u 2 ). As a matter of fact, one computes the extended reduced dynamics as

η(k + 1) =F r (η(k), u 1 (k), ξ 1 (k)) (7a) ξ (k + 1) =Aξ (k) + Bu 2 (k) (7b) with F r (η, u 1 , ξ 1 ) = F -N 1 0 (•) • F(•, u 1 , ξ 1 ) • F N 1 0 (η)
and a copy of (6b) which is free of delays itself. Moreover, (7) exhibits a cascade structure with connection variable ξ 1 and unchanged drift term F r (η, 0, 0) = F 0 (η).

The following result can be thus given while the proof is omitted as it follows the lines of [START_REF]Nonlinear discrete-time systems with delayed control: A reduction[END_REF] by exploiting the strictfeedforward cascade structure of ( 7) when suitably interconnected to the original dynamics (5) in closed loop [START_REF] Mattioni | Lyapunov stabilization of discrete-time feedforward dynamics[END_REF].

Theorem 3.1: Consider the two-channel input delayed dynamics [START_REF] Karafyllis | Discrete-time systems[END_REF] with invertible drift term F 0 (•). Any feedback u = (α 1 (η, ξ ), α 2 (η, ξ )) achieving Global Asymptotic Stability (GAS) of the equilibrium of the reduced model [START_REF] Seuret | Delays and Networked Control Systems[END_REF] ensures GAS of the equilibrium of (5).

The cascade structure is the core of the stabilizing design over the reduced dynamics we shall discuss on in Section IV among other possibilities.

Remark 3.2:

As an alternative reduction design, one might introduce an artificial delay over the less retarded input channel u 1 so to directly compensate the delay mismatch and then apply the standard methodology in [START_REF]Nonlinear discrete-time systems with delayed control: A reduction[END_REF]. However, this approach induces a dynamical feedback over u 1 .

C. An alternative differential/difference representation

Assuming for the sake of simplicity p 1 = p 2 = 1 and following [START_REF] Monaco | Discrete-time state representations: a new paradigm[END_REF], one can equivalently describe the dynamics (7) via the so-called (F 0 , G)-representation. Denoting by η + e (u 1 , u 2 ) any curve in R n+N parametrized by (u 1 , u 2 ), an equivalent representation of ( 7) is provided through two coupled differencedifferential equations over R n+N as η + = F 0 (η), η + := η + (0, 0) (8a)

ξ + = Aξ , ξ + := ξ + (0, 0) (8b) ∂ η + (u 1 , u 2 ) ∂ u 1 = G 1 (η + (u 1 , u 2 ), ξ + 1 (u 1 , u 2 ), u 1 , u 2 ) (8c) ∂ ξ + (u 1 , u 2 ) ∂ u 1 = 0 (8d) ∂ η + (u 1 , u 2 ) ∂ u 2 = 0, ∂ ξ + (u 1 , u 2 ) ∂ u 2 = B (8e)
with G 1 (η, ξ 1 , u 1 , u 2 ) being a vector field over R n+N , parameterized by (u 1 , u 2 ) and verifying1

G 1 (F r (η, u 1 , ξ 1 ), ξ 2 , u 1 , u 2 ) :=∇ u 1 F r (η, ξ 1 , u 1 ). (9)
Thus, for any (k, η e (k), u 1 (k), u 2 (k)), one recovers [START_REF] Seuret | Delays and Networked Control Systems[END_REF]

η e (k + 1) = η + e (0, 0) + u 1 (k) 0 G e1 (η + e (u 1 , 0), u 1 , 0)du 1 + u 2 (k) 0 G e2 (η + e (u 1 (k), u 2 ), u 1 (k), u 2 )du 2 ( 10
)
with

G e1 = (G 1 , 0), G e2 = (0, B). Remark 3.3:
The integral form [START_REF] Mattioni | Further results on sampled-data stabilization of time-delay systems[END_REF] rewrites as (see [START_REF] Monaco | Discrete-time state representations: a new paradigm[END_REF])

η e (k + 1) = η + e (0, 0) + u 1 (k) 0 G e1 (η + e (u 1 , u 2 (k)), u 1 , u 2 (k))du 1 + u 2 (k) 0 G e2 (η + e (0, u 2 ), 0, u 2 )du 2
because by definition the vector fields G e1 (η e , u 1 , u 2 ) and G e2 (η e , u 1 , u 2 ) verify the so called compatibility conditions

∇ u 1 G e2 (•, u 1 , u 2 ) -∇ u 2 G e1 (•, u 1 , u 2 ) = G e1 (•, u 1 , u 2 ), G e2 (•, u 1 , u 2 ) with G e1 , G e2 = (∇ η e G e2 )G e1 -(∇ η e G e1 )G e2 .
IV. STABILIZATION OF THE EXTENDED REDUCED DYNAMICS-AN I&I APPROACH Hereinafter, we discuss the design of a stabilizing controller for the reduced dynamics [START_REF] Seuret | Delays and Networked Control Systems[END_REF] by assuming the existence of a stabilizing feedback when there is no mismatch in the delays acting over the input channels of (5) (i.e., when N 2 -N 1 = 0). Assumption 4.1 (Uniform delay): When N = N 2 -N 1 = 0, there exists a feedback u 1 = γ 1 (η), u 2 = γ 2 (η) which makes the origin a GAS equilibrium for the "ideal" reduced-dynamics

η(k + 1) =F r (η(k), u 1 (k), u 2 (k)) (11)
computed over the uniformly delayed system (1). Remark 4.1: Assumption 4.1 can be inferred from the stabilizability of the delay-free dynamics associated to [START_REF] Karafyllis | Discrete-time systems[END_REF]. For further details the reader is referred to [START_REF]Nonlinear discrete-time systems with delayed control: A reduction[END_REF].

In the following, we denote γ(•) = (γ 1 (•), γ 2 (•)). Under Assumption 4.1, the existence of a stabilizing feedback over the multi-delayed dynamics (5) can be proved by defining an I&I feedback over the extended reduced model [START_REF] Seuret | Delays and Networked Control Systems[END_REF]. For this purpose, the I&I design over the dynamics [START_REF] Seuret | Delays and Networked Control Systems[END_REF] proceeds along the steps sketched below. Target dynamics -From Assumption 4.1, one deduces the target dynamics over R n as

ζ (k + 1) =F r (ζ (k), γ 1 (ζ (k)), γ 2 (ζ (k))) (12)
possessing a GAS equilibrium at the origin.

Immersion mapping -The immersion mapping π : R n → R n+p 2 N is defined as

π(ζ ) = ζ (k) π 2 (ζ (k)) =       ζ (k) γ 2 (ζ (k)) γ 2 (ζ (k + 1)) . . . γ 2 (ζ (k + N -1))       where, for i = 1, . . . , N ζ (k + i) = F r (•, γ(•)) • • • • • F r (ζ (k), γ(ζ (k))) i times .
The on-the set feedback is thus given by

c(ζ (k)) = (c 1 (ζ (k)), c 2 (ζ (k))) = (γ 1 (ζ (k)), γ 2 (ζ (k + N)))
so that the following invariance condition is verified

F r (ζ (k), c 1 (ζ (k)), γ 2 (ζ (k)) Aπ 2 (ζ (k)) + Bc 2 (ζ (k)) = π(F r (ζ (k), γ(ζ (k)))).
Invariant set -The invariant set is described as the null set of the mapping φ (η, ξ ) : R n+p 2 N → R p 2 N with φ (η, ξ ) = col{φ 1 (η, ξ ), . . . , φ N (η, ξ )} and for any i = 1, . . . , N

φ i (η(k), ξ (k)) = ξ i (k) -γ 2 (η(k + i -1))
with for i = 1, . . . , N and u 1 = γ 1 (η)

η(k + i) = F r (•, γ 1 (•), ξ i (k)) • • • • • F r (η(k), γ 1 (η(k)), ξ 1 (k))
i.e., one sets

M ={(η, ξ ) ∈ R n × R p 2 N s.t. φ i (η, ξ ) = 0 for i = 1, . . . , N}.
Accordingly, the off-the-set component is defined over R p 2 N as z = col(z 1 , . . . , z N ) with z i = φ i (η, ξ ) for i = 1, . . . , N.

The following result can now be enhanced by showing that Assumption 4.1 is sufficient to infer I&I stabilizability of the extended reduced dynamics [START_REF] Seuret | Delays and Networked Control Systems[END_REF]. The proof is omitted as it follows the lines of [START_REF] Monaco | Immersion and invariance stabilization of nonlinear discrete-time dynamics with delays[END_REF].

Proposition 4.1: Under Assumption 4.1, any feedback ψ(η e , z) : R n+p 2 N × R p 2 N → R p making the trajectories of the closed-loop system

z(k + 1) =Az(k) + Bψ 2 (η e (k), z(k)) η(k + 1) =F r (η(k), ψ (η e (k), z(k)), ξ 1 (k))) ξ (k + 1) =Aξ (k) + Bψ 2 (η e (k), z(k))
bounded for all k ≥ 0 with lim k→∞ z(k) = 0 and ψ(π(ζ ), 0) = c(ζ ) ensures I&I stabilizability of the reduced dynamics [START_REF] Seuret | Delays and Networked Control Systems[END_REF]. Accordingly, the origin is a GAS equilibrium for

η(k + 1) =F r (η(k), ψ 1 (η e (k), φ (η e (k))), ξ 1 (k)) (13a) ξ (k + 1) =Aξ (k) + Bψ 2 (η e (k), φ (η e (k))). (13b)
The I&I stabilizing feedback is given in the theorem below. Theorem 4.1: Let the system (5) verify Assumption 4.1. Then, the reduced model ( 7) is I&I stabilizable with target dynamics [START_REF]Nonlinear discrete-time systems with delayed control: A reduction[END_REF] under the I&I feedback u = ψ(η e , z)

u 1 (k) = ψ 1 (η e (k), z(k)) =γ 1 (η(k)) (14a) u 2 (k) = ψ 2 (η e (k), z(k)) = z(k) + γ 2 (η(k + N)) (14b)
verifying ψ(π(ζ ), 0) = c(ζ ) and with making A + B Schur.

Proof. The proof follows the lines of the main result in [START_REF] Monaco | Sampled-data stabilization of nonlinear dynamics with input delays through immersion and invariance[END_REF]. It is a matter of computations to verify that by construction of the immersion mapping, invariance of the closedloop dynamics is ensured by the choice c

1 (ζ (k)) = γ 1 (ζ (k)), c 2 (ζ (k)) = γ 2 (ζ (k + N))
. Thus, the associated set is feedback invariant and the overall design aims at making it attractive while ensuring boundedness of the extended dynamics

z(k + 1) =Az(k) + B(u 2 (k) -γ 2 (η(k + N))) η(k + 1) =F r (η(k), u 1 (η(k)), γ 2 (η(k)) + z 1 (k)) =F r (η(k), u 1 (k), γ 2 (η(k))) + F (η(k), u 1 (k), z 1 (k)) ξ (k + 1) =Aξ (k) + Bu 2 (k) with F (η, u 1 , z 1 ) := p 2 ∑ i=1 z i 1 0 ∇ v i F r (η, u 1 , c i γ 2 (η) + v i )dv i with z 1 = col(z 1 1 , . . . , z p 2 1 ), c i = (1 p 2 -i+1 0 1×i-1 ) and v i = (z 1 1 , . . . , z i-1 1 , v i , 0 1×i-1
). As a result, I&I stability is ensured by any feedback of the form ( 14) making A + B Schur.

Remark 4.2: Contrarily to classical prediction methods, the feedback ( 14) requires the computation of the trajectories of the reduced dynamics [START_REF] Seuret | Delays and Networked Control Systems[END_REF] over N steps ahead by also minimizing the prediction horizon.

V. A CHAINED DYNAMICS AS AN EXAMPLE

As an example consider the chained dynamics [START_REF] Giamberardino | Exact steering and stabilization of a PVTOL aircraft[END_REF] ẋ1 (t) = x 2 (t), ẋ2 (t) = u 1 (tτ 1 ), ẋ3 (t) = x 5 (t) ẋ4 (t) = x 6 (t), ẋ5 (t) = u 2 (tτ 2 ) ẋ6 (t) = -x 3 (t)(1 + u 1 (tτ 1 ))

and let the control be piecewise constant over time intervals of length δ (the sampling period) with respective delays τ i = N i δ , N i ∈ N for i = 1, 2.

Remark 5.1: The above system might represent the dynamics provided after suitable coordinates change and feedback as described in [START_REF] Giamberardino | Exact steering and stabilization of a PVTOL aircraft[END_REF]. Setting x = col(x 1 , . . . , x 6 ) and x(k) := x(kδ ), one exactly computes the sampled-data equivalent model as

x(k + 1) =A δ x(k) + B δ 0 (u 1 (k -N 1 ), u 2 (k -N 2 )) (15)
+ B δ 1 (u 1 (k -N 1 ))x(k) with A δ =         1 δ 0 0 0 0 0 1 0 0 0 0 0 0 1 0 δ 0 0 0 -δ 2

1 , u 2 ) = δ 2 u 1 2 δ u 1 δ 2 u 2 2 -δ 4 (1+u 1 )u 2 24 δ u 2 -δ 3 (1+u 1 )u 2 6 B δ 1 (u 1

 1212423611

Fig. 1 .

 1 Fig. 1. δ = 10 seconds and x d = (10, 0, 0, 10, 0, 0)

  by integrating (8c)-(8d) over the interval [0, u 1 (k)[ and (8e) over the interval [0, u 2 (k)[ and initial condition (8a)-(8b) with η e = η e (k); i.e. η e (k + 1) = η + e (u 1 (k), u 2 (k)) with

Because F 0 (•) admits an inverse, then F r (•, u 1 , u

) is smooth enough and admits an inverseF -1 r (•, u 1 , u 2 ) for (u 1 , u 2 ) ∈ R 2 sufficiently small.

This work was partially supported by the international project CNRS-NSFC-PRC1197 for cooperation among France, Italy and China.

A. A reduced feedback for the uniformly delayed case

Assuming N 1 = N 2 = 1, we want to solve a steering problem for the chained dynamics. Basically, we aim at defining a feedback law so that the full state x(k) reaches a desired value x d = (x 1 d , 0, 0, x 2 d , 0, 0) in exactly one step over δ (deadbeat). For this purpose, we first rewrite the error dynamics as ε(k) = x(k)x d and compute the corresponding dynamics

possessing an equilibrium at the origin to be stabilized. Accordingly, we apply our procedure to stabilize [START_REF] Bekiaris-Liberis | Predictor-feedback stabilization of multi-input nonlinear systems[END_REF]. By noticing that B δ 1 (u 1 )x d = 0, one defines the reduction as

))ε(k) and the corresponding reduced dynamics as

As far as control design is concerned, we first build the feedback stabilizing [START_REF] Mattioni | Lyapunov stabilization of discrete-time feedforward dynamics[END_REF] in the uniformly delayed case (i.e., when N 1 = N 2 ) so to guarantee the requirements in Assumption 4.1. For this purpose, we set up a multi-rate strategy of orders m 1 = 2 and m 2 = 4 over, respectively, u 1 and u 2 by setting

At any sampling instant t = kδ by denoting δ = δ 4 and by dropping the k-argument in the right hand side, the multi-rate reduced model gets the form

2 ) with six control inputs. Accordingly, one computes the feedback

, 2 and j = 1, . . . , 4) as the unique solution to η(k + 1) ≡ 0 also ensuring global exponential stability of ( 16) when N 1 = N 2 = 1 and, thus, Assumption 4.1.

B. The double-channel case

Assuming now N 1 = 1 and N 2 = 2, one computes the extended reduced model of the error dynamics under multirate sampling as

By applying the I&I procedure in Section IV, one computes the off-the-set component as z j (k) = ξ j (k)γ j 2 (η(k)). Accordingly, for i = 1, 2 and j = 1, . . . , 4, the final multi-rate feedback gets the form

C. Simulations

Simulations of the proposed deadbeat maneuver are reported when applying the I&I reduced feedback and setting j = 0 for j = 1, 2, 3, 4 and desired final configuration x d = (10, 0, 0, 10, 0, 0) when starting from the origin. The red solid lines represent the evolution of the target and the controls when a uniform delay affects all of the input channels, while the blue solid lines represent the actual behavior in the multichannel (MC) case with N 1 = 1 and N 2 = 2.

The proposed strategy ensures convergence of the dynamical system toward the desired final position in the desired number of steps while ensuring η(k) ≡ 0 in exactly one step (simulations of this last scenario are omitted for the sake of space). Furthermore, we note that the proposed feedback still ensures stability for larger values of the sampling period while still guaranteeing small control effort.

VI. CONCLUSIONS

In this paper, we show how to extend the reduction approach to handle time-delay systems affected by two distinct inputdelays. Moreover, we exhibit one among the possible controllers by combining reduction and Immersion and Invariance arguments for achieving stabilization in closed loop. The proposed methodology applies to sampled-data delayed dynamics under entire delays. Future works are toward different directions: sampled-data systems under non-entire delays [START_REF]Sampled-data reduction of nonlinear input-delayed dynamics[END_REF]; a comparison with the continuous-time prediction framework with special emphasis on the cascade like representations provided by transport PDEs [START_REF] Bekiaris-Liberis | Lyapunov stability of linear predictor feedback for distributed input delays[END_REF], [START_REF] Bekiaris-Liberis | Predictor-feedback stabilization of multi-input nonlinear systems[END_REF] with respect to the discrete-time one [START_REF] Monaco | Sampled-data stabilization of nonlinear dynamics with input delays through immersion and invariance[END_REF]; the specialization of this methodology to different scenarios where time delays are unavoidable as in networked systems [START_REF] Liberati | Stochastic and exact methods for service mapping in virtualized network infrastructures[END_REF].

ACKNOWLEDGMENT

The authors thanks the anonymous reviewers for their helpful and interesting comments and suggestions. Mattia Mattioni thanks the Université Franco-Italienne/Università Italo-Francese (UFI/UIF) for supporting his mobility through the Da Vinci grant 2016.


Elisabeth Pelz
email: pelz@u-pec.fr

Timed Processes of Interval-Timed Petri Nets

. First we introduce the notion of timed processes for ITPNs inductively. Then we investigate if the equivalence of inductive and axiomatic process semantics -true for classical Petri nets -could hold for ITPNs too. We will see that the notions of independence and immediate firing obligation seem to be antagonistic ones, and that local axioms, adequate to define processes of classical Petri nets, are not sufficient to caracterize timed Processes of IITPNs. We propose several original "global" axioms which reveal to be an effective solution. Thus we yield finally a full axiomatic definition of timed processes for ITPNs.

Introduction

Petri nets are an algebraic and graphical formalism, proposed by Carl Adam Petri [START_REF] Petri | Fundamentals of a Theory of Asynchronous Information Flow[END_REF], used to represent complex interactions and activities in a system, they model situations like synchronisation, sequentiality, concurrency and conflict. Classical Petri nets do not carry any time information and so they are not suitable for quantitative analysis of the performance and reliability of systems with respect to time.

Several time extensions of Petri nets have been proposed in the literature, [START_REF] Merlin | A Study of the Recoverability of Communication Protocols[END_REF][START_REF] Ramchandani | Analysis of Asynchronous Concurrent Systems by Timed Petri Nets[END_REF]. In this paper, we consider Interval-Timed Petri Nets (ITPNs) with autoconcurrency which are a generalisation of Timed Petri Nets. The main feature of Interval-Timed Petri Nets is that transitions which are enabled need to start immediately their firing, and the firing lasts some time within an (integer) interval. Thus in the observation the startfiring and the endfiring of a transition are considered as two distinct events. Furthermore, in the class of ITPNs we consider here, we allow transitions to take no time (i.e. to have zero duration). This obligation of immediate firing led to the standard execution of Timed Petri Nets in (simultanous) maximal steps.

Let us state precisely the concepts which lead to the describtion of the behaviour of ITPNs under maximal step semantics, cf. [START_REF] Pelz | Interval-timed petri nets with auto-concurrent semantics and their state equation[END_REF]. Each transition has its own clock. The progress of time is managed by a global clock by means of (discrete) ticks which increment all local clocks. Inbetween two ticks, we must fire as many transitions as possible, i.e., for a maximal number of enabled transitions there are startfiring events; but also, we have to endfire every fired transition which reach its maximal duration (i.e., which must endfire) plus an arbitrary multiset of fired transitions which may endfire. The maximal multiset of events which occur between two time ticks is called a global step. In [START_REF] Pelz | Interval-timed petri nets with auto-concurrent semantics and their state equation[END_REF] such standard semantics of ITPNs in terms of firing step sequences are exhaustively defined.

By convention, we only consider ITPNs with zero duration which are wellformed, as in [START_REF] Pelz | Interval-timed petri nets with auto-concurrent semantics and their state equation[END_REF], i.e. where no infinite global step is possible.

Partial order semantics allow to describe the behaviour of concurrent systems by expressing explicitly concurrency, seen as independency. Processes are the usual partial order semantics for classical Petri nets [START_REF] Starke | Processes in petri nets[END_REF][START_REF] Best | Nonsequential Processes -A Petri Net View[END_REF]. They are also defined for time Petri nets [START_REF] Aura | Time processes for time petri-nets[END_REF][START_REF] Winkowski | Algebras of processes of timed petri nets[END_REF][START_REF] Valero Ruiz | Timed processes of timed petri nets[END_REF] as well as for high level Timed Petri nets (with onesafe markings) [START_REF] Fleischhack | Hierarchical Timed High Level Nets and their Branching Processes[END_REF]. Processes of classical Petri Nets can be defined by axiomatic definitions or by inductive ones using firing sequences, as discussed in [START_REF] Best | Sequential and concurrent behaviour in petri net theory[END_REF].

Inspired by this approach, we define in this paper timed processes for ITPNs, inductively using firing step sequences. To our knowledge processes have never been introduced for this class. Our definitions will be coherent with the approach in [START_REF] Fleischhack | Hierarchical Timed High Level Nets and their Branching Processes[END_REF], albeit arbitrary markings and auto-concurrency introduce new challenges. We propose a way to respect also the above quoted concepts of immediate firing obligation and global tick in the inductive definition.

But when trying to define timed processes axiomatically, some antagonism appears. Let us remind that the axiomatic definition (for classical Petri Nets) states local properties which are true for all events in the process, independently of all other events and independently of any particular cut (or marking). Now, for ITPNs, events have to satisfy global contraints too, they are no longer independent but inter-dependent and cuts (before ticks) will play the role of synchronisation barriers. In particular, each tick event depends on the set of events which precede it. We will see the limits of an axiomatization where only local properties are defined and illustrate them with an example. Then gradually the global constraints are discussed and formulated in "global" axioms. Such global axioms are something original in Petri Net semantics. We succeed to give them in first order logic without quantification on sets (or cuts). Finally we are able to present a group of local and global axioms which form a total axiomatization of timed processes.

The remaining of the paper is organized as follows: Section 2 contains formal definitions about Interval-Timed Petri Nets. In Section 3 basic definitions around partial order structures can be found. Section 4 gives an inductive definition of timed processes and Section 5 details the discussion and formulation of an axiomatic one. Section 6 presents some concluding remarks.

Some Definitions

Let us start to define classical Petri nets.

Definition 1 Petri Nets

A Petri net is a 3-tuple N = (P, T, v) such that -P and T are finite sets of places and transitions respectively with P ∩ T = ∅ -v : (P × T ) ∪ (T × P ) -→ N is its valuation function.

The states of Petri nets are described by markings M : P -→ N which are represented by vectors of dimension |P |.

Let x be a node such that, x ∈ P ∪ T . The preset of x is denoted by • x, with • x = {y ∈ P ∪ T | v(y, x) > 0}. Similarly, x • denotes the postset of x, with x • = {y ∈ P ∪ T | v(x, y) > 0}. In the same manner, the preset of a net N is defined by

• N = {x ∈ P ∪ T | • x = ∅}, the postset of a net N is defined by N • = {x ∈ P ∪ T | x • = ∅}.
Formally, a multiset U of events E is a mapping U : E → N, such that, for e ∈ E the natural number U (e) is called the multiplicity of e. The multiset U can be written in the extended set notation U = {e U (e) | e ∈ E and U (e) = 0}.

Several time extensions of classical Petri nets have been proposed to integrate temporal modeling properties, time Petri nets [START_REF] Merlin | A Study of the Recoverability of Communication Protocols[END_REF], timed Petri nets [START_REF] Ramchandani | Analysis of Asynchronous Concurrent Systems by Timed Petri Nets[END_REF] and causal time Petri nets [START_REF] Bui Thanh | Petri nets with causal time for system verification[END_REF].

In this paper, Interval-Timed Petri Nets (ITPNs) are considered in their most general setting, i.e. allowing zero duration and autoconcurrency. ITPNs are an extension of Timed Petri Nets in which the firing duration of each transition is given within an interval. We recall shortly the definitions of [START_REF] Pelz | Interval-timed petri nets with auto-concurrent semantics and their state equation[END_REF], which contains much more details and examples.

Definition 2 Interval-Timed Petri Nets An Interval-Timed Petri Net is a 5-tuple N = (P, T, v, M 0 , I) such that -(P, T, v) is a Petri net, called skeleton of the net N -M 0 : P -→ N is its initial marking -I : T -→ N, N is its interval function.
We suppose that the set of transitions is enumerated: T = {t 1 , t 2 , .., t |T | }. The time interval associated with a transition t is given by I(t) = sfd(t), lfd(t) , where sfd(t) is called the shortest firing duration and lfd(t) ≥ sfd(t) the longest firing duration. Only ITPNs are considered whose transitions have a non empty preset and postset i.e., for each transition t ∈ T holds that | • t| > 0 and |t • | > 0.

In Interval-Timed Petri Nets a marking is not sufficient to describe completely the state of a net. The state must also include temporal informations. This is given by a matrix which codes the transitions clocks.

Definition 3 State A state of an ITPN N = (P, T, v, M o , I) is a pair S = (M, h) such that -M is a marking. -h is a clock matrix which has |T | rows and d columns s.t. d = max ti∈T lfd(t i ) + 1 .
The value h i,j+1 represents the number of active transitions t i with age j (i.e. fired since j time ticks).

The set of all possible states of N is denoted by States(N ). The initial state of N is denoted S 0 = (M 0 , h 0 ) where M 0 is the initial marking of the skeleton and h 0 is a zero matrix, i.e. no transition is active.

Firing rules for ITPNs Definition 4 Autoconcurrently enabled transitions

Let N be an ITPN and S = (M, h) its current state. Then a transition t is enabled at the marking M n times autoconcurrently if ∀p ∈ P, n • v(p, t) M (p). If n = 1 this is the usual definition of (single) enabling. For each transition the value E i (M ) tells how many times (at most) transition t i can be fired autoconcurrently at marking M . Thus

E i (M ) = n i if ∀p ∈ P, (n i • v(p, t i ) M (p) and ∃p ∈ P, (n i + 1) • v(p, t i ) > M (p) .
When transitions may fire, firing starts immediately; this is done by removing input tokens from the preplaces of the chosen transitions. A startfired transition t stays active for some time delay in between its associated time interval sfd(t), lfd(t) , until it may or must endfire by delivering the output tokens to its postplaces. Three types of events are distinguished : startfire, endfire and tick events. The effect of each of these events on the state of an ITPN is given below.

Definition 5 State change rules

Let N be an ITPN and (M, h) its current state.

1. Startfire events : A startfire event, denoted by [t i , may occur immediately, even up to n times, if

t i is enabled at M , resp. if E i (M ) = n.
For each occurrence of [t i the needed input tokens of t i are removed from their preplaces, the clock associated with t i will count this occurrence by incrementing the number h i,1 .

(M, h)

[ti -→ (M , h ) with M = M - p∈ • ti v(p, t i ) and h i,1 = h i,1 + 1.
There may be conflicts between enabled transitions, and the way they are solved is arbitrary. Tick events may not occur when there are still enabled transitions, i.e., if for some i, E i (M ) > 0. 2. Endfire events : An endfire event, denoted by t i must occur (even n times)

if the clock associated with some t i reach the upper bound of its associated interval i.e. h i,j+1 ≥ 1 with j = lfd(t i ). An endfire event t i may occur if there is an active transition t i with age in [sfd(t i ), lfd(t i )[ . The corresponding h i,j+1 is then decremented.

(M, h) ti -→ (M , h ) if sfd(ti) j lfd(ti) h i,j+1 > 1 with M = M + p∈t • i v(t i , p
) and h i,j+1 = h i,j+1 -1 for some j with h i,j+1 > 0.

If this new state enables some transitions, one or more startfire events must then occur, and if endfire events(of zero duration) must occur in the sequel, they have to be handled, and so on. 3. Tick events : A tick event, denoted by , is enabled once neither a startfire event nor a must endfire event have to occur. The tick event increments the clocks for all active transitions and models the passing of time.

(M, h) -→ (M , h ) with M = M and for all i holds if

E i (M ) = 0 and h i,lfd(ti)+1 = 0 then h i,j = h i,j-1 if 1 < j d 0 if j = 1 . p1 t1 [0, 2] t2 [1, 1] p2 p3 t3 [0, 0] t4 [1, 3] p4 t5 [1, 2] 2 Fig. 1: ITPN N
The condition of the occurrence of a tick event ensures that what have occurred since the previous tick event (i.e. in between two ticks) is maximal. In the case of transitions which may late zero time, which is allowed in the net class considered here, the notion of start firing event which need to occur "immediately", means "before the next tick". There is no time scale within zero time. The following definition will precise the notion of global step which happens in between two ticks and where multisets of startfire and endfire events will alternate until nothing more need to occur.

We only consider wellformed ITPNs in this article. They ensure to have always only a finite number of events which appear between two ticks. If there is no firing sequence of transitions of possible zero duration which increases a marking, the ITPN is wellformed. This property is decidable on the subnet restricted to transitions whose sfd is zero.

All results given here could be easily extended to ITPNs which are not necessarily wellformed: they allow infinite global steps where no tick event can follow. Thus such an infinite global step would be the "end" of a step firing sequence. We just like to limite the considerations here to the standard wellformed case.

Maximal Step Semantics for ITPNs

The executions of wellformed ITPNs with zero duration and autoconcurrency under maximal step semantics are given by the so called firing step sequence as defined in [START_REF] Pelz | Interval-timed petri nets with auto-concurrent semantics and their state equation[END_REF], where a firing step sequence is an alternating sequence of globalsteps and ticks.

A globalstep is a multiset of firing events of an ITPN in between two tick events, it consists on two principal multisets, the first one is called Endstep and the second one is called Iteratedstep. So a firing step is a triplet (Endstep, Iteratedstep, tick), or a couple (globalstep, tick).

An Endstep at state S contains all endfire events which must occur at S and an arbitrary multiset of endfire events which may occur at S. At the beginning, at initial state S 0 , it is always empty as no transition has startfired. In the following steps, it can be empty; then the whole global step can be empty and one tick event follows immediately the previous one. An Iteratedstep is an alternating sequence of multisets of startfire events (not necessarily maximal) and multisets of endfire events with zero duration (containing all must endfire ones). The alternation ends if neither a transition is enabled nor an endfire event with zero duration must occur, thus the iterated step is maximal and finite. This situation happens because of the wellformedness.

Thus a firing step sequence σ of length n is given by

σ = S 0 globalstep1 -----→ S0 -→ S 1 globalstep2 -----→ S1 -→ S 2 • • • S n-1 globalstepn -----→ Sn-1 -→ S n .
If in Sn-1 = ( Mn-1 , hn-1 ) no transition is active, i.e. if hn-1 is the Zero-matrix, then we have a deadlock , and the last tick and S n do not exist.

The following example illustrates firing steps.

E xample 1 Consider the ITPN N , one possible initial firing step from its initial state S 0 is given in the sequel. The first Endstep is necessarily empty (Endstep 1 = ∅). Then, suppose that we fire two times t 1 and one time t 2 , i.e. {[t 1

2 , [t 2 } then we choose to endfire t 1 at zero duration, i.e. {t 1 }, after that we fire {[t 4 }, no further startfire event is possible now, so a tick event is executed. The first iterated step is the union of all these multisets :

Iteratedstep 1 = {[t 1 2 , [t 2 } {t 1 } {[t 4 } = {[t 1 2 , [t 2 , t 1 , [t 4 }. Thus a possible first firing step of N is {}, {[t 2 1 , [t 2 , t 1 , [t 4 }, .

True concurrent semantics

In this paper we plan to study the behaviour of ITPNs without sequentializing the observation. Thus we will use partial order semantics to express true concurrency and in particular, nonsequential processes [START_REF] Goltz | The non-sequential behavior of petri nets[END_REF][START_REF] Best | Nonsequential Processes -A Petri Net View[END_REF][START_REF] Starke | Processes in petri nets[END_REF].

Processes have been defined and investigated for classical Petri nets and for some other net classes like time Petri Nets [START_REF] Winkowski | Algebras of processes of timed petri nets[END_REF][START_REF] Aura | Time processes for time petri-nets[END_REF][START_REF] Valero Ruiz | Timed processes of timed petri nets[END_REF]. The only known contribution on process semantics of a timed Petri Net class is [START_REF] Fleischhack | Hierarchical Timed High Level Nets and their Branching Processes[END_REF], but in a context of high level nets with one-safe markings. Arbitrary markings, zero durations of events and auto-concurrency give us new challenges. Also, no axiomatic approach exists until now for time or timed Petri nets.

Partial order structures

Concurrent runs or executions of an ITPN are usually represented by condition/event nets where all arcs have an arc weight 1.

N = (B, E, G) is a condition/event net if B ∩ E = ∅ and G ⊆ (B × E) ∪ (E ×B).
The places of B are called conditions and the transitions of E are called events.

A causal net is a condition/event net N = (B, E, G) such that

-for every b ∈ B, | • b| 1 and |b • | 1, -G * , the transitive closure of G is acyclic,
-N is finitly preceded, i.e., for every x ∈ B ∪ E the set {y | (y, x) ∈ G * } is finite.

Causal nets do not allow any branching at conditions. In a causal net N = (B, E, G), the transitive closure of the flow relation G is acyclic and therefore a partial order. We call it the precedence relation and denote it by ≺. The symbol denotes the reflexive and transitive closure of G.

A homomorphism φ is a mapping that preserves the nature of nodes and the environment of events. A homomorphism is used to connect conditions and events of a causal net to places and transitions of the executed net whose behaviour is observed.

A chain c of a causal net is a set of totally ordered events, i.e., c ⊂ E and ∀e ∈ c ∀e ∈ c (e e) ∨ (e e ) . It can be seen as a sequence of events that occurred during the run of the system.

A set AC of nodes of a causal net is an antichain if ∀x ∈ AC ∀x ∈ AC (¬(x ≺ x ) ∧ ¬(x ≺ x)). An antichain AC is a maximal antichain or a cut if ∀x / ∈ AC the union AC ∪ {x} is not an antichain. Note that usually, cuts are considered restricted to conditions or restricted to events. In particular, a cut restricted to conditions is called cut of conditions or B-cut. Note that each B-cut of a process of a classical Petri Net represent a possible marking that may occur during the concurrent execution for some observer.

Process semantics for ITPNs

A timed process of an ITPN N will be defined as a pair (N , φ) where N is a causal net and φ a homomorphism which labels the causal net with information from the ITPN N . The set of clock labels is introduced to capture information about time elapsed since a transition is active. It is defined by CL = {(t, j) | t ∈ T and j lfd(t i )} and P ∩ CL = ∅.

A clock label (t, j) means that t is active and has age j.

The following set of firing events denoted by FE will label the events:

FE = {[t | t ∈ T } ∪ {t | t ∈ T } ∪ { } and P ∩ F E = ∅.
Thus in a causal net where conditions are labeled in P ∪ CL a B-cut is able to represent a time-state (M,h). Note that for any set B ⊆ B the image φ(B ) defines a multi-set of labels.

Inductive definition

Let N = (P, T, v, M 0 , I) be an ITPN. A timed process π of N is constructed along a possible firing step sequence σ of N , whose length is n o , as follows.

We construct successively labeled causal nets π i = (N i , φ i ) = (B i , E i , G i , φ i ) where φ i : B i ∪ E i → (P ∪ CL) ∪ F E by induction on i by using three Addprocedures given below for the creation of events. The i-th induction step corresponds to the i-th firing step of a σ. We stop if π = (N , φ) = π no .

The sets B CL and B P will be the sets of conditions whose postset is currently empty and which are labeled by clock labels and by places respectively.

Base of induction i = 0: • π 0 = B 0 will be a set of conditions with φ 0 : B 0 → P representing the initial marking such that

∀p ∈ P |φ 0 -1 (p) ∩ B 0 | = M 0 (p).
We set E 0 = 0 = ∅, B P = B 0 and B CL = ∅. Hypothesis: Let n 1. We suppose that ∀i < n, π i = (B i , E i , G i , φ i ) has been constructed and the current B CL and B P are known.

Induction step i = n: We start by setting -If φ i (b) = (t, 0) for some t with lfd(t) = 0, then Add b, t , i . -If φ i (b) = (t, 0) for some t with sfd(t) = 0 and lfd(t) = 0, then Add b, t , i or do nothing. ( Maximality of the globalstep) Repeat step b) until ∀t ∈ T : • t φ(B P )) (i.e. until no startfire event is possible) , then go to c). c) (Treatment of a Tickevent)

B i = B i-1 , E i = E i-1 , G i = G i-1 and φ i = φ i-1 . Then π i is constructed
If B CL = ∅ then Add , i . End (If i = n o )
The three Add-procedures are as follows:

The startfire event creation Add B , [t, i :

-We add an event e with φ i (e) = [t:

E i = E i ∪ {e} . -We add arcs G i = G i ∪ {(b, e)|b ∈ B }. -We add a condition b with φ i (b ) = (t, 0): B i = B i ∪ {b }; B CL = B CL ∪ {b }. -We add an arc G i = G i ∪ (e, b ) and reset B P = B P \ B .
The endfire event creation Add b, t , i :

-We add an event e with φ i (e) = t :

E i = E i ∪ {e} . -We add an arc G i = G i ∪ (b, e) and redefine B CL = B CL \ {b}. -For each p ∈ t • , we add v(t, p) conditions B = {b 1 , .., b v(t,p) } with φ i (b ) = p for all b ∈ B : B i = B i ∪ B and B P = B P ∪ B . -We add arcs G i = G i ∪ {((e, b )|b ∈ B }.
The tick event creation Add , i :

-We add an event e with φ i (e) = :

E i = E i ∪ {e}. -We add arcs G i = G i ∪ {(b, e)|b ∈ B CL }.
-For each b ∈ B CL , if φ i (b) = (t, j) for some t and j, then we add a condition b with φ i (b ) = (t, j + 1):

B i = B i ∪ {b } and an arc G i = G i ∪ (e, b ). -We redefine B CL = e • .
We observe that c) happens at each step because of the wellformedness of the executed ITPN. If B CL = ∅ then a deadlock appeared; otherwise a tick is added. A process construction stops after the creation of some tick event, except for deadlock. Thus global steps are fully included. It is easy to see, that for each i the cut π • i is a B-cut and represents the time-state S i+1 reached after the execution of the considered firing step sequence of length i, respectively Sn0-1 in the case of a deadlock after n 0 global steps. We use abreviation as follows: i Denotes condition bi and j denotes event ej.

Axiomatic definition and how to overcome its limits

We start by proposing an axiomatization by local properties of events as processes of a classical Petri Nets have been axiomatized, for instance in [START_REF] Best | Sequential and concurrent behaviour in petri net theory[END_REF]. The causal net π = (N , φ) is an timed evolution of N if ) for some t and some j < lfd(t) and

φ : B ∪ E → (P ∪ CL) ∪ F E is a homomorphism verifying -∀b ∈ B,
* ∀t ∈ T ∀j ∈ [0, d] |φ -1 ((t, j)) ∩ • e| = |φ -1 ((t, j + 1)) ∩ e • |
These axioms define especially local properties of events in the same way as axioms of processes for classical Petri Nets, i.e., they ensure that each event has a correct pre-and postset of conditions with respect to the firing rule. Only the initial cut and the final one are evoked. It is evident that each event of an inductively defined process satisfies clearly the corresponding axiom.

First let us state the following sentence. Proposition 1 There are evolutions which are not processes.

Proof. An evolution of the net N of Fig. 1 is given in Fig. 3. It respects all points of the axiomatic definition but does not correspond to any firing step sequence of N . We can see in this example that tick event e 2 is not global as it should be, and may only occur when neither a startfire event nor a must endfire event is possible. In particular, e 3 and e 4 are independent from e 2 , thus conditions b 8 and b 9 are also independent from e 2 instead of entering it. These axioms also allow infinite evolutions, and we could have added an axiom like [π • = ∅ and ∀b ∈ B ∃x ∈ π • b ≤ x] to ensure that π is finite. But as finiteness will be a consequence of the axioms adjoined in the sequel, we omit it here. Fig. 3: An evolution which is not a process of running example.

Therefore, with the given axiomatic definition we are unable to avoid some partial orders that violate important properties like the fact that tick events have to be global and have to form a chain. Let us try to formulate supplementary axioms about non local properties for tick events: The axiom (a) ensures that all tick events form a chain in the partial order, and (b) that all conditions entering later tick events are necessarily greater than other preceding tick events, thus in particular greater than its potential direct predecessor tick. In particular, for the running example, point (b) makes impossible to creat a "partial" tick event like e 2 in Fig. 3, as b 9 and b 8 entering e 5 are not comparable to (and not greater than) e 2 .

Finally global axioms about maximality and concerning the final cut have to be defined. Final cut axioms:

-(d) ∀t ∈ T ∃p ∈ • t |φ -1 (p) ∩ π • | < v(p, t) -(e) ∀t ∈ T ∀b (φ(b) = (t, lf d(t)) ⇒ |b • | = 1) -(f) ∀x ∈ π • φ(x) ∈ P ∨ ∃e (φ(e) = ∧ ∀x (e ≺ x ⇒ φ(x) ∈ CL) ∧ ∀b / ∈ e • (φ(b) ∈ CL) ⇒ b • = ∅)
As by (d) no startfire event is possible at the final cut π • , availible tokens (P labeled conditions) are maximally used for startfire events and thus the obligation of startfiring, up to some choice, is satisfied. By axiom (e) must endfire events must occur. Axiom (f) ensures that either (case 1) all elements in the final cut are place labeled, which together with (d) means that the process ends by an deadlock; or (case 2) there is a last tick event whose postset are clock labeled conditons in the final cut π • and all other clock labeled conditons have a successor; i.e., they enter in an endfiring event, or they enter in a tick event which is by axiom (b) the appropriate one and not a later one.

We may conclude that what happens between two tick events is a global step and axioms (d) and (e) together ensure its maximality. Axiom (f) also implies the finiteness of the process. Finally the finite cut correspond to the time state reached after the execution of all events of the evolution.

The initial cut • π and the final cut π • are the only sets of nodes evoked in the given axioms; they are just used like constant sets. Thus we have successfully avoided to use second order quantification over sets -representing intermediate B-cuts -in all proposed axioms.

As consequence of these observations we obtain the desired result.

Proposition 2 Let N be a wellformed ITPN. Then the class of timed evolutions of N which also satisfy the axioms (a) to (f ) is the same as that of timed processes of N defined inductively.

Conclusion

In this paper we investigate ITPNs in their most general setting, i.e., with autoconcurrency and with zero duration. In a previous paper their usual maximal step semantics were introduced [START_REF] Pelz | Interval-timed petri nets with auto-concurrent semantics and their state equation[END_REF], in terms of firing step sequences. The goal of the present article is to present their truly concurrent behaviour. Thus first, timed processes of ITPNs have been defined inductively along firing step sequences. Then the possibility of defining these processes in an axiomatic way too are studied. Our first attempt was to propose local axioms, similar to the way processes of classical Petri Nets are defined axiomatically, obtaining the so called timed evolutions. Then we stated and illustrated the fact that some timed evolutions do not correspond to any firing step sequence and therefore they cannot be timed processes.

Several supplementary "global" axioms are gradually formulated and discussed. They are a novelty when defining processes, but the price to pay to capture global timing and firing constraints.

We succeed to give a full axiomatization of timed processes totally compatible with the firing step semantics.

Acknowlegment

My thanks go to Raymond Devillers for his attentive reading of divers versions and a lot of pertinent remarks and suggestions.

  as follows: a) (Treatment of the first Endstep of the current globalstep) For each condition b ∈ B CL : -If φ i (b) = (t, j) for some t with j = lfd(t) then Add b, t , i . -If φ i (b) = (t, j) for some t with sfd(t) j < lfd(t) then Add b, t , i or do nothing. b) (Treatment of the Iteratedstep of the current globalstep) b.1) (Treatment of Startfirings) If there exists a set B ⊆ B P with φ i (B ) = • t for some t ∈ T , then Add B , [t, i . Repeat b.1) or goto to b.2) . b.2) (Treatment of an Endstep) For each condition b ∈ B CL :

Fig. 2 :

 2 Fig. 2: An arbitrary process of the ITPN N of Fig.1.

1 :• Case 2 :

 12 φ(b) ∈ P ∪ CL and ∀e ∈ E, φ(e) ∈ FE (coherence of labeling). -• π ⊆ B and ∀p ∈ P, |φ -1 (p) ∩ • π| = M 0 (p) (the initial marking). -For each event e of the causal net N it holds : • Case If φ(e) = [t for some t ∈ T then * ∀p ∈ P |φ -1 (p) ∩ • e| = v(p, t) and |e • | = 1 with φ(e • ) = {(t, 0)} If φ(e) = t for some t ∈ T then * | • e| = 1 and φ( • e) = {(t, j)} for some j ∈ [sfd(t), lfd(t)] and * ∀b ∈ e • φ(b) ∈ P and ∀p ∈ P |φ -1 (p) ∩ e • | = v(t, p). • Case 3: If φ(e) = then * ∀b ∈ • e ∪ e • φ(b) ∈ CL and * ∀b ∈ • e φ(b) = (t, j)

  Globality axioms: -(a) ∀e ∀e (φ(e) = ∧ φ(e ) = ) ⇒ (e = e ∨ e ≺ e ∨ e ≺ e ) -(b) ∀e ∀e (φ(e) = ∧ φ(e ) = ∧ e ≺ e)) ⇒ (∀b ∈ • e e ≺ b)