Christophette Blanchet-Scalliet

Frédéric Patras

Counterparty risk valuation for CDS

Counterparty risk valuation for CDS.

Introduction

Default Risk has become one of the key issues of contemporary finance. In practice, default risk computations are directly involved in three, closely connected, but still separated areas: first, the pricing of single and multiname credit derivatives (ABS, CDS, CDOs...), second, risk valuation for regulatory, risk management and economic capital valuation purposes, third, rating assignements. The present article is focused mainly on the first two aspects of risk valuation. Notice however that the next generation of rating methodologies will most probably have to include advanced correlation tools such as the ones considered here.

Although deriving new formulas for credit derivative transactions on two assets, our main interest will be on counterparty risk. Once again, this is a central argument, both for regulatory purposes (counterparty risk was already a key issue in the Basel 1 agreements, but its relevance and complexity was emphasized by the later improvements of the set of rules, see e.g. [START_REF]Bank for International Settlements, OTC Derivatives: settlement procedures and counterparty risk management[END_REF][START_REF] Hull | Risk Management and Financial Institutions[END_REF][START_REF]The Application of Basel 2 to trading activities and the treatment of double default effects[END_REF]) and also for practical risk management.

Concretely, the 2007 "subprime" credit crisis has emphasized how a mispricing of counterparty risk could be dangerous. Before the crisis, financial institutions engaged heavily in credit derivatives transactions for hedging purposes. One of the main side effects of the crisis has been to reveal that their counterparties were not reliable: monoline insurers (who act traditionaly as guarantees for municipalities-type bond emissions but engaged more recently in the ABS business) faced downgrades and/or bankruptcy, whereas some companies offering CDS protection have also been on the wedge of bankruptcy due to spread widenings and collateral agreements. In spite of these facts, in the present state of the art quantitative counterparty risk assessment is still largely in infancy.

We address here one of the fundamental questions in the field, namely we introduce a Merton-type model and derive formulas for the joint distributions of the default events -and other relevant joint probabilities-of two default-prone entities. Closed formulas for counterparty risk on a CDS transaction or for a first-to-default swap on two underlyings follow.

Notice that we refrain to seek for the outmost generality or for a complete list of pricing formulas that could be obtained using the methods developed in the present article. Most credit derivatives on two underlyings with time-dependent payoffs can actually be priced using our results. The exercise of deriving the corresponding formulas is left to the interested reader.

2 Modeling two dimensional default risk.

Recall that we are interested in modeling the counterparty risk on a credit risk transaction. This involves (in general and depending of the particular features of the transaction) the computation of various joint laws. For example, for a vanilla credit default swap, the computation relies on the distribution of the default time of the counterparty and the conditional distribution (w.r. to the default of the counterparty) of the values of the CDS contract. The same methodology can be applied to the valuation of first-to-default contracts on two underlyings when the payoff is time-dependent (see section 4 of the present article; the time-independent case has been addressed in [START_REF] He | Double lookbacks[END_REF][START_REF] Zhou | An analysis of default correlations and multiple defaults[END_REF][START_REF] Patras | A reflection principle for correlated defaults[END_REF]).

We follow Merton's structural approach to risk, where the default of a company is triggered by its firm value falling below a threshold (see [START_REF] Merton | On the pricing of corporate debt: The risk structure of interest rates[END_REF] or e.g. [START_REF] Bielecki | Credit risk: modeling, valuation and hedging[END_REF]Chap. 3]). It is well-known that the original Merton methodology, where the threshold is determined by the firm's liabilities, as well as its natural refinements such as the Black-Cox first passage time formulas [START_REF] Black | Valuing corporate securities: Some effects of bond indenture provisions[END_REF], give qualitatively good but numerically poor results. For example, the structural method will rank correctly the risks of two companies but will not be able to predict the spreads of the corresponding CDS. For pricing purposes, the correct way to use the Merton and Black-Cox models is to calibrate their parameters on the market prices of the securities issued by the companies. Doing so insures that the models price correctly the risk. This is the ground for their various uses, either in credit risk measurement (think to the Basel 2 Vasicek-type large pool formulas [START_REF] Vasicek | Probability of Loss on a Loan Portfolio[END_REF][START_REF] Hull | Risk Management and Financial Institutions[END_REF]), either for pricing purposes (think to the one-factor Gaussian copula model for CDO tranches [START_REF] Ph | Credit derivatives pricing models[END_REF]).

Notice that the computations we are interested in require to go beyond the existing formulas for two-dimensional credit risk in the structural approach [START_REF] He | Double lookbacks[END_REF][START_REF] Zhou | An analysis of default correlations and multiple defaults[END_REF][START_REF] Patras | A reflection principle for correlated defaults[END_REF]. Indeed, the formulas in these articles rely mainly on the computation of the probability that one (and only one) out of two firms defaults or that the two firms default before a given maturity, whereas pricing counterparty risk for a CDS transaction requires (among others) the exact knowledge of default times distributions.

We have tried to keep some balance between generality and the choice of too restrictive assumptions. Notice that the model may be simplified by selecting a suitable subset of meaningful parameters, depending on the particular situations and/or the available set of data. In the end, the model we use is as follows.

We label 1 and 2 the two default-prone entities. In view of applications to counterparty risk, the counterparty will be labelled 2. We write τ 1 (resp. τ 2 ) for the random time when the first (resp. second) entity defaults. Since we work in the structural model, defaults are triggered when two log-normal processes V 1 and V 2 associated respectively to the first and second entity fall below a barrier process. As in Black-Cox [START_REF] Black | Valuing corporate securities: Some effects of bond indenture provisions[END_REF], we assume that the barrier is described by a time-dependent deterministic process v i (t) := K i e γit . At last, we assume that the risk-neutral dynamics of the processes V 1 and V 2 are given by:

dV i (t) V i (t) = (r -k i )dt + σ i dB i (t),
where r is the constant short-term interest rate and B i , i = 1, 2 are two Brownian motions. The coefficient k i is a payout ratio representing net payouts/inflows by the firm, see e.g. the account of Merton's approach in [START_REF] Bielecki | Credit risk: modeling, valuation and hedging[END_REF]Chap.2]. Notice that we use a risk-neutral dynamics since we are interested in pricing formulas, but the same construction holds with a real-life dynamics (just replace r -k i by the drift under the historical probability).

At last, we assume that the Brownian motions B 1 and B 2 are correlated: Cov(B 1 (t), B 2 (t)) = ̺t. This is an important assumption that reflects the fact that the counterparty of a CDS transaction is usually a well-rated company that will not default excepted in a very bad macroeconomic environment. In particular, if the counterparty defaults, one may expect CDS spread on other entities to widen considerably simultaneously. This phenomenon is accounted for by a positive correlation coefficient. It is the main reason, together with the dynamical aspects of the problem, why simplistic counterparty risk models fail, both theoretically and empirically, to account for counterparty-driven loss expectations on derivative contracts.

Counterparty risk

In this section, we derive a closed formula for the counterparty default leg of a CDS contract, that is the present value (PV) of the expected losses on a vanilla single-name credit derivative transaction due to the default of the protection seller. Notice that the notion of counterparty default leg should not be confused with the usual notion of default leg for a CDS contract, that is, the present value of future payments by the protection seller.

We follow standard market practices. Namely, we assume that the CDS contract has a notional value C and that, if the underlying entity defaults, the buyer of protection receives (1 -R u ) • C from the seller of protection, where R u stands for the recovery rate of the underlying entity. Similarly, if the counterparty (the protection seller) defaults at t on the CDS contract, we assume that the buyer of protection receives (1 -R c ) • V + t , where V + t = sup(0, V t ) stands for the positive part of the market value of the CDS contract at t, and where R c stands for the counterparty recovery rate. The present moment is normalized to t = 0 in what follows, it may or may not coincide with the inception of the CDS contract.

Counterparty default leg

Using the joint law of the default time of the counterparty and of the underlying entity for the CDS, we compute the default probability of the underlying entity conditional to the default of the counterparty, and obtain a closed formula for the counterparty default leg.

The coupon payments rate (CDS spread) by the protection buyer is written s. We assume continuous payments of the fees: in practice, fees are payed quarterly (and sometimes semi-annually), but due to the payments-in-arrears conventions, the continuous payments assumption is a reasonable one. It is usually defined, at inception of the contract, by equalizing the fee and default legs of the CDS contract (see Section 3.3. Some empirical adjustment is sometimes done for the counterparty default risk, taking into account advanced risk management parameters such as netting agreements. Our computation of the counterparty default leg leads to a new, sounder, methodology, to assess the fair value of this adjustment.

First, the theoretical counterparty default leg D c is given by

D c = (1 -R c ) • E[e -rτ2 • sup(0, p(V 1 (τ 2 ), τ 2 ))1 τ2<(T ∧τ1) ]
where p(V 1 (τ 2 ), τ 2 ) is the market price of the CDS contract at t = τ 2 (when

τ 1 ≥ τ 2 ). The value p(V 1 (τ 2 ), τ 2
) is obtained as the difference between the default and fee legs, that is:

p(V 1 (τ 2 ), τ 2 ) = D l (V 1 (τ 2 ), τ 2 ) - sC r • E[(1 -e -r((T ∧τ1)-τ2) )1 τ1≥τ2 |F τ2 ]
where we write F t , as usual, for the natural filtration of the probability space underlying the two Brownian motions B 1 (t), B 2 (t). Notice that the term T ∧ τ 1 can be, in most situations, safely replaced by T in the previous expansion. This is because, for standard values for the spreads and implied default probabilities in single-name default risk computations, the computation of the fee leg conditional to the hypothesis that no default occurs is a good first-order approximation to the unconditional fee leg. The following computations could be simplified accordingly. Now, the value of D l (V 1 (τ 2 ), τ 2 ) is given by:

D l (V 1 (τ 2 ), τ 2 ) = E[C(1 -R u )e -r(τ1-τ2) 1 τ2≤τ1≤T |F τ2 ]
Theorem 3.1 The counterparty default leg D c is given by:

D c = C(1 -R c ) * E 1 τ2<(T ∧τ1) e -rτ2 (1-R u + s r ) e -µτ 2 (β-α) N ( -µ τ2 -α(T -τ 2 ) √ T -τ 2 )+e -µτ 2 (β+α) N ( -µ τ2 + α(T -τ 2 ) √ T -τ 2 ) - s r 1-e -r(T -τ2) 1-N ( -µ τ2 -β(T -τ 2 ) √ T -τ 2 )-e -2µτ 2 β N ( -µ τ2 + β(T -τ 2 ) √ T -τ 2 ) + where ν 1 := r -k 1 -γ 1 -1 2 σ 2 1 , α := ν 2 1 σ 2 1 + 2r, β := ν1 σ1 , µ τ2 := ln( V 1 (τ 2 ) v 1 (τ 2 ) ) σ1
.

Indeed,

p(V 1 (τ 2 ), τ 2 )1 τ2<(T ∧τ1) = C1 τ2<(T ∧τ1) E (1 -R u )e -r(τ1-τ2) 1 τ2≤τ1<T - s r 1 τ2<τ1 + s r e -r(τ1-τ2) 1 τ2≤τ1<T + s r e -r(T -τ2) 1 τ2≤T <τ1 |F τ2
and therefore

p(V 1 (τ 2 ), τ 2 )1 τ2<(T ∧τ1) = C1 τ2<(T ∧τ1) E (1-R u + s r )e -r(τ1-τ2) 1 τ2≤τ1<T |F τ2 -E s r 1 τ2<τ1 |F τ2 +E s r e -r(T -τ2) 1 τ2≤T <τ1 |F τ2 .
The Theorem follows by standard computations of integrals over Gaussian densities that are sketched in the Appendix 1.

Explicit formulas

Recall that τ i = inf{t, V i (t) ≤ K i e γit }. The condition V i (t) ≤ K i e γit can be rewritten: W i (t) ≥ y i 0 , where W i (t) = ln( Kie γ i t Vi(t) ) -ln( Ki Vi(0) ) and y i 0 = ln V i (0)ln K i . Equivalently, W i (t) is the diffusion process:

dW i (t) = -ν i t -σ i dB i (t), with W i (0) = 0 and ν i := r -k i -γ i -1 2 σ 2 i . Let us define Z(t) by: Z(t) = (Z 1 (t), Z 2 (t)) * = 1 1 -̺ 2 σ -1 1 -̺σ -1 2 0 1 -̺ 2 σ -1 2 y 1 0 -W 1 (t) y 2 0 -W 2 (t)
.

We get:

dZ 1 (t) = φ 1 dt + dX 1 (t), dZ 2 (t) = φ 2 dt + dX 2 (t),
where X(t) is a standard planar Brownian motion and

φ 1 = ν 1 σ 2 -ν 2 σ 1 ̺ σ 1 σ 2 1 -̺ 2 , φ 2 = ν 2 σ 2 .
In particular, Z(t) is a 2-dim. Brownian motion with drift and the barrier conditions

V i (t) = v i (t) now read: Z 2 (t) = 0 and 1 -̺ 2 Z 1 (t) + ̺Z 2 (t) = 0.
We want to compute the default leg D c , that is, equivalently:

E[h(B 1 (τ 2 ), τ 2 )1 τ2≤(T ∧τ1) ] = E[ h(Z 1 (τ 2 ), τ 2 )1 τ2≤(T ∧τ1) ] = T 0 +∞ 0 h(r, s)P (τ 2 ∈ ds, Z 1 (τ 2 ) ∈ da)dsda where h(x, t) := e -rt (1-R u + s r ) e -µx,t(β-α) N ( -µ x,t -α(T -t) √ T -t )+e -µx,t(β+α) N ( -µ x,t + α(T -t) √ T -t ) - s r 1-e -r(T -t) 1-N ( -µ x,t -β(T -t) √ T -t )-e -2µx,tβ N ( -µ x,t + β(T -t) √ T -t ) + , µ x,t := σ -1 1 (ν 1 t+σ 1 x+ln V 1 (0)-ln K 1 ) and h(z, t) = h( -y 1 0 -ν1t σ1 + 1 -ρ 2 •z, t).
Applying the Girsanov theorem, (Z 1 (t), Z 2 (t)) * is a classical Brownian motion for the probability law Q:

dQ dP = e -φ1X1(T )-φ2X2(T )-[ φ 2 1 2 + φ 2 2 2 ]T Pa.s. Let r 0 e iθ0 := Z 1 (0) + iZ 2 (0) = y 1 0 σ2-̺y 2 0 σ1 σ1σ2 √ 1-̺ 2 + i y 2 0 σ2 . Lemma 3.2 We have, for (a, 0) ∈ R 2 s.t. a > 0 : P(τ 2 ∈ dt, τ 2 = τ 2 ∧ τ 1 , Z 1 (τ 2 ) ∈ da) = e φ1(a-r0 cos(θ0))-φ2r0 sin(θ0)-|| φ|| 2 t 2 π α 2 ta e -(a 2 +r 2 0 )/2t ∞ n=0 n sin nπθ 0 α I nπ/α ( ar 0 t )dadt.
where || φ|| 2 := φ 2 1 + φ 2 2 , α := arcsin(̺) + π 2 and I nπ/α is the modified Bessel function of index nπ/α. The Lemma follows from Thm. in Appendix 2 (up to a straightforward adaptation since we consider here a polyhedral domain D := {(x, y) ∈ R 2 |y ≥ 0, 1 -̺ 2 x + ̺y ≥ 0} with a horizontal lower -instead of an upper-boundary, so that the signs have to be changed accordingly in the formulas).

Indeed, according to [START_REF] Carslaw | Conduction of heat in solids[END_REF] (see also [13, pp.697]), we have, for (a, b) in a neighborhood of (a, 0) with b > 0:

f (a, b, t)dadb = Q(Z(t) ∈ (da, db), τ 1 ∧ τ 2 > t) = 2µ αt e -(µ 2 +r 2 0 )/2t ∞ n=0 sin nπθ α sin nπθ 0 α I nπ/α ( µr 0 t )dµdθ,
where θ := arctg( b a ), µ := √ a 2 + b 2 . Therefore, we have:

Q(τ 2 = τ 2 ∧ τ 1 , τ 2 ∈ dt, Z 1 (τ 2 ) ∈ da) = π α 2 ta e -(a 2 +r 2 0 )/2t ∞ n=0 n sin nπθ 0 α I nπ/α ( ar 0 t )dadt,
and the proof follows.

Theorem 3.3 The counterparty default leg D c of the CDS is given by:

D c = C(1 -R c ) T 0 +∞ 0 h(µ, t)e φ1(µ-r0 cos(θ0))-φ2r0 sin(θ0)-|| φ|| 2 t 2 π α 2 tµ e -(µ 2 +r 2 0 )/2t ∞ n=0 n sin nπθ 0 α I nπ/α ( µr 0 t )dtdµ.
Notice that although involving a double integral on Gaussian densities and Bessel function (which asymptotic behavior is well-understood, making numerical approximations easy and efficient), this kind of higher order integrals is highly familiar in physics (heat conduction in solids, cross-sections computations, acoustics...) and can be handled efficiently. However these techniques are not, for the time being, of our competence, and we postpone to further work the numerical analysis of the problem. For the use of Bessel functions in physics, we refer to the classical treatises such as [START_REF] Carslaw | Conduction of heat in solids[END_REF][START_REF] Gray | A treatise on Bessel functions and their applications to physics[END_REF][START_REF] Watson | A treatise on the theory of Bessel functions[END_REF].

Fair price of a CDS

In this section, we take advantage of our computation of the counterparty default leg to compute the fair price of a CDS contract at an arbitrary time (normalized again to t = 0 in this section) between the inception of the contract and its maturity T . As usual, it is obtained as difference between the default and fee legs, but, contrary to the usual pricing formulas, we take into account exactly the effect of the counterparty default leg.

Notice that we insist in deriving exact formulas but, for practical purposes, it may be convenient to use the standard approximation schemes to simplify the use of the formulas and fasten the computations. For example, in order to compute the fee leg, it may be convenient to assume that defaults can occur only at times t i , i = 1...n, so that the following integral expressions can be safely replaced by finite sums involving only the computation of the default probabilities P(τ 1 ∧ τ 2 ≤ t).

Let us write D s for the "standard" default leg of the CDS, that is, the present value of the cash-flows corresponding to payments by the seller of protection if there is a default occurring on the assets underlying the CDS contract. The total default leg D tot of the CDS contract is given by the sum D s + D c , where D c is given by Thm. 3.3.

Lemma 3.4

The standard default leg is given by:

D s = C(1 -R u ) T 0 +∞ 0 e φ1(µ cos(α)-r0 cos(θ0))+φ2(µ sin(α)-r0 sin(θ0))-|| φ|| 2 T 2 π α 2 tµ e -(µ 2 +r 2 0 )/2t ∞ n=0 (-1) n+1 n sin nπθ 0 α I nπ/α ( µr 0 t )dµdt
The proof follows from the same reasoning as the one of Lemma 3.2 and can be omitted.

Notice that:

Q(τ 1 ∈ dt, τ 1 = τ 1 ∧ τ 2 , Z 1 (t) + iZ 2 (t) = dµ • e iα ) = π α 2 tµ e -(µ 2 +r 2 0 )/2t ∞ n=0 (-1) n+1 n sin nπθ 0 α I nπ/α ( µr 0 t )dµdt
Let us write s for the spread of the CDS contract (the continuous coupon rate served by the protection buyer to the protection seller, till the end of the contract, or the default of the underlying, or the default of the protection seller); s is fixed at inception of the contract and remains constant till the maturity T . Recall that the fee leg of a credit derivative contract is the present value of cumulated payments by the protection buyer. We write from now on τ for τ 1 ∧ τ 2 .

Lemma 3.5 The fee leg F of the CDS contract is given by:

F s -1 = 1 -e -rT r P(τ ≥ T ) + E[ 1 -e -rτ r 1 τ ≤T ] = 1 -e -rT r ∞ 0 α 0 e φ1(µ cos(κ)-r0 cos(θ0))+φ2(µ sin(κ)-r0 sin(θ0))-|| φ|| 2 T 2 2µ αT e -(µ 2 +r 2 0 )/2T ∞ n=1 sin nπκ α sin nπθ 0 α I nπ/α ( µr 0 T )dµdκ + T 0 +∞ 0 1 -e -rt r e φ1(µ cos(α)-r0 cos(θ0))+φ2(µ sin(α)-r0 sin(θ0))-|| φ|| 2 T 2 π α 2 tµ e -(µ 2 +r 2 0 )/2t ∞ n=0 (-1) n+1 n sin nπθ 0 α I nπ/α ( µr 0 t )dµdt + T 0 +∞ 0 1 -e -rt r e φ1(µ-r0 cos(θ0))-φ2r0 sin(θ0)-|| φ|| 2 t 2 π α 2 tµ e -(µ 2 +r 2 0 )/2t ∞ n=0 n sin nπθ 0 α I nπ/α ( µr 0 t )dtdµ
The first term was computed in [13, p.698], the last two follow from our previous computations.

Theorem 3.6 The fair price of a CDS, taking into account the counterparty risk, is given by: D tot -F where F and D tot are given by the previous Lemmas.

First-to-default on two underlyings

As was mentioned in the introduction, most credit derivative transactions on two default-prone instruments with time-dependent payoffs can be priced using the techniques developed in the present article. As an example, we derive the fair spread of a first-to-default contract on two underlyings. Most notations are as above, when we were dealing with the counterparty risk on a CDS, and we do not recall them excepted when necessary. The only difference is that, now, the two default-prone entities are treated on the same footing. We still write C for the notional value of the contract and assume a given recovery rate R (e.g. 40%) so that, at the first default occuring before the maturity of the contract, the buyer of protection will receive C(1 -R) (recall this is the very definition of a first-to-default contract; on the other hand, the buyer of protection pays a continuous fee -still called the "spread"-till the first default occurs or till the maturity of the contract if no default occurs before the maturity). On the other hand, the fee leg is given by the same formula as in Lemma 3.5 -this is because the coupon is served by the protection buyer till a first default occur in both cases (a CDS with counterparty risk or a first-to-default swap on two underlyings).

Theorem 4.2 The fair spread s of a first-to-default swap on two underlyings at inception of the contract is given by

s = D F ′
where D is given by Lemma 4.1 and F ′ = F s -1 by Lemma 3.5.

Appendix 1: Theoretical default legs for CDS

We include in this section a proof of the formulas for the market price of a CDS conditional to the default of the counterparty. These are classical computations and/or variations thereof. We give therefore only short indications and refer to [START_REF] Bielecki | Credit risk: modeling, valuation and hedging[END_REF]Chap. 3] for further details. The notations are as in Section 3; N stands as usual for the cumulated standard normal distribution. Lemma 5.1 On the set τ 2 < τ 1 , we have:

P (τ 1 ≤ T |F τ2 ) = N ( -Y τ2 -ν 1 (T -τ 2 ) σ 1 √ T -τ 2 ) + e -2ν1σ -2 1 Yτ 2 N ( -Y τ2 + ν 1 (T -τ 2 ) σ 1 √ T -τ 2 ),
where

Y t := ln( V1(t) v1(t) ) = ln( V1(0) K1 ) + ν 1 t + σ 1 B 1 (t), ν 1 := r -k 1 -γ 1 -1 2 σ 2 1 .
The lemma is a direct application of Cor. E[e -r(τ1-τ2)

1 τ1<s |F τ2 ] = = e -µτ 2 (β-α) N ( -µ τ2 -α(s -τ 2 ) √ s -τ 2 ) + e -µτ 2 (β+α) N ( -µ τ2 + α(s -τ 2 ) √ s -τ 2 ),
where α :=

ν 2 1 σ 2 1 + 2r, β := ν1 σ1 , µ τ2 := Yτ 2 σ1 .
Indeed by the previous lemmas,

E[e -r(τ1-τ2) 1 τ1<T |F τ2 ] = T τ2 e -r(s-τ2) dP (τ 1 ≤ s|F τ2 ) = T τ2 e -r(s-τ2) [dN ( -Y τ2 -ν 1 (s -τ 2 ) σ 1 √ s -τ 2 ) + e -2ν1σ -2 1 Yτ 2 dN ( -Y τ2 + ν 1 (s -τ 2 ) σ 1 √ s -τ 2 )] = α + β 2α e -µτ 2 (β-α) N ( -µ τ2 -α(T -τ 2 ) √ T -τ 2 )+ α -β 2α e -µτ 2 (β+α) N ( -µ τ2 + α(T -τ 2 ) √ T -τ 2 )+ +e -2ν1σ -2 1 Yτ 2 [ α -β 2α e -µτ 2 (-β-α) N ( -µ τ2 -α(T -τ 2 ) √ T -τ 2 )+ α + β 2α e -µτ 2 (-β+α) N ( -µ τ2 + α(T -τ 2 ) √ T -τ 2 )],
and the formula follows.

6 Appendix 2: First hitting time in a polyhedral domain

Our results rely largely on the following two-dimensional extension of a Theorem of Daniels, see [START_REF] Daniels | Sequential tests constructed from images[END_REF]Fla 3.1]. This natural extension is important in view of applications to multidimensional Brownian processes, particularly in the setting of credit risk. It was first announced without a proof in [START_REF] Iyengar | Hitting lines with two-dimensional Brownian motion[END_REF] and could be easily extended to higher dimensional cases. We could not find a proof in the literature, and include therefore a short demonstration in this appendix. Let Z (x0,y0) t (abbreviated to Z t when no confusion can arise), a planar Brownian starting at (x 0 , y 0 ) evolving in a polyhedral domain D with absorbing boundary ∂D. We write τ for the first hitting time of the boundary and f (x 0 , y 0 , x, y, t) (abbreviated to f (x, y, t) when no confusion can arise) for the density of the surviving process:

f (x, y, t)dxdy := P (Z t ∈ (dx, dy), τ > t)

We look for the distribution of hitting times: P (τ ∈ dt, Z τ ∈ dp), dp ∈ ∂D and can assume (up to a planar rotation) that ∂D is horizontal and an upper boundary for D in the neighborhood of p, so that dp is a horizontal line element: dp = (da, b), with p = (a, b) ∈ ∂D. The Theorem follows.

Lemma 4 . 1 ee

 41 The default leg of the contract is given by:D = C(1-R)[ -rte φ1(µ cos(α)-r0 cos(θ0))+φ2(µ sin(α)-r0 sin(θ0))-|| φ|| 2 T -rt e φ1(µ-r0 cos(θ0))-φ2r0 sin(θ0)-|| φ|| 2 t

Lemma 5 . 2 √ c 2 -Corollary 5 . 3

 52253 For a, b, c ∈ R with b < 0 and c 2 > a: 2a, g(y) := e b(c-d) N ( b-dy √ y ), h(y) := e b(c+d) N ( b+dy √ y ).See Lemma 3.2.1, Fla. 3.16 in[START_REF] Bielecki | Credit risk: modeling, valuation and hedging[END_REF]. We have, on τ 1 > τ 2 :

Theorem 6 . 1

 61 We have:P (τ ∈ dt, Z τ = (da, b)) = -1 2 ∂ ∂b f (a, b, t)dadt.(1)Sketch of the proof : Let us write φ(x, y, ∆t)dadt for P (τ ∈ dt, Z τ ∈ (da, b)|Z t-∆t = (x, y)), where in practice we will choose ∆t << 1 and study the asymptotics when ∆t goes to 0. From Daniels' theorem[START_REF] Daniels | Sequential tests constructed from images[END_REF] Fla 3.1] which computes the first exit density for a one-dimensional BM, together with the independence of the horizontal and vertical components of a two-dimensional BM, we get, in a neighborhood of (a, b):φ(x, y, ∆t) ∼ = 1 2π∆t 2 exp -(a -x) 2 2∆t • exp -(b -y) 2 2∆t • (b -y)Then,P (τ ∈ dt, Z τ ∈ (da, b))da -1 dt -1 = D f (x, y, t -∆t)φ(x, y, ∆t)dxdy ∼ = D [f (a, y, t-∆t)+(x-a)f ′ x (a, y, t-∆t)+ (x -a) 2 2 f ′′ x (a, y, t-∆t)]φ(x, y, ∆t)dxdyBy symmetry, in a neighborhood of (a, b) in D, φ(x, y, ∆t) ∼ = φ(2a-x, y, ∆t), so that the second term of the expansion vanishes. Since ∂D is an absorbing boundary, f (a, b, t -∆t) = f ′x (a, b, t -∆t) = f ′′ x (a, b, t -∆t) = 0 and the third term reads:D (x -a) 2 2 f ′′ x (a, y, t -∆t)φ(x, y, ∆t)dxdy ∼ =b, t -∆t)dy = O(∆t)Similarly, the first term reads: D f (a, y, t -∆t)φ(x, y, ∆t)dxdy ∼ = e -(b-y) 2 2∆t f (a, y, t -∆t)dy =b, t -∆t)


Luc Dartois
email: ldartois@ulb.ac.be

Paulin Fournier
email: paulin.fournier@labri.fr

Ismaël Jecker
email: ijecker@ulb.ac.be

Nathan Lhote
email: nlhote@labri.fr

On Reversible Transducers

Keywords: 1998 ACM Subject Classification F.4.3 Formal Languages Transducers, reversibility, two-way, uniformization Digital Object Identifier 10.4230/LIPIcs

Deterministic two-way transducers define the robust class of regular functions which is, among other good properties, closed under composition. However, the best known algorithms for composing two-way transducers cause a double exponential blow-up in the size of the inputs. In this paper, we introduce a class of transducers for which the composition has polynomial complexity. It is the class of reversible transducers, for which the computation steps can be reversed deterministically. While in the one-way setting this class is not very expressive, we prove that any two-way transducer can be made reversible through a single exponential blow-up. As a consequence, we prove that the composition of two-way transducers can be done with a single exponential blow-up in the number of states.

A uniformization of a relation is a function with the same domain and which is included in the original relation. Our main result actually states that we can uniformize any non-deterministic two-way transducer by a reversible transducer with a single exponential blow-up, improving the known result by de Souza which has a quadruple exponential complexity. As a side result, our construction also gives a quadratic transformation from copyless streaming string transducers to two-way transducers, improving the exponential previous bound.

Introduction

Automata and transducers. Automata theory is a prominent domain of theoretical computer science, initiated in the 60s [START_REF] Büchi | Weak second-order arithmetic and finite automata[END_REF] and still very active nowadays. Many extensions of finite automata have been studied such as automata over more complex structures (infinite words, trees, etc) or transducers which can be seen as automata with an additional write-only output tape and which will be the focus of our study in the remainder of this article.

Transducers have been studied for almost as long as automata [START_REF] Aho | A general theory of translation[END_REF] and important results have been obtained, however the theory of transducers is not as advanced as automata theory. The language A ˚aA ˚can be recognized by a deterministic (left) or codeterministic (right) automaton, but not by a reversible one.

113:2

One of the reasons for this is that many descriptions which are equivalent for automata become different in expressiveness in the case of transducers. For instance, deterministic and non-deterministic automata recognize the same class of languages, the regular languages. However this is not the case for transducers since in particular a deterministic transducer must realize a function while a non-deterministic one may realize a relation. Similarly, by allowing the reading head to move left and right, one gets a two-way model of automata and it is known that two-way automata are as expressive as one-way automata [START_REF] Shepherdson | The reduction of two-way automata to one-way automata[END_REF]. However two-way transducers can model relations and functions that are unobtainable in the one-way case, such as the function mirror which reverses its input. Recently, two-way transducers were also proven to be equivalent to the one-way deterministic model of streaming string transducers [START_REF] Alur | Expressiveness of streaming string transducers[END_REF], which can be thought of as transducers with write-only registers.

Reversible transducers. A transition system is called reversible when for every input, the directed graph of configurations is composed of nodes of in-degree and out-degree at most one. This property is stronger than the more studied notion of determinism since it allows to navigate back and forth between the steps of a computation. In this article, we study the class of transducers that are simultaneously deterministic and codeterministic, i.e. reversible. The main motivation for the definition of this class is its good properties with respect to composition. When we consider one-way transducers, runs only go forward and thus determinism gives good properties for composition: the next step of a run is computed in constant time. However, when considering composition of two-way transducers, the second machine can move to the left, which corresponds to rewinding the run of the first machine. Then the stronger property of reversibility allows for this back and forth navigation over runs of transducers, and we recover the property of reaching the next (or previous here) step of a computation in a constant time. This leads to the recovery of the polynomial state complexity of composition which exists for deterministic one-way transducers.

Let us now discuss the expressiveness of reversible transducers. Regarding automata in the one-way case, it is well-known that any regular language can be recognized by a deterministic one-way automaton and symmetrically by a codeterministic one-way automaton, since the mirror of a regular language is still regular. However, the class of one-way reversible automata is very restrictive (see Figure 1 for an example or [START_REF] Pin | On reversible automata[END_REF] for a study of its expressive power, where they are called bideterministic). It turns out however, that if we allow bidirectionality then any regular language can be recognized by a reversible automaton. In fact, a two-way reversible automaton can be constructed from either a one-way or two-way automaton using only a linear number of states (see [START_REF] Kondacs | On the power of quantum finite state automata[END_REF] and [START_REF] Kunc | Reversibility of computations in graph-walking automata[END_REF], respectively). We prove, as a consequence of our main theorem, that reversible transducers are as expressive as functional two-way transducers, and exactly capture the class of regular functions. As stated earlier, regular functions are also characterized by streaming string transducers (SST). As a byproduct, we also give a quadratic construction from copyless SST to reversible transducers, improving results from [START_REF] Alur | Regular transformations of infinite strings[END_REF][START_REF] Dartois | Aperiodic string transducers[END_REF].

L. Dartois, P. Fournier, I. Jecker, and N. Lhote

113:3

Synthesis problem and uniformization of transducers. In the bigger picture of verification, two-way transducers can be used to model transformations of programs or non-reactive systems. If we consider the synthesis problem, where the specification is given as a relation of admissible input-output pairs, an implementation is then given as a function, with the same domain, relating a unique output to a given input. The uniformization problem asks if given a relation, we can extract a function that has the same domain, and is included in the relation. We argue that the synthesis problem can be instantiated in the setting of transformations as the problem of uniformization of a non-deterministic two-way transducer by a functional transducer. Our main result states that we can uniformize any non-deterministic two-way transducer by a reversible transducer with a single exponential blow-up.

Related work.

As stated earlier, reversible one-way automata were already considered in [START_REF] Pin | On reversible automata[END_REF]. Two-way reversible automata were shown to capture the regular languages in [START_REF] Kondacs | On the power of quantum finite state automata[END_REF] by a construction from a one-way deterministic automaton to a two-way reversible automaton with a linear blow-up. This construction was extended to two-way automata in [START_REF] Kunc | Reversibility of computations in graph-walking automata[END_REF], still with a linear complexity. However, these constructions for automata cannot be simply extended to transducers because more information is needed in order to produce the outputs at the right moment. To the best of our knowledge, reversible transducers have not been studied yet, however, since we introduce reversible transducers as a tool for the composition of transducers, our work can be linked with the construction of Hopcroft and Ullman that gives the composition of a one-way transducer and a two-way transducer, while preserving determinism. Our construction strictly improves theirs, since ours produces, with a polynomial complexity instead of an exponential one, a reversible transducer that can in turn be easily composed.

A procedure for the uniformization of a two-way non-deterministic transducer by a deterministic one has been known since [START_REF] De | Uniformisation of two-way transducers[END_REF]. The complexity of this procedure is quadruply exponential, while our construction is done in a single one, and produces a reversible transducer.

Organization of the paper. Preliminary definitions are given in the next Section. In Section 3, we present our main results on composability and expressiveness of reversible transducers. Section 4 is devoted to the main technical construction of the paper. Connections with streaming string transducers are discussed in Section 5 while further works are considered in Section 6.

Automata and transducers

Given a finite alphabet A, we denote by A ˚the set of finite words over A, and by ε the empty word. We will denote by A $% the alphabet A Z t$, %u, where the new symbols $ and % are called the left and right endmarkers. A language over A is a subset L of A ˚. Given two finite alphabets A and B, a transduction from

A to B is a relation R Ď A ˚ˆB ˚.
Automata. A two-way finite state automaton (2FA) is a tuple A " pA, Q, q I , q F , ∆q, where A is a finite alphabet; Q is a finite set of states partitioned into the set of forward states Q `and the set of backward states Q ´; q I P Q `is the initial state; q F P Q `is the final state; ∆ Ď Q ˆA$% ˆQ is the state transition relation. By convention, q I and q F are the only forward states verifying pq I , $, qq P ∆ and pq, %, q F q P ∆ for some q P Q. However, for any backward state p ´P Q ´, ∆ might contain transitions pp ´, $, qq and pq, %, p ´q, for some I C A L P 2 0 1 7 113:4

On Reversible Transducers q P Q. Note that, in our figures, we do not represent explicitly the initial and final states, and rather use arrows labeled with the endmarkers to indicate the corresponding transitions. A configuration u.p.u 1 of A is composed of two words u, u 1 P A $% and a state p P Q. The configuration u.p.u 1 admits a set of successor configurations, defined as follows. If p P Q `, the input head currently reads the first letter of the suffix u 1 " a 1 v 1 . The successor of u.p.u 1 after a transition pp, a 1 , qq P ∆ is either ua 1 .q.v 1 if q P Q `, or u.q.u 1 if q P Q ´. Conversely, if p P Q

´, the input head currently reads the last letter of the prefix u " va. The successor of u.p.u 1 after pp, a 1 , qq P ∆ is u.q.u 1 if q P Q `, or v.q.au 1 if q P Q ´. For every word u P A $% , a run of A on u is a sequence of successive configurations " u 0 .q 0 .u 1 0 , . . . , u m .q m .u 1 m such that for every 0 ď i ď m, u i u 1

i " u. The run is called initial if it starts in configuration q I .u, final if it ends in configuration u.q F , accepting if it is both initial and final, and end-to-end if it starts and ends on the boundaries of u. More precisely, it is called left-to-right if q 0 , q m P Q

ànd u 0 " u 1 m " ε; right-to-left if q 0 , q m P Q ´and u 1 0 " u m " ε; left-to-left if q 0 P Q `, q m P Q ´and u 0 " u m " ε; right-to-right if q 0 P Q ´, q m P Q `and u 1 0 " u 1 m " ε.
Abusing notations, we also denote by ∆ the extension of the state transition relation to a subset of Q ˆA$ % ˆQ composed of the triples pp, u, qq such that there exists an end-to-end run on u between p and q. For every triple pp, u, qq P ∆, we say that q is a u-successor of p and that p is a u-predecessor of q. The language L A recognized by A is the set of words u P A ˚such that $ u % admits an accepting run, i.e., pq I , $ u %, q F q P ∆. The automaton A is called a one-way finite state automaton (1FA) if the set Q ´is empty; deterministic if for all pp, aq P Q ˆA$% , there is at most one q P Q verifying pp, a, qq P ∆; codeterministic if for all pq, aq P QˆA $% , there is at most one p P Q verifying pp, a, qq P ∆; reversible if it is both deterministic and codeterministic. weakly branching if for all a P A there is at most one state p P Q and one pair of distinct states q 1 , q 2 P Q such that pp, a, q 1 q P ∆ and pp, a, q 2 q P ∆. An automaton with several initial and final states can be simulated by using non-determinism while reading the endmarker $ and non-codeterminism while reading the endmarker %, hence requiring a single initial state and a single final state does not restrict the expressiveness of our model. Let us remark that unlike in the case of most two-way machines, a reversible two-way automaton always halts on any input. Indeed, codeterminism insures that it is never the case that two transitions head to the same configuration. Hence, the unique run (due to determinism) cannot loop since no configuration can be visited twice, and the first configuration starts from the left of the initial endmarker, which is a configuration that cannot be reached later on in the run.

Transducers. A two-way finite state transducer

(2FT) is a tuple T " pA, B, Q, q I , q F , ∆, µq,
where B is a finite alphabet; A T " pA, Q, q I , q F , ∆q is a 2FA, called the underlying automaton of T ; and µ : ∆ Ñ B ˚is the output function. A run of T is a run of its underlying automaton, and the language L T recognized by T is the language L A T P A ˚recognized by its underlying automaton. Given a run of T , we set µp q P B ˚as the concatenation of the images by µ of the transitions of T occurring along . Note that in the deterministic (or codeterministic) case we are able to extend µ to end-to-end runs since in this case we can unambiguously associate an end-to-end run to a unique sequence of transitions pp, u, qq. The transduction R T Ď A ˚ˆB ˚defined by T is the set of pairs pu, vq such that u P L T and µp q " v for an accepting run of A T on $ u %. Two transducers are called equivalent if they define the same transduction. A transducer T is respectively called one-way (1FT), deterministic, weakly branching, codeterministic or reversible, if its underlying automaton has the corresponding property. Examples. Let us consider the language L aa Ď ta, bu ˚composed of the words that contain two a symbols in a row. This language is recognized by the deterministic one-way automaton A 1 , represented in Figure 2a, and by the reversible two-way automaton A 2 , represented in Figure 2b. However, it is not recognizable by a one-way reversible automaton. Let us analyze the behavior of A 2 to see how moving back and forth through the input allows it to recognize L aa in a reversible manner. First, A 2 uses an intermediate step to go from 1 back to 0 `when reading a b, to avoid creating non-codeterminism. Second, once A 2 reads two consecutive a symbols, it does not go directly in the final state looping on every input, since this would generate non-codeterminism. Instead, A 2 goes in an inverse copy of the first three states, where it rewind its run until the left endmarker. It is then free to go in the looping accepting state.

0 1 2 $ % a a b b a, b (a) A deterministic 1FA A1 0 `1 `1" 1 ´1" 0 " 2 $ % a b a b a a b a $ b a, b (b) A reversible 2FA A2

Results on reversible transducers

In this section, we present the main results of our paper. In Subsection 3.1, we show the polynomial composition of reversible transducers. In the following, we give expressiveness results of the class of reversible transducers, relying on this composition procedure as well as the construction presented in Section 4.

Composition of reversible transducers

The nicest feature of reversible transducers has to be the low complexity (and simplicity) of their composition. Indeed the composition of two such transducers is polynomial in the number of states of the inputs, and the construction is itself quite simple. This is due to the fact that the difficult part in the composition of transducers is to be able to navigate the run easily. In the one-way case, the composition is easy since runs can only move forward. In the two-way case, one needs to advance in the run, but also rewind it. Since the former is made easy by the determinism, and the latter is symmetrically handled by the codeterministim, composition of reversible transducers is straightforward. Let us also remark that only the first transducer has to be reversible in order to obtain a polynomial complexity. However the reversible nature of the obtained transducer depends on the input transducers being both reversible.

Theorem 1. Let T 1 be a reversible two-way transducers and T 2 be two-way transducer with n 1 and n 2 states respectively, such that T 1 can be composed with T 2 . Then one can construct a two-way transducer T 3 with n 1 ¨n2 states realizing R T2 ˝RT1 . Furthermore, if T 2 is reversible, deterministic or codeterministic, then so is T 3 .

Proof. Let T 1 " pA, B, Q, q I , q F , ∆, µq and T 2 " pB, C, P, p I , p F , Γ, νq. We define T 3 " pA, C, Q ˆP, pq I , p I q, pq F , p F q, Θ, ξq. The idea is that at each step, T 3 simulates a transition I C A L P 2 0 1 7

113:6

On Reversible Transducers δ P ∆, plus the behavior of T 2 over the production µpδq P B ˚of this transition. To be precise, the transducer T 3 also detects when it simulates an initial or final configuration of T 1 (i.e. upon reading an endmarker in the initial or final state), and accordingly adds the corresponding endmarker to the production before simulating T 2 . The partition of the set of states of T 3 depends on the combination of the signs of both components. If T 2 is moving to the right, we use the determinism of T 1 , we update the first component of the current state according to the unique transition δ originating from it, and we simulate T 2 entering µpδq from the left. To do so, T 3 needs to have access to the same letter of the input tape as T 1 . Thus, we have pQ `ˆP `q Ď pQ ˆP q `and pQ ´ˆP `q Ď pQ ˆP q ´. If T 2 is moving to the left, then we use the codeterminism of T 1 to rewind the corresponding run, we update the first component of the current state according to the unique transition δ arriving in it, and we simulate T 2 entering µpδq from the right. To do so, T 3 needs to have access to the letter on the other side of the input head (with respect to T 1 ). Thus, we have pQ ´ˆP ´q Ď pQ ˆP q ànd pQ `ˆP ´q Ď pQ ˆP q

´.

We now define the transition function Θ and the production function ξ. Let pq, a, q 1 q P ∆ be a transition of T 1 such that " pp, v, p 1 q is an end-to-end run of T 2 , where v denotes the word µpq, a, q 1 q P B ˚.

If is a left-to-right run of T 2 , then ppq, pq, a, pq 1 , p 1 qq belongs to Θ and produces νpp, v, p 1 q.

If is a left-to-left run of T 2 , then ppq, pq, a, pq, p 1 qq belongs to Θ and produces νpp, v, p 1 q.

If is a right-to-right run of T 2 , then ppq 1 , pq, a, pq 1 , p 1 qq belongs to Θ and produces νpp, v, p 1 q.

If is a right-to-left run of T 2 , then ppq 1 , pq, a, pq, p 1 qq belongs to Θ and produces νpp, v, p 1 q. The behavior of the transducer T 3 is completely determined by the combined behaviors of transducers T 1 and T 2 . When T 3 simulates a transition of T 1 , it also simulates the corresponding end-to-end run of T 2 over the production of this transition. If the direction of both simulations is the same, then T 3 moves forward. Otherwise, it moves backward. The transducer stops when it reaches a final state in both T 1 over the input, and T 2 over the simulated run over partial productions of the run of T 1 over the input. Then the final output of T 3 is the concatenation of the outputs of the partial runs of T 2 it simulates, which corresponds to the output of T 1 . Hence, the transducer T 3 realizes the composition T 2 ˝T1 . The possible determinism (resp. codeterminism) of T 3 is a direct consequence of the one of T 1 and T 2 . Indeed, a witness of non-determinism (resp. non codeterminism) of T 3 can be traced back to a witness run of either T 1 or T 2 that is not deterministic (resp.codeterministic).

One-way transducers

In the next subsections, we give some procedures to construct a reversible transducer from either a one-way or a two-way transducer. The main ingredient of the proofs is the technical construction from Lemma 6 (presented in Section 4) which constructs a reversible transducer from a weakly branching codeterministic one-way transducer. The proofs of this section share the same structure: in order to build a reversible transducer that defines a function F, we express F as a composition of transductions definable by reversible transducers, and we conclude by using Theorem 1. The detailed constructions are presented in the full version of this article. Building on Lemma 6, we show that codeterministic one-way transducers can be expressed as the composition of weakly branching codeterministic ones.

Theorem 2. Given a codeterministic 1FT with n states, one can effectively construct an equivalent reversible 2FT with 4n 2 states.

113:7

Proof. Let T be a codeterministic 1FT with n states. The function R T can be expressed as the composition R T 1 ˝RM , where M and T 1 are defined as follows.

Transducer M is a reversible 1FT with a single state that multiplies all the letters of the input word by n while marking them with a state of T ; Transducer T 1 is a weakly branching and codeterministic one-way transducer that has the same set of states as T . On input R M puq, T 1 mimics the behavior of T on u, while using the fact that the input word is larger to desynchronize the non-deterministic branchings that were occurring simultaneously in T . Intuitively, a transition of T can only be taken by T 1 at the copy of the letter corresponding to the target state of the transition. By Lemma 6, T 1 can be made into a reversible 2FT T 2 with 4n 2 states. Therefore, since both T 2 and M are reversible, we can conclude using Theorem 1, finally obtaining a reversible 2FT with 4n 2 states equivalent to T .

Using composition again, the statement can be extended to deterministic one-way transducers.

Theorem 3. Given a deterministic 1FT with n states, one can effectively construct an equivalent reversible 2FT with 36n 2 states.

Proof. Let T be a deterministic 1FT with n states. Then s T , the transducer obtained by reversing all transitions of T , is codeterministic. The function R T can be expressed as the composition R M B ˝R s T ˝RM A , where M A and M B realize the mirror functions over the input and output alphabet of T respectively. Both of them are realized by a 3 states reversible transducer. Then by Theorem 2, we can construct s T 1 which has 4n 2 states, is reversible and realizes the same function as s T . By Theorem 1, we can compose the three transducers, finally obtaining a reversible transducer equivalent to T with 9 ¨4n 2 states.

Two-way transducers

We now prove our main result, which states that any two-way transducer can be uniformized by a reversible two-way transducer. Let us recall that uniformization by a deterministic transducer was done in [START_REF] De | Uniformisation of two-way transducers[END_REF]. We use similar ideas for the uniformization. The key difference is that we rely on the construction of Section 4 while in [START_REF] De | Uniformisation of two-way transducers[END_REF], the main construction is the tree-trimming construction of Hopcroft-Ullman from [START_REF] Hopcroft | An approach to a unified theory of automata[END_REF].

Theorem 4. Given a 2FT T with n states, one can effectively construct a reversible 2FT T 1 whose number of states is exponential in n, and verifying L

A T 1 " L A T and R T 1 Ď R T .
Proof. Let T " pA, B, Q, q I , q F , ∆, µq be a 2FT with n states. We define a function uniformizing R T as the composition R T 1 ˝RU ˝RDr , where D r , U and T are defined as follows.

The right-oracle D r is a codeterministic one-way transducer with 2 n 2 `n states that enriches each letter of the input word u P A $% with information concerning the behavior of T on the corresponding suffix, represented by the set of pairs that admit a left-to-left run, and the set of states from which T can reach the final state. The uniformizer U is a deterministic one-way transducer with n! states. On input u 1 " R Dr puq, U uses the information provided by D r to pick a run u of T on input u, and enriches each letter a i of the input word with the sequence of transitions occurring in the run u that correspond to the letter a i . Finally, the reversible transducer T 1 has the same set of states as T , and follows the instructions left by U to solve the non-determinism and the non-codeterminism.

I C A L P 2 0 1 7

113:8

On Reversible Transducers

As a consequence of Theorem 2 and Theorem 3, there exist two reversible 2FT D r 1 and U 1 whose number of states are exponential in n, and that verify R D 1 r " R Dr and R U 1 " R U . Therefore, since D r 1 , U 1 and T 1 are reversible, by Theorem 1 there exists a reversible transducer T 2 whose number of states is exponential in n, and that satisfies R T

2 " R T 1 ˝RU 1 ˝RDr 1 " R T .
The following result is a direct corollary of Theorem 4, applied to deterministic two-way transducers.

Corollary 5. Reversible two-way transducers are as expressive as deterministic two-way transducers.

4

The tree-outline construction

In this section lies the heart of our result. We show that any weakly branching and codeterministic transducer can be made reversible. These hypotheses allow us to simplify our proof, and still obtain a more general result, as a corollary.

Lemma 6. Let T be a codeterministic and weakly branching 1FT with m states. Then one can effectively construct a reversible 2FT T 1 with 4m 2 states that is equivalent to T .

Proof. The construction presented in this proof is illustrated on an example in Figure 3. Let T " pA, Q, q I , q F , ∆, µq be a codeterministic 1FT, and let ă be a total order over Q. As an example, take the codeterministic 1FT T presented in figure 3a.

Let T 1 " pA, F, f I , f F , ∆ 1 , µ 1 q be a 2FT defined as follows:

On input u P L T , T 1 explores depth first the run-tree T u composed of the initial runs of T on the word $ u % (illustrated in Figure 3b). More precisely it explores the "sheath" of the run-tree (see Figure 3c for a graphical representation). To do this, the states of T 1 are composed of two states of T with a marker. The first state represents the upper part of the sheath, while the second state represents the lower part. Moreover the marker is used to denote whether we are above the branch (q) or below the branch (q).

Initially we start with the state pq I , q I q and go forward according to the transitions of T . While moving forward whenever a branching state q is reached, if the state is marked q it moves to the maximal successor of q (in order to stay above the branch) and symmetrically if the state is marked q it moves to the minimal successor of q (in order to stay below the branch). Whenever one of the branches reaches a dead end we continue the sheath exploration by switching the marker (i.e. changing from above the branch to below or vice-versa) and start moving backward accordingly to the transitions of T . While moving backward, if the successor of a branching state q is reached, while we were inside the fork, e.g. in state q max (where q max is the maximal successor of q), we continue the exploration of the sheath by going in the state q min and we start moving forward again. Whenever the upper and lower explorations of the sheath coincide, i.e. in states of the form pq, qq (represented in red in Figure 3d), it means we are on a prefix of the accepting run, we can thus produce the corresponding output.

Formally T 1 " pA, F, f I , f F , ∆ 1 , µ 1 q is defined as follows:

F " F `YF ´where F `" QˆQYQˆQ and F ´" pQˆQYQˆQqztpp, pq, pp, pq | p P Qu f I " pq I , q I q f F " pq F , q F q We define the transition relation ∆ 1 by differentiating several types of behavior, depending on whether we are going f orward, or backward, whether the upper component or the

2 1 0 $ $ % b a, b a a (a) A codeterministic transducer T q I 2 1 0 1 0 q F 2 1 (b) The run-tree of T on $ ab % q I 2 1 0 1 0 q F 2 1 (c) Graphical representation of the run of T 1 $ a b % I F 2 1 2 0 2 0 2 1 1 0 1 0 2 1 2 0 2 0 2 1 1 1 1 0 1 0 1 1 0 0 (d)
The run of T 1

Figure 3

Illustrations of the proof concepts of Lemma 6. For the sake of clarity, the outputs of T are omitted. lower component is involved, and whether it is above or below its branch. Let p and q be two states in Q, and a P A be a letter. If p has no a-successor, then: (fua) `pp, qq, a, pp, qq ˘P ∆ 1 , and (fuw) `pp, qq, a, pp, qq ˘P ∆ 1 . If p has an a-successor, but not q, then: (flw) `pp, qq, a, pp, qq ˘P ∆ 1 , and (fla) `pp, qq, a, pp, qq ˘P ∆ 1 . Otherwise, p and q admit an a-successor. We denote p max (resp. p min ) the maximal (resp. minimal) a-successor of p (resp. q) with respect to ă. Then: If p min ‰ p max , then: (buw) `pp max , qq, a, pp min , qq ˘P ∆ 1 , and (bua) `pp min , qq, a, pp max , qq ˘P ∆ 1 . If q min ‰ q max , then: (bla) `pp, q min q, a, pp, q max q ˘P ∆ 1 (blw) `pp, q max q, a, pp, q min q ˘P ∆ 1 (fualw) `pp, qq, a, pp max , q min q ˘P ∆ 1 , (fuwla) `pp, qq, a, pp min , q max q ˘P ∆ 1 , (bulw) ppp min , q min q, a, pp, qqq P ∆ 1 , and (bula) `pp max , q max q, a, pp, qq ˘P ∆ 1 .

We define µ 1 as the function such that for every pp, a, qq P ∆: if q " p min " p max then µ 1 `pp, pq, a, pq, qq ˘" µpp, a, qq if q " p min ‰ p max then µ 1 `pp max , qq, a, pq, qq ˘" µpp, a, qq if q " p max ‰ p min then µ 1 `pq, p min q, a, pq, qq ˘" µpp, a, qq and µ 1 ptq " ε for every t P ∆ 1 which is not of one of theses forms.

I C A L P 2 0 1 7 113:10 On Reversible Transducers

One can see, by a case study that T 1 is deterministic. Indeed, the fact that T is weakly branching implies that the rules (buw) and (bua) are mutually exclusive with the rules (bla) and (blw). Moreover these four rules are mutually exclusive with the rules (bulw) and (bula) by construction. And since T is codeterministic, the predecessor is unique. Finally, the rules (fua), (fuw), (flw), (fla), (fualw), and (fuwla) are mutually exclusive by construction, since the conditions on the number of a-successors are incompatible.

A similar case study gives that T 1 is codeterministic. Hence T 1 is reversible.

A detailed proof of the equivalence between T and T 1 can be found in the full version of the article, and we give a quick intuition of the proof. It relies on two main arguments. The first one is that at any point if the transducer T 1 follows two different runs, then it will come back to the same position, where the state that leads to the shortest run has been switched. Following this, we then prove that upon any branching, T 1 comes back to the same position but since the shortest run has been switched, it is able to solve the non-determinism, take the transition of the accepting run and produce the correct output.

Streaming string transducers

Streaming string transducers, which were introduced in [START_REF] Alur | Expressiveness of streaming string transducers[END_REF], are one-way deterministic automata with additional write-only registers. Partial outputs are stored in the registers via register updates, and at the end of a run an output is produced using these registers. Thus an SST realizes a function over words, and it is known that they are as expressive as 2FT [START_REF] Alur | Expressiveness of streaming string transducers[END_REF]. Direct transformations from SST to 2FT were already considered in [START_REF] Alur | Regular transformations of infinite strings[END_REF][START_REF] Dartois | Aperiodic string transducers[END_REF]. However, these constructions were exponential in the number of states (and linear in the number of registers). Using Theorem 3, we are able to get a construction which is quadratic in the number of states (and also linear in the number of registers). Before explaining the construction, let us formally define the SST.

Substitutions. Given a finite alphabet A and a finite set X of variables. Let S X ,A denote the set of functions σ : X Ñ pX Y Aq ˚. The elements of S X ,A are called substitutions. Any substitution σ can be extended to range over both variables and letters of the output alphabet σ : pX Y Aq ˚Ñ pX Y Aq ˚by setting σpaq " a for every a P A ˚and σpuvq " σpuqσpvq for u, v P pX Y Aq ˚. This allows us to easily compose substitutions from S X ,A by defining σ 2 ˝σ1 as the usual function composition σ2 ˝σ1 . We denote by Id X the identity element of S X ,A , which maps every variable to itself, and by σ ε the substitution mapping every variable to ε. A substitution σ is called copyless if for every X P X , each variable Y P X appears at most once in σpXq, and for every Y P X there exists at most one X P X such that Y appears in σpXq.

Streaming string transducers.

A streaming string transducer (SSTfor short) is a tuple Z " pA, B, Q, q I , q F , ∆, X , O, τ q, where B is the output alphabet, A Z " pA, Q, q I , q F , ∆q is a one-way deterministic automaton, called the underlying automaton of Z; X is a finite set of variables; O P X is the final variable; τ : ∆ Ñ S X ,B is the output function. A run of Z is a run of its underlying automaton, and the language L Z recognized by Z is the language L A Z P A ˚recognized by its underlying automaton. Given a run of Z on u, we set τ p q P S X ,B as the composition of the images by τ of the transitions of Z occuring along . The transduction R Z Ď A ˚ˆB ˚defined by Z is the function mapping any word u of L A Z to pσ ε ˝τ p qqpOq, where is the single accepting run of A Z on $ u %. The SST Z is called copyless, if for every run of Z the substitution τ p q is copyless.

113:11

Theorem 7. Given a copyless SST with n states and m variables, one can effectively construct an equivalent reversible 2FT with 8m ¨n2 states.

Proof. We write Z as the composition of a one-way deterministic transducer D 1 and a reversible one T . The first transducer has the same underlying automaton as Z, the difference being that it outputs the substitution of Z instead of applying it. Then T is a transducer that navigates the substitutions to produce the output word of Z. This can be done in a reversible fashion thanks to the property of copylessness of Z. Note that the transducer T was already defined in [START_REF] Dartois | Aperiodic string transducers[END_REF], Section 4. Formally, let Z " pA, B, Q, q I , q F , ∆, X , O, τ q be a copyless SST with n states and m variables, and let S Z Ă S A,X be the range of τ . We express R Z as the composition of R D1 : L A Z Ñ S Z and R T2 : S Z Ñ B ˚, defined as follows.

D 1 is a deterministic 1FT obtained by stripping Z of its SST structure, i.e., D 1 " pA, S Z , Q, q I , q F , ∆, τ q. It maps each word of L A Z to the corresponding sequence of substitutions.

T " pS Z , B, P, init, f in, Γ, νq where P `" X o Z tinit, f inu, P ´" X i . States labeled by i (resp. o) are in (resp. out) states and appear when we start (resp. finish) producing a variable. We define Γ and ν as follows: pinit, σ, initq P Γ; pinit, $, O i q P Γ; pO o , %, f inq P Γ; pX i , σ, Y i q P Γ and νppX i , σ, Y i qq " v if σpXq " vY... with v P B ˚;

pX i , σ, X o q P Γ and νppX i , σ, X o qq " v if σpXq " v; pX o , σ, Y i q P Γ and νppX o , σ, Y i qq " v if there exists a variable Z where σpZq " ...XvY..; pX o , σ, Y o q P Γ and νppX o , σ, Y o qq " v if σpY q " ...Xv. Due to copylessness, for any σ and any variable X, there is at most one variable Y such that X appears in σpY q. Plus, as the variables are ordered by their appearance in σpY q, the transducer T is reversible. It starts by reaching the end of the word, then starts producing the variable O. By following the substitution tree of O, it then produces exactly the image of the input by Z.

By Theorem 3, there exists a reversible 2FT D 1 1 with 4n 2 states satisfying R D 1 1 " R D1 . Finally, since both D 1 1 and T are reversible, by Theorem 1 there exists a reversible transducer T 1 with 8m ¨n2 states such that R T 1 " R T ˝RD 1 1 " R Z .

Conclusion

We argue that reversible transducers can be seen as a canonical representation of regular transductions. We believe that the polynomial complexity of composition of reversible transducers is a good tool for the verification of cascades of transformations of non-reactive systems. While preserving the expressive power of functional transducers, reversible transducers allow for easier manipulations, the best example being their polynomial composition. Thanks to the tree-outline construction that we presented, one can uniformize a non-determinsitic two-way transducer by a reversible one with a single exponential blow-up. This improves the known constructions that were used up to now, however it is still open whether this blow-up can be avoided. In [START_REF] Kunc | Reversibility of computations in graph-walking automata[END_REF] the authors extended the result of [START_REF] Kondacs | On the power of quantum finite state automata[END_REF] and showed that deterministic two-way automata can be made reversible with a linear blow-up. We conjecture that our approach can also be extended to the two-way case and that deterministic two-way transducers can be made reversible using only a polynomial number of states.

I C A L P 2 0 1 7

113:12 On Reversible Transducers

We have shown that applying this construction allows for a quadratic transformation from copyless streaming string transducers to reversible two-way transducers. The converse does not hold, since even on languages deterministic two-way automata are known to be exponentially more succint than deterministic one-way automata. Beyond this, we do not reject the possibility that if one were to embed some recognition power into the variables of a SST, it may be possible to have a polynomial transformation from reversible automata to copyless SST.

Figure 1

 1 Figure 1The language A ˚aA ˚can be recognized by a deterministic (left) or codeterministic (right) automaton, but not by a reversible one.

Figure 2

 2 Figure 2Two automata recognizing the language Laa " A ˚aaA ˚.

This work was partially supported by the French ANR project ExStream (ANR-13-JS02-0010), the ARC project Transform (Fédération Wallonie Bruxelles) and the FNRS PDR project Flare. I. Jecker is an F.R.S.-FNRS Aspirant fellow.


Jie Han
email: jiehan@xjtu.edu.cn

Unprotected mothers and infants breastfeeding in public amenities during the COVID-19 pandemic

Xue Wang 1 • Jie Han 1 • Eric Lichtfouse 2, 3 The outbreak of the coronavirus disease, named COVID-19, has quickly spread at the global scale. On July 11, 2020, there have been a total of 12,286,264 confirmed cases worldwide (WHO 2020a). Recent studies related to air pollution have reported that the novel coronavirus could survive in the ambient air for several hours and potentially transmit through aerosols, especially in enclosed indoor environments with limited social distancing and poor ventilation [START_REF] Morawska | It is time to address airborne transmission of COVID-19[END_REF][START_REF] Sharma | Environmental chemistry is most relevant to study coronavirus pandemics[END_REF]WHO 2020b). When breastfeeding in public amenities, mothers can wear masks or cloth face coverings to protect themselves from respirable virus carriers in the air, while their infants cannot wear any respiratory protection to avoid direct exposure to the indoor air. With respect to the airborne transmission of COVID-19, breastfeeding in public amenities therefore represents a blind spot in the current regulatory guidelines and risk mitigation efforts (CDC 2020;NHC 2020;WHO 2020c). Here we outline the common issues in the current design of lactation facilities and the use of other public amenities by breastfeeding mothers, as a timely reminder on the potential risks to breastfeeding mothers and unprotected infants during the current pandemic (Fig. 1).

Breastfeeding is the most effective way to ensure the health and survival of infants. For newborns, breastmilk is the ideal food because it is safe, nutritious and contains antibodies (WHO 2020d). While the COVID-19 has been detected in human breastmilk [START_REF] Groß | Detection of SARS-CoV-2 in human breastmilk[END_REF], there has been no evidence to date suggesting transmission to infants via breastmilk, but this appears more and more likely because a recent report has evidenced transplacental transmission to the fetus followed by neurological manifestations [START_REF] Vivanti | Transplacental transmission of SARS-CoV-2 infection[END_REF]. The World Health Organization (WHO) has recommended mothers with confirmed or suspected COVID-19 infection to continue breastfeeding with necessary precautions (WHO 2020e). In the same vein, the American Academy of Pediatrics (AAP) recommends mothers to consider extending the duration of breastfeeding to supply antibodies to their infants or toddlers during the current pandemic (AAP 2020). Overall, breastfeeding appears to be a good practice to maintain the health and reduce the risks for infants during the current pandemic, yet there is a need for sufficient lactation rooms in the public space.

Once a privileged facility, lactation rooms have become more common as a public amenity for lactating mothers and their infants. For instance, the US federal laws require that employers with over 50 employees must provide a placeother than a bathroom-for employees to give breastmilk to infants (NCSL 2020). Some states require shopping malls, airports and public service centers to provide areas for breastfeeding (NCSL 2020). A recent survey shows that only 77% of US airports display information on accesses to lactation rooms [START_REF] Lee | The traveling mother: Navigating, visualizing and utilizing lactation spaces in US airports[END_REF]. In China, the National Health Commission requires that baby care rooms with an area no less than 10 m 2 should be provided at transportation hubs, commercial centers, hospitals, tourist attractions and other public places either wider than 10,000 m 2 or with more than 10,000 visitors per day (NHC 2016). The commission also recommends employers to provide lactation rooms under the same conditions. As a result, in September 2018, there were about 286,000 organizations across the country which had provided lactation rooms in their workplace in China (Anonymous 2019). Overall, the number of lactation rooms has clearly increased, but their design and location may not be optimized.

Several issues have been evidenced in recently set-up public amenities for breastfeeding. For instance, many public lactation rooms are located in corners with an inadequate design, often as small, enclosed spaces with windowless walls. This is dangerous for the heath of mothers and babies because enclosed spaces such as schools and beauty salons are known to concentrate air pollutants [START_REF] De Gennaro | Indoor air quality in schools[END_REF][START_REF] Rogula-Kopiec | Air pollution of beauty salons by cosmetics from the analysis of suspensed particulate matter[END_REF]. A survey of 105 lactation facilities in US university campuses revealed that over 80% of the designated spaces were structurally enclosed, and only about 40% of those places had in-room control of air temperature (Henry-Moss et al. 2019). Worse, only 8% of the busiest US airport fulfilled the minimum requirements of space and facilities for a public lactation room [START_REF] Haight | Airports in the United States: Are they really breastfeeding friendly?[END_REF]. In China, while surveys are scarce, many lactation rooms and baby care rooms were found to be inadequate in sizes and ventilation (PMM 2018). For example, a survey of 60 public locations in three major Chinese cities disclosed that only 24% of locations provided an adequate area of more than 10 m 2 for baby care [START_REF] Teng | The investigation on the space design of the baby care room in public places, a Dissertation submitted for the Master's Degree[END_REF]). Moreover, 70% of those rooms were located next to public toilets, and only 35% of the rooms had good ventilation. This is a serious health issue because [START_REF] Zhu | Air microbiological pollution and its influencing factors in hospital nursing room[END_REF] found severe contamination in indoor air by bacteria in baby care rooms at a hospital, resulting in an overall low compliance rate of 40% versus the national standard. In conclusion, many lactation facilities are inappropriate in terms of location, ventilation, temperature control and health security. Mothers may therefore be tempted to find other locations.

Some mothers opt to breastfeed in public toilets as a secure place shielded from public views and free of intrusion by the opposite sex [START_REF] Sha | Breast-feeding mothers face a policy dilemma: many breast-feed in public toilets[END_REF]. Such practice, which is commonly perceived as breastfeeding in public, threatens the unprotected infants because human wastes carry a myriad of pathogens [START_REF] Haight | Airports in the United States: Are they really breastfeeding friendly?[END_REF][START_REF] Spurles | A qualitative study of attitudes toward public breastfeeding among young Canadian men and women[END_REF][START_REF] Datta | Metagenomic applications in microbial diversity, bioremediation, pollution monitoring, enzyme and drug discovery. A review[END_REF]. Indeed, pathogens could be transmitted not only by airborne transport of respiratory droplets, but also via the fecal-oral route from toilet flushing or poor hygiene. This is very likely because [START_REF] Knowlton | Bioaerosol concentrations generated from toilet flushing in a hospital-based patient care setting[END_REF] found that the atmospheric concentrations of fine particles, below 0.3 μm, and bioaerosols both increased significantly after toilet flushing in hospitals. Moreover, those aerosols formed a prolonged and uniform suspension in air with no obvious attenuation within 30 min after toilet flushing. In the same vein, 81% of aerosols and 78% of surfaces of public toilets located in an office building and a hospital contained respiratory or enteric viruses including the adenovirus, the Torque teno virus and the norovirus GII [START_REF] Verani | Viral contamination of aerosol and surfaces through toilet use in health care and other settings[END_REF]. Overall, breastfeeding in public toilets presents high risk of contamination, which might be aggravated by the fast breathing of infants.

Infants should be exclusively breastfed for six months and then continue to be fed with breastmilk and complementary food at least until 12 months (AAP 2012; WHO 2020f). For infants within six months of age, the general recommendation is 8-12 times during 24 h, each feeding lasting 10-20 min (CDC 2018;[START_REF] Littleton | Breastfeeding FAQs: how much and how often[END_REF]. Most importantly, infants younger than 12 months have much faster respiratory rates than adults, generally in the range 30-50 breaths per minute compared with 12-18 by adults [START_REF] Fleming | Normal ranges of heart rate and respiratory rate in children from birth to 18 years of age: a systematic review of observational studies[END_REF]. While being breastfed, the infant's nose and mouth are exposed to the ambient air, and the infant maintains a faster breathing rate for the suckswallow-breath coordination. This suggests that infants are at elevated risks of exposure to airborne pathogens in public amenities during breastfeeding.

Fig. 1 Risk of infants' exposure to airborne pathogens and pollutants in a public lactation room. The number of lactation rooms have increased in the public space, yet many issues remain to be solved, such as inadequate area, location near toilets, poor ventilation and lack of air temperature control

The COVID-19 episode has also accentuated the risk induced by poor ventilation. Indeed, regulators and utility operators have discouraged the use of air conditioning in confined public spaces to prevent the spread of COVID-19 by air circulation (CPMI 2020; WHO 2020g). This creates a dilemma for facilities lacking natural ventilation such as public lactation rooms. Furthermore, COVID-19 remained viable and infectious in aerosols for three hours at ambient conditions (van Doremalen et al. 2020). Higher rates of viral transmission were observed in confined space when persons were in contact with COVID-19 infected patients [START_REF] Zhao | Investigation of transmission chain of a cluster COVID-19 cases[END_REF]. In addition, breastfeeding in public toilets or family restrooms increases the risk of fecal-oral transmission of COVID-19 [START_REF] Xiao | Evidence for gastrointestinal infection of SARS-CoV-2[END_REF]. High viral loads of COVID-19 have been detected in human feces, even in asymptomatic individuals and recovered patients several weeks after their respiratory samples became clear [START_REF] Han | Viral RNA load in mildly symptomatic and asymptomatic children with COVID-19[END_REF][START_REF] Wu | Prolonged presence of SARS-CoV-2 viral RNA in faecal samples[END_REF][START_REF] Zhang | Detectable SARS-CoV-2 viral RNA in feces of three children during recovery period of COVID-19 pneumonia[END_REF]. Direct evidence was provided on June 25, 2020, by the Beijing Center for Disease Prevention and Control, which announced that two persons became infected after using a public toilet that was later tested positive [START_REF] Li | Solved: Beijing couple infected in a public toilet[END_REF]. This was known as the first confirmed case of COVID-19 transmission in public toilet environments in China. Overall, the risk of virus transmission to breastfeeding mothers and infants in public amenities is high. What could we suggest to improve their safety?

There is actually no viable means of protecting an infant's respiration while being breastfed. To this date, no specific guideline has been published to mitigate such risks during the current pandemic (CDC 2020; NHC 2020). Given that many public breastfeeding amenities are small and poorly ventilated, we suggest that, when not in use, doors should be regularly opened to allow natural ventilation, while standard cleaning and disinfection protocols for public spaces are followed (CDC 2020). When breastfeeding in a public facility, mothers should wear respiratory protection to protect themselves and others who may use the same facility concurrently or shortly after. Mothers should use the facility alone during the current pandemic to reduce the risk of cross-infection between users. In light of the known risks of fecal-oral transmission of COVID-19, breastfeeding in public toilets is not recommended during the current pandemic. Instead, mothers should be encouraged to breastfeed in open areas where good ventilation and physical distancing can be achieved. Efforts should also be put in improving the design of public lactation rooms, including the provision of adequate areas and emergency ventilation facilities. Safety windows should be installed well above the average height of adults with exhaust fans in operation to maintain good ventilation in the room without compromising the privacy of users. More generally, air pollution and the associated health risks should be alleviated both indoors and outdoors using any means [START_REF] Yu | Water spray geoengineering to clean air pollution for mitigating haze in China's cities[END_REF][START_REF] Yu | Fog geoengineering to abate local ozone pollution at ground level by enhancing air moisture[END_REF][START_REF] Feng | Evidence for regional heterogeneous atmospheric particulate matter distribution in China: implications for air pollution control[END_REF][START_REF] Wang | Unexpected rise of ozone in urban and rural areas, and sulfur dioxide in rural areas during the coronavirus city lockdown in Hangzhou, China: implications for air quality[END_REF]. Here, recent results suggest that the use of essential oils, a traditional medicine, may offset the deleterious effect of airborne particulate matter [START_REF] Kfoury | Essential oil components decrease pulmonary and hepatic cells inflammation induced by air pollution particulate matter[END_REF]).

Funding This work was funded by the "Young Talent Support Plan" of Xi'an Jiaotong University.