Patrick Maillé
email: patrick.maille@imt-atlantique.fr

Bruno Tuffin
email: bruno.tuffin@inria.fr

Enforcing free roaming among UE countries: an economic analysis

In October 2015, the European parliament has decided to forbid roaming charges among UE mobile phone users, starting June 2017, as a first step toward the unification of the European digital market.

In this paper, we aim at investigating the consequences of such a measure from an economic perspective. In particular, we analyze the effect of the willingness-to-pay heterogeneity among users (also due to wealth heterogeneity), and the fact that the roaming behavior is positively correlated with wealth.

Considering a monopolistic operator, we compare the paidroaming situation (with usage-based pricing) to the envisioned free-roaming from the point of view of the operator and of users. Our analysis suggests that imposing free roaming degrades the revenues of the operator but can also deter some users from subscribing. This is because paid roaming allows some partial market segmentation; hence we conclude that such (apparently beneficial) regulatory decisions must be taken with care.

I. INTRODUCTION

Users are more and more dependent on online services (email, geographical mapping, ridesharing, ...), and maintaining access to those services while abroad is increasingly valuable. Hence a strong demand for the possibility of roaming, i.e., of having an operator in the visited country provide connectivity services in a seamless manner. This is done through arrangements between operators, that we do not consider in this paper. We rather focus here on the economic aspects of roaming from the user point of view through the prices charged. Since user willingness-to-pay for global connectivity is large, and because of very limited competition on that segment [START_REF] Corliano | Evaluation of the socio-economic implications of contractual mobility in roaming architectures[END_REF], [START_REF] Infante | Regulation of international roaming in the european union-lessons learned[END_REF], the market ends up with relatively high prices for such services.

While some existing work consider the economic aspects of national roaming, with cooperation/competition issues among operators [START_REF] Stühmeier | Roaming and investments in the mobile internet market[END_REF], we concentrate on international roaming. More precisely, we investigate the potential impact of the recent decision of the European parliament 1 to forbid roaming charges in Europe as of June 15, 2017. Already, since April 2016 those roaming charges have been capped, as a period of transition. The aim of those decisions is to create an open European digital market, and foster economic activity by easing travels among EU countries. Also, imposing free-of-charge roaming carries an idea of improved fairness among users, while paid roaming could lead to prohibitive costs for some users. Finally, it is well-known that users have a preference for flat-rate pricing; having no extra charge whatever the data usage (in volume and geography terms) goes in that direction. This was pointed out in [START_REF] Hämmäinen | Flat-rate pricing for international mobile data roaming[END_REF], but at the time (2009) free roaming seemed like an unrealistic option.

Our claim in this paper is that free roaming being beneficial is not always obvious. To investigate the question, we take a simple model with one monopoly operator implementing usage-based roaming pricing (when allowed), and consider the pricing decisions with and without the free-roaming constraint. Our user-side model assumes that there is a positive correlation between the willingness-to-pay for the domestic connectivity service, and the willingness-to-pay for the roaming connectivity service, since both are linked to user wealth (and in addition, we expect wealthier people to travel more often). Assuming the operator selects revenue-maximizing prices for both cases [START_REF] Maillé | Telecommunication Network Economics: From Theory to Applications[END_REF], we show that imposing free-of-charge roaming to the operator can actually worsen the situation for several actors: the operator revenue diminishes, less users subscribe to the (domestic) service, and the least wealthy users would have preferred the paid-roaming situation. This is due to the fact that extra roaming prices allow to discriminate high-income users: the operator can charge less for the basic service and still make substantial revenues through roaming charges that it collects mainly from those wealthy users. Removing that option, all users are charged the same amount: as the unique revenue source, the subscription price is larger, leading to less users subscribing to the service and low-income users being worse off. In summary, enforcing free roaming only benefits to high-income users, to the expense of low-income ones, a phenomenon going against the initial fairness-improvement aim of free roaming. Hence our recommendation is that those aspects be considered with care when making such regulatory decisions or monitoring their implementation.

The remainder of this paper is organized as follows. Section II presents our model for user preferences and operator revenues. The outcomes are computed in Section III, and the paid-roaming and free-roaming situations are compared in Section IV. Conclusions and directions for future work are given in Section V.

II. MODEL

Our mathematical model focuses on a single country, but we keep in mind that different countries will correspond to different markets, hence different distributions among user willingness-to-pay for digital services: this is particularly salient in the UE, where GDP per capita among countries vary by a factor up to 15 2 .

Note that the envisioned rules allow operators to limit roaming rights for frequent travelers, hence we assume here that users can only subscribe to providers operating in their country of residence 3 , a rule imposed by the EU to prevent (unfair) competition between countries. Therefore, the rule does not exactly create a unified European market, and we can still expect discrepancies among subscription prices in different countries.

A. Pricing plan

In this paper, we assume that a monopolistic provider operates in the considered country: following the most popular data plans, we consider that this provider offers an unlimited data consumption plan when in the residence country, at a price (per month) p. Market segmentation and the choice of other quota-based plans are worth studying but are beyond the scope of this paper, where we focus on the impact of roaming charges.

Again following the current market conditions, we assume that roaming data is charged based on usage, through a simple linear pricing scheme. The price per volume unit for roaming traffic is denoted by c, so that a user consuming a roaming volume v (possibly null) over a month, is charged a total amount p + cv.

B. User preferences

For this plan, users have different willingness-to-pay values (in monetary units per month) for the domestic data use. We denote that value for a particular user by θ, and assume that the distribution of θ over the market is known to the operator. Also, users have different needs and preferences in terms of data consumption while roaming: some just travel less than others, and some are willing to pay more for mobile access than others in roaming situations. Nevertheless, we expect a positive correlation between the willingness-to-pay θ for the (local) data plan, and the willingness-to-pay function (in terms of volume) for roaming data, which we denote by r θ (•), a function of the consumed volume over a month.

As a result, for a generic user characterized by θ, the net utility when subscribing to the operator's offer and consuming a volume v r per month (on average) when roaming is of the form

U = θ -p + r θ (v r ) -cv r . (1)
In this paper, to carry out analytical derivations, a specific form for r θ will be considered, as commonly adopted in [START_REF] Cho | Pricing for mobile data services considering service evolution and change of user heterogeneity[END_REF], [START_REF] Maillé | Users facing volume-based and flat-rate-based charging schemes at the same time[END_REF], but other choices can be studied similarly: 2 Source: https://en.wikipedia.org/wiki/Economy_of_the_European_Union 3 http://europa.eu/rapid/press-release_IP-16-3111_en.htm Assumption A: For any value of θ, the function r θ is such that

r θ (x) = θx -α x 2 2 if x ≤ θ α θ 2 2α otherwise.
with α a fixed parameter. The marginal valuation function r θ then has the simple expression

r θ (x) = [θ -αx] +
where [y] + := max(y, 0). Functions defined by Assumption A are non-negative, null at 0, non-decreasing and concave, and cover some expected effects:

• users with high θ values (i.e., willing to pay more for the plan even without roaming) are also willing to pay more for roaming data usage than users with low θ values; • and those users are more frequently out of their residence country, so that if roaming was at no extra cost (i.e., c = 0) they would consume a larger amount of roaming data, here θ α .

III. USER CHOICES AND OPERATOR REVENUE FOR FIXED

PRICES

We assume here that the subscription price p as well as the roaming data per-unit price c are fixed by the operator, and we analyze user choices. Later, we will consider that the operator is able to anticipate those choices, and uses this ability to set p and c so as to maximize revenue.

A type-θ user will consider whether or not to subscribe-and if so, how much roaming data to use-based on p and c. To do so, the user estimates how much roaming data v r (θ) she would use, and just applies (1): if the net utility is positive the user subscribes, otherwise she doesn't. More specifically, we can define the optimal net value from roaming usage V (θ, c) := max x≥0 r θ (x) -cx, so that the net utility is simply θ -p + V (θ, c), and the user subscribes if and only if θ + V (θ, c) > p.

Under Assumption A we simply have

V (θ, c) = (θ-c) 2 2α 1l {θ>c} , obtained at a volume v * r (θ) = θ-c α +
, so the user subscribes if and only if

θ + (θ -c) 2 2α 1l {θ>c} > p. (2)
The left-hand side of ( 2) is strictly increasing in θ. Consequently, if a user θ subscribes, any other user with θ ≥ θ also subscribes. Additionally, the left-hand side of ( 2) is continuous, null at 0 and tending to infinity when θ → ∞, hence there exists a unique solution θ of

θ + ( θ -c) 2 2α 1l { θ>c} = p, (3)
and the set of subscribers is the set D := {θ : θ > θ}. We then have the following proposition. Proposition 1: For any price pair (p, c) the users who subscribe are those with θ > θ, where

θ = min p, c -α + α 2 + 2α[p -c] + . (4)
Proof: If c ≥ p, we immediately check that the solution to (3) is θ = p.

Alternatively, if c < p the solution to [START_REF] Hämmäinen | Flat-rate pricing for international mobile data roaming[END_REF] is in the open interval (c, p). More precisely, θ is the unique root in (c, p) of the degree-two polynomial

(X -c) 2 2α + X -p, that is, θ = c -α + α 2 + 2α(p -c).
We finally check that (4) summarizes both cases.

A. Payed roaming

We assume without loss of generality a total mass 1 of users.

The ISP has to determine the prices p and c in order to maximize its revenue. The revenue of the ISP can be written

R(p, c) = ∞ θ= θ (p + cv * r (θ))dF (θ)
where F is the distribution of θ over the population of potential subscribers, and v * r (θ) the volume of roaming usage for a typeθ user. Recall that under Assumption A we have v

* r (θ) = θ-c α + .
We end up with

R(p, c) = p(1 -F ( θ)) + c ∞ θ= θ [θ -c] + α dF (θ).
If F is exponential with rate λ, we have

R(p, c) = pe -λ θ + c α e -λ θ [ θ -c] + + c α e -λc λ e -λ[ θ-c] +
Determining the optimal revenue seems intractable analytically, but it can easily be done numerically.

B. Free roaming

We now consider the situation where the provider cannot charge for roaming usage, hence c = 0. In that case, the subscription price p can be adjusted to maximize revenue.

Proposition 2: For any subscription price p, the set of sub-

scribers is D = ( θ, ∞) = -α + α 2 + 2αp, ∞ and the revenue can be written R(p, c) = p(1-F (-α+ α 2 + 2αp)).
If F is exponential with rate λ, the revenue-maximizing p

is p = 1+ √ 1+α 2 λ 2 αλ 2
.

Proof:

The expression of θ comes directly from c = 0 in Proposition 1.

Still with c = 0, the expression of the ISP revenue can be simplified to R(p, 0) = p(1 -F (-α + α 2 + 2αp)).

For F (x) = 1 -e -λx , by differentiating with respect to p, we get a maximum when 1 -λpα/ α 2 + 2αp = 0, that is,

p = 1+ √ 1+α 2 λ 2 αλ 2 .
IV. COMPARING FREE ROAMING TO PAID ROAMING Our goal in this section is to compare the impact of optimal strategies defined in the previous section. A question we would like to answer is: What is the impact of free roaming with respect to a paid one on the ISP revenue and on users in general. Let us observe a numerical example, with an exponential distribution of rate λ of user parameters.

Figure 1 displays the optimal subscription price p in terms of λ. Without the possibility for the ISP to make extra revenue from roaming usage, the base subscription price with free roaming is larger than the one with paid roaming. As expected, when λ increases (i.e., people are less wealthy) prices decrease in both cases. Figure 2 displays the ISP revenue for both free and paid roaming in terms of λ when using the optimal prices, for α = 1. Paid roaming naturally yields larger revenues since the provider has more degrees of freedom. Now let us take a look at users, who differ through their type (the value of θ in our model). Figure 3 shows the threshold value θ, above which users subscribe and below which they do not. We observe that θ is larger for free roaming than for paid roaming, hence imposing free roaming would lead to a smaller number of subscribers. most of the revenue comes from the most wealthy users, while with free roaming all subscribers contribute at the same level to the revenues. In terms of user utility, we can distinguish three zones for θ:

• users with very low θ values do not subscribe to the service in any scenario (paid or free roaming), and are not affected by the change; • users with high θ values subscribe in both scenarios, but pay more and consume less in the paid-roaming case than in the free-roaming case, hence those users would prefer the free-roaming scenario; • between those extremes, users strictly prefer the paidroaming situation, since they benefit from a lower subscription price (which can allow them to subscribe while they would not in the free-roaming case) and have a limited roaming usage. In addition to looking at the impact of the ISP policy on each user, we can look at its impact on the population as a whole, by considering consumer surplus. Consumer surplus is defined as the aggregated net utility of users:

CS = D (θ -p + r θ (v r (θ)) -cv r (θ))dF (θ).
If p r is the revenue-maximizing subscription price in case of free roaming, and (p p , c p ) the revenue-maximizing prices in case of paid roaming, with CS r and CS p the corresponding consumers surpluses, we can simplify the formulas:

CS r = ∞ -α+ √ α 2 +2prα (θ -p r + θ 2 /(2α))dF (θ) CS p = D θ -p p + ([θ -c p ] + ) 2 2α dF (θ) = cp θ (θ -p p )dF (θ) + + ∞ max(cp, θ) θ -p p + (θ -c p ) 2 2α dF (θ)
For F exponential with rate λ, we end up with

CSr = -α+ α 2 +2 1+ √ 1+α 2 λ 2 λ 2 θ - 1 + √ 1 + α 2 λ 2 αλ 2 + θ 2 /(2α) λe -λθ dθ = e (-λ(-α+ (α 2 λ 2 +2 √ α 2 λ 2 +1+2)/λ 2 α 2 λ 2 + 2 √ α 2 λ 2 + 1 + 2 + 1 αλ 2 CSp = - e -λ θ λp -e -λ θ λ θ + e -λc cλ -e -λc λp -e -λ θ + e -λc λ + +e -λx 2αλ 2 (x -p) + c 2 λ 2 -2cλ 2 x + λ 2 x 2 + 2λ(α + x -c) + 2 2αλ 2
with x = max(c p , θ). Figure 6 displays CS for both free and paid roaming in terms of λ when using the optimal prices, for α = 1. The impact on consumer surplus leans towards free roaming: it yields higher CS than paid roaming, but the relative difference is quite small, and we may expect that there exist distributions of θ such that the CS with paid roaming exceeds that with free roaming. Hence it is not obvious that imposing free roaming would benefit users as a whole, illustrating that an analysis such as the present one is of interest.

V. CONCLUSIONS AND PERSPECTIVES

In this paper, we have proposed a model, focusing on the provider and user sides, to investigate the impact of recent UE decisions forbidding charging for data usage while roaming.

Our results suggest that imposing a switch from paid roaming to free roaming would favor the most wealthy users, and that it could be to the detriment of users with intermediate wealth. Also, the revenue extracted by the provider would be significantly lower. Since this effect on users depending on their wealth was not obvious, we consider that is it worth highlighting and that such decisions, even if intuitively beneficial for the society, should be taken with care and their implementation closely monitored.

Among the limitations of our work, we have considered a monopolistic operator. It would be interesting to investigate to what extent our conclusions remain valid in the case of several competing operators.

In future work, we also intend to study the interactions among providers of countries with significant roaming traffic from one to another.

Figure 1 .

 1 Figure 1. Revenue-maximizing subscription price, in terms of λ with α = 1

Figure 2 .

 2 Figure 2. ISP revenue in terms of λ

Figure 3 .

 3 Figure 3. Subscription threshold θ, in terms of λ: users with θ > θ subscribe to the service.

Figures 4 and 5 Figure 4 .Figure 5 .

 545 Figures 4 and 5 respectively display the total price paid (subscription plus possible roaming) and the user utility, for each type-θ user. The figures show that with paid roaming,

Figure 6 .

 6 Figure 6. Consumer surplus in terms of λ

https://ec.europa.eu/digital-single-market/en/news/ new-rules-roaming-charges-and-open-internet


Yavar Kian
email: yavar.kian@univ-amu.fr

Diomba Sambou
email: disambou@mat.uc.cl

Eric Soccorsi
email: eric.soccorsi@univ-amu.fr

Logarithmic stability inequality in an inverse source problem for the heat equation on a waveguide

Keywords: Mathematics subject classification 2010: 35R30, 35K05 Inverse problem, heat equation, time-dependent source term, stability inequality, Carleman estimate, partial boundary data

published or not. The documents may come

Logarithmic stability inequality in an inverse source

problem for the heat equation on a waveguide

Introduction

Statement and origin of the problem

Let ω ⊂ R n-1 , n ≥ 2, be open and connected, with C 4 boundary ∂ω. Set Ω := ω × R and Γ := ∂ω × R. For T ∈ (0, +∞) fixed, we consider the parabolic initial boundary value problem (IBVP)

     ∂ t u -∆u = F (t, x) in Q := (0, T ) × Ω, u(0, •) = 0 in Ω, u = 0 on Σ := (0, T ) × Γ, (1.1)
with source term F ∈ L 2 (Q). In this paper, we examine the inverse problem of determining F from a single Neumann boundary measurement of the solution u to (1.1).

Let us first notice that there is a natural obstruction to uniqueness in this problem. This can be easily understood from the identity ∂ ν u = 0 on Σ, verified by any u ∈ C ∞ 0 (Q), despite of the fact that the function F := (∂ t -∆)u may well be non uniformly zero in Q. Otherwise stated, the observation of ∂ ν u on Σ may be unchanged, whereas F is modified. To overcome this problem, different lines of research can be pursued. One of them is to extend the set of data available in such a way that F is uniquely determined by these observations. Another direction is the one of assuming that the source term F is a priori known to have the structure

F (t, x) = σ(t)β(x), (t, x) ∈ Q, (1.2)
where t → σ(t) is a known function, and then proving that ∂ ν u uniquely determines β. In this paper we investigate the second direction. Namely, we examine the stability issue in the identification of the time-independent part β of the source, from partial observation on Σ of the flux ∂ ν u induced by the solution u to (1.1).

Source terms of the form (1.2) are commonly associated with the reaction term in linear reaction diffusion equations. These equations arise naturally in various fields of application, investigating systems made of several interacting components, such as population dynamics [21], fluid dynamics [START_REF] Bear | Dynamics of fluids in porous media[END_REF], or heat conduction [START_REF] Beck | Inverse heat conductions, Ill-Posed Problems[END_REF]. More precisely, when σ(t) := e -µt , where µ a positive constant, the system (1.1)-(1.2) describes the diffusion in transmission lines or cooling pipes with significantly large length-to-diameter ratio, of decay heat, that is the heat released as a result of radioactive decay. In this particular case, (1.2) models a heat source produced by the decay of a radioactive isotope, and β is the spatial density of the isotope. From a practical viewpoint, the rate of decay µ of the isotope inducing the decay heat diffusion process, is known, and therefore the same is true for the function σ, while the density function β is generally unknown. This motivates for a closer look into the inverse problem under investigation in this article.

Existing papers: a short review

Inverse source problems have been extensively studied over the last decades. We refer to [START_REF] Isakov | Inverse source problems[END_REF] for a more general overview of this topic than the one presented in this section, where we solely focus on parabolic inverse source problems consisting in determining a source term by boundary measurements of the solution to a parabolic equation. The uniqueness issue for this problem was investigated in [START_REF] Cannon | Determination of an unknown heat source from overspecified boundary data[END_REF], and conditional stability was derived in [START_REF] Choulli | Some stability estimates in determining sources and coefficients[END_REF][START_REF] Yamamoto | Conditional stability in the determination of force terms of heat equations in a rectangle[END_REF][START_REF] Yamamoto | Conditional stability in the determination of densities of heat sources in a bounded domain, Estimation and Control of Distributed Parameter Systems[END_REF]. In [START_REF] Yu | Lipschitz stability in inverse parabolic problems by the Carleman estimate[END_REF], inspired by the Bukhgeim-Klibanov approach introduced in [START_REF] Bukhgeim | Global uniqueness of a class of multidimensional inverse problem[END_REF], Imanuvilov and Yamamoto proved Lipschitz stability of the source with respect to one Neumann boundary measurement of the solution to a parabolic equation with non-degenerate initial data, and partial Dirichlet data supported on arbitrary subregions of the boundary. In [START_REF] Choulli | Some stability estimates in determining sources and coefficients[END_REF], Choulli and Yamamoto established a log-type stability estimate for the time-independent source term β, appearing in (1.2), by a single Neumann observation of the solution on an arbitrary sub-boundary.

All the above mentioned results are stated in a bounded spatial domain. But, to the best of our knowledge, there is no result available in the mathematical literature, dealing with the recovery of a non-compactly supported unknown source function, appearing in a parabolic equation, by boundary measurements of the solution. This is the starting point of this paper, in the sense that we aim for extending the stability result of [START_REF] Choulli | Some stability estimates in determining sources and coefficients[END_REF], which is valid in bounded spatial domains only, to the framework of infinite cylindrical domains.

The forward problem

Prior to describing the main achievement of this paper in section 1.4, we briefly investigate the well-posedness of the IBVP(1.1). Actually, we start by examining the forward problem associated with the IBVP

     ∂ t v -∆v = f in Q, v(0, •) = v 0 in Ω, v = 0 on Σ, (1.3)
for suitable source term f and initial data v 0 . More precisely, we seek an existence, uniqueness and (improved) regularity result for the solution to the above system, as well as a suitable energy estimate. Such results are rather classical in the case of bounded spatial domains, but it turns out that they are not so well-documented for unbounded domains such as Ω. Therefore, for the sake of completeness, we shall establish Theorem 1.1, presented below.

As a preliminary, we recall for all s ∈ (0, +∞), that the Sobolev space

H s (Ω) := L 2 (R; H s (ω)) ∩ H s (R; L 2 (ω))
is endowed with the norm

u 2 H s (Ω) := u 2 L 2 (R;H s (ω)) + u 2 H s (R;L 2 (ω)) ,
and then remind from [22, Section 4.2.1] that

H r,s (Q) := L 2 0, T ; H r (Ω)) ∩ H s (0, T ; L 2 (Ω)), r ∈ (0, +∞).
Having said that, we may now state the following forward result associated with (1.3).

Theorem 1.1 Let v 0 ∈ H 1 0 (Ω) and f ∈ L 2 (0, T ; H 1 0 (Ω)). Then, there exists a unique solution v ∈ H 2,1 (Q) ∩ C([0, T ]; H 1 0 (Ω)) to the IBVP (1.3), such that v(t) H 1 (Ω) ≤ v 0 H 1 (Ω) + f L 2 (0,T ;H 1 (Ω)) , t ∈ [0, T ]. (1.4)
As will be seen in the sequel, Theorem 1.1 is a crucial step in the derivation of the observability inequality presented in Section 4.1, which is a cornerstone in the analysis of the inverse problem under investigation. But, just as important is the following consequence of Theorem 1.1, which enables us to define properly the boundary data used by the identification of the unknown function β in Theorem 1.2, below.

Corollary 1.1 Let F be defined by (1.2), where σ ∈ C 1 ([0, T ]) and β ∈ H 1 0 (Ω). Then, the IBVP (1.3) admits a unique solution u ∈ H 2,1 (Q). Moreover, we have ∂ t u ∈ H 2,1 (Q) ∩ C([0, T ]; H 1 0 (Ω))
, and the following estimate holds:

∂ t u(t) H 1 (Ω) ≤ (1 + T 1/2 ) σ C 1 ([0,T ]) β H 1 (Ω) , t ∈ [0, T ].
(1.5)

The proofs of Theorem 1.1 and Corollary 1.1 are presented in Section 2.

Main result

For M ∈ (0, +∞) fixed, we introduce the set of admissible unknown source functions, as

B(M ) := ϕ ∈ H 1 0 (Ω); ϕ H 1 (Ω) ≤ M . (1.6)
Then, the main result of this article can be stated as follows.

Theorem 1.2 Put γ := γ × R, where γ is an arbitary closed subset of the boundary ∂ω, with non empty interior, and let σ ∈ C 1 ([0, T ]) satisfy σ(0) = 0. For M ∈ (0, +∞), pick β ∈ B(M ), and let u be the H 2,1 (Q)-solution to the IBVP (1.1), associated with

F (t, x) = σ(t)β(x), (t, x) ∈ Q,
which is given by Corollary 1.1. Then, there exists a constant C > 0, depending only on ω, σ, T , M and γ , such that the estimate

β L 2 (Ω) ≤ CΦ ∂ ν u H 1 (0,T ;L 2 (γ)) , (1.7)
holds with

Φ(r) := r 1/2 + | ln r| -1/2 if r ∈ (0, +∞) 0 if r = 0. (1.8)
Notice that we have u ∈ H 1 (0, T ; H 2 (Ω)) from Corollary 1.1, which guarantees that the trace ∂ ν u appearing in the right hand side of the stability estimate (1.8) is well-defined in H 1 (0, T ; L 2 (γ)).

To the best of our knowledge, Theorem 1.2 is the first stability result in the identification of the non-compactly supported source term β, appearing in a parabolic equation, by a single partial boundary observation of the solution. A similar statement was actually derived in [START_REF] Choulli | Some stability estimates in determining sources and coefficients[END_REF]Theorem 2.2] (see also [START_REF] Choulli | Une introduction aux problèmes inverses elliptiques et paraboliques[END_REF]Theorem 3.4]) when the domain Ω is bounded, so Theorem 1.2 extends this result to the case of infinite cylindrical domains.

Notice that the statement of Theorem 1.2 is valid in absence of any assumption on the behavior of the source term β outside a compact subset of the infinite cylindrical domain Ω = ω×R. Another remarkable feature of the result of Theorem 1.2 is that the logarithmic dependency of the spacevarying source term, with respect to the boundary data, manifested in [11, Theorem 2.2] for a bounded domain, is preserved by the stability estimate (1.7). Otherwise stated, the stability of the reconstruction of β by a single boundary observation of the solution, is not affected by the infinite extension of the support of the unknown coefficient. This phenomenon is in sharp contrast with the one observed for the determination of the electric potential appearing in the Schrödinger equation, by a finite number of Neuman data, where Lipschitz stability (see [1, Theorem 1] and [2, Theorem 1]) degenerates to Hölder (see [START_REF] Kian | Hölder stable determination of a quantum scalar potential in unbounded cylindrical domains[END_REF]Theorem 1.4]), as the support of the unknown potential becomes infinite.

The proof of Theorem 1.2 is by means of a Carleman inequality specifically designed for the heat operator in the unbounded cylindrical domain Ω. The derivation of this estimate is inspired by the approach used in this particular framework by [START_REF] Bellassoued | An inverse stability result for non compactly supported potentials by one arbitrary lateral Neumann observation[END_REF][START_REF] Kian | Carleman estimate for infinite cylindrical quantum domains and application to inverse problems[END_REF][START_REF] Kian | Hölder stable determination of a quantum scalar potential in unbounded cylindrical domains[END_REF] for the Schrödinger equation.

Outline

The paper is organized as follows. In Section 2, we establish Theorem 1.1 and Corollary 1.1. In Section 3, we derive a Carleman estimate for the heat operator in Ω, which is the main tool for the proof of the observability inequality presented in Section 4.1. Finally, Section 4 contains the proof of Theorem 1.2, which is by means of the above mentioned observability inequality.

Analysis of the forward problem

Proof of Theorem 1.1

Let A be the Dirichlet Laplacian in L 2 (Ω), i.e. the self-adjoint operator generated in L 2 (Ω) by the closed quadratic form

a(ϕ) := Ω |∇ϕ| 2 dx, ϕ ∈ D(a) := H 1 0 (Ω).
Evidently, A acts as -∆ on its domain

D(A) := {ϕ ∈ H 1 0 (Ω), ∆ϕ ∈ L 2 (Ω)}, so we may rewrite the IBVP (1.3) into the following Cauchy problem v + Av = f in (0, T ), v(0) = v 0 . (2.1)
Further, since ω is bounded, then there exists a positive constant c(ω), depending only on ω, such that the Poincaré inequality holds:

a(ϕ) ≥ c(ω) ϕ 2 L 2 (Ω) , ϕ ∈ H 1 0 (Ω).
As a consequence, we have A ≥ c(ω) in the operator sense, and A + p is thus boundedly invertible in L 2 (Ω) for all p ∈ C \ (0, +∞), with

(A + p) -1 B(L 2 (Ω)) ≤ √ 2 max(1, c(ω) -1 ) 1 + |p| , p ∈ C, Re p ≥ 0. Moreover, as v 0 ∈ H 1 0 (Ω) = D(a) = D(A 1/2 ) and f ∈ L 2 (Q), then we derive from [22, Section 4, Theorem 3.2] that (2.1) admits a unique solution v ∈ L 2 (0, T ; D(A)) ∩ H 1 (0, T ; L 2 (Ω)).
From this and the identity

D(A) = H 2 (Ω) ∩ H 1 0 (Ω), arising from [12, Lemma 2.2], it then follows that v ∈ H 2,1 (Q).
The last step of the proof is to show that v ∈ C([0, T ]; H 1 0 (Ω)) satisfies (1.4). Bearing in mind that A is the infinitesimal generator of a contraction semi-group of class C 0 in L 2 (Ω) (see e.g. [13, Section XVII.A.3, Theorem 2]), this can be done with the aid of Duhamel's formula, giving

v(t) = e -tA v 0 + t 0 e -(t-s)A f (s) ds, t ∈ [0, T ].
(2.2)

Indeed, since v 0 ∈ D(A 1/2
) and e -tA commutes with A 1/2 for all t ∈ [0, T ], then we have e -tA v 0 ∈ D(A 1/2 ) and A 1/2 e -tA v 0 = e -tA A 1/2 v 0 , which entails

t → e -tA v 0 ∈ C([0, T ]; D(A 1/2 )) = C([0, T ]; H 1 0 (Ω)). (2.3)
Furthermore, for all t ∈ [0, T ], we infer from the basic identity

e -tA v 0 2 H 1 (Ω) = e -tA v 0 2 L 2 (Ω) + A 1/2 e -tA v 0 2 L 2 (Ω) , that e -tA v 0 2 H 1 (Ω) = e -tA v 0 2 L 2 (Ω) + e -tA A 1/2 v 0 2 L 2 (Ω) ≤ v 0 2 L 2 (Ω) + A 1/2 v 0 2 L 2 (Ω) ≤ v 0 2 H 1 (Ω) . (2.4)
Here, we used the fact that the operator e -tA is linear bounded in L 2 (Ω) for all t ∈ [0, T ], with e -tA B(L 2 (Ω)) ≤ e -tc(ω) ≤ 1. Similarly, since f (s) ∈ D(A 1/2 ) for a.e. s ∈ (0, T ), we get

t → t 0 e -(t-s)A f (s) ds ∈ C([0, T ]; H 1 0 (Ω)), (2.5)
by arguing as before. Next, taking into account that

t 0 e -(t-s)A f (s) ds 2 H 1 (Ω) = t 0 e -(t-s)A f (s) ds 2 L 2 (Ω) + A 1/2 t 0 e -(t-s)A f (s) ds 2 L 2 (Ω) = t 0 e -(t-s)A f (s) ds 2 L 2 (Ω) + t 0 e -(t-s)A A 1/2 f (s) ds 2 L 2 (Ω)
,

for every t ∈ [0, T ], we obtain t 0 e -(t-s)A f (s) ds 2 H 1 (Ω) ≤ T t 0 e -(t-s)A f (s) 2 L 2 (Ω) + e -(t-s)A A 1/2 f (s) 2 L 2 (Ω) ds ≤ T t 0 f (s) 2 L 2 (Ω) + A 1/2 f (s) 2 L 2 (Ω) ds ≤ T f 2 L 2 (0,T ;H 1 (Ω)) . (2.6)
Finally, putting (2.2), (2.3) and (2.5) together, we find that v ∈ C([0, T ]; H 1 0 (Ω)), and (1.4) follows readily from (2.2), (2.4) and (2.6).

Proof of Corollary 1.1

Since F ∈ L 2 (0, T ; H1 0 (Ω)) and the initial data of the IBVP (1.1) is zero everywhere, then there exists a unique solution u ∈ H 2,1 (Q) to (1.1), according to Theorem 1.1. Moreover, differentiating (1.1) with respect to t, we obtain that ∂ t u is solution to the system (1.3), associated with

f (t, x) = σ (t)β(x) ∈ L 2 (0, T ; H 1 0 (Ω)) and v 0 := σ(0)β ∈ H 1 0 (Ω). Therefore, we have ∂ t u ∈ H 2,1 (Q) ∩ C([0, T ]; H 1 0 (Ω))
, from Theorem 1.1, and the estimate (1.4) yields

∂ t u(t) H 1 (Ω) ≤ |σ(0)| β H 1 (Ω) + σ (t)β(x) L 2 (0,T ;H 1 (Ω)) ≤ |σ(0)| + T 1/2 σ C 0 ([0,T ]) β H 1 (Ω) ,
for all t ∈ [0, T ]. This leads to (1.5).

A parabolic Carleman inequality in unbounded cylindrical domains

In this section we establish a Carleman estimate, stated in Theorem 3.1, for the heat operator (c.ii) ∃α 0 > 0 such that |∇ ψ 0 (x )| ≥ α 0 for all x ∈ ω;

P u := (∂ t -∆)u, u ∈ C([0, T ]; H 1 0 (Ω)) ∩ H 2,1 (Q). ( 3
(c.iii) ∂ ν ψ 0 (x ) ≤ 0 for all x ∈ ∂ω\γ .
Here, ∇ denotes the gradient with respect to x = (x 1 , . . . ,

x n-1 ) ∈ R n-1 , i.e. ∇ f := (∂ x1 f, . . . , ∂ xn-1 f ),
and ∂ ν is the normal derivative with respect to ∂ω, that is ∂ ν := ν • ∇ , where ν stands for the outward normal vector to ∂ω.

Thus, putting ψ(x) = ψ(x , x n ) := ψ 0 (x ) for all x = (x , x n ) ∈ Ω, it is apparent that the function ψ ∈ C 4 (Ω) ∩ W 4,∞ (Ω) satisfies the three following conditions: (C.i) inf x∈Ω ψ(x) > 0; (C.ii) |∇ψ(x)| ≥ α 0 > 0 for all x ∈ Ω; (C.iii) ∂ ν ψ(x) ≤ 0 for all x ∈ Γ\γ.
Here and henceforth, the notation ν stands for the outward unit normal vector to the boundary Γ, and ∂ ν := ν • ∇. Evidently, ν = (ν , 0), so we have ∂ ν ψ = ∂ ν ψ 0 , as the function ψ does not depend on the longitudinal variable x n .

Next, for each ρ ∈ (0, +∞), we introduce the following weight function

Φ ρ (t, x) = Φ ρ (t, x ) := g(t) e ρψ(x ) -e 2ρ ψ L ∞ (Ω) with g(t) := 1 t(T -t) , (t, x) ∈ Q, (3.2)
and, for further use, we gather in the coming lemma several useful properties of Φ ρ .

Lemma 3.1 There exists a constant ρ 0 ∈ (0, +∞), depending only on ψ, such that for all ρ ∈ [ρ 0 , +∞), the following statements hold uniformly in Q:

(a) |∇Φ ρ | ≥ α := 4ρ0α0 T 2 > 0; (b) ∇|∇Φ ρ | 2 • ∇Φ ρ ≥ C 0 ρ|∇Φ ρ | 3 ; (c) H(Φ ρ )ξ • ξ + C 1 ρ|∇Φ ρ ||ξ| 2 ≥ 0, ξ ∈ R n-1 × R; (d) |∂ t |∇Φ ρ | 2 | + |∆ 2 Φ ρ | + |∆|∇Φ ρ || + ρ -1 (∆Φ ρ ) 2 ≤ C 2 |∇Φ ρ | 3 ; (e) |∂ 2 t Φ ρ | + |∇Φ ρ | -1 (∂ t Φ ρ ) 2 ≤ C 3 λ |∇Φ ρ | 3 , λ ≥ λ 0 (ρ) := e 4ρ ψ L ∞ (Ω) .
Here, C j , j = 0, 1, 2, 3, are positive constants depending only on T , ψ and α 0 , and H(Φ ρ ) denotes the Hessian matrix of Φ ρ with respect to x ∈ Ω.

The proof of Lemma 3.1 is postponed to Section 3.3. Now, with reference to (3.2), we may state the Carleman estimate for the operator P , as follows.

Theorem 3.1 Let u ∈ H 2,1 (Q) ∩ C([0, T ]; H 1 0 (Ω)
) be real valued. Then, there exists ρ 0 ∈ (0, +∞), such that for all ρ ∈ [ρ 0 , +∞), there is λ 0 = λ 0 (ρ) ∈ (0, +∞), depending only α 0 , ω, γ , T and ρ, such that the estimate

e λΦρ (λg) -1/2 ∆u L 2 (Q) + e λΦρ (λg) -1/2 ∂ t u L 2 (Q) + e λΦρ (λg) 1/2 |∇u| L 2 (Q) + e λΦρ (λg) 3 2 u L 2 (Q) ≤ C e λΦρ P u L 2 (Q) + e λΦρ (λg) 1/2 ∂ ν u L 2 ((0,T )×γ) , (3.3)
holds for all λ ∈ [λ 0 , +∞) and some positive constant C, which depends only on α 0 , ω, γ , T , ρ and λ 0 .

We point out that it is actually possible to adapt the Carleman inequality of Theorem 3.1 to more general differential operators of the form ∂ t -∆ + A(t, x) • ∇ + q(t, x), with A ∈ L ∞ (Q) n and q ∈ L ∞ (Q). Nevertheless, as will appear in Section 4 below, such an estimate is not needed by the analysis of the inverse source problem carried out in this paper. Therefore, in order to avoid the inadequate expense of the size of this paper, we shall not go further into the matter.

Proof of Theorem 3.1

The proof of Theorem 3.1 is inspired by the ones of [8, Lemma 1.2], [14, Lemma 5.2] and [START_REF] Choulli | Une introduction aux problèmes inverses elliptiques et paraboliques[END_REF]Theorem 3.4]. For the sake of notational simplicity, we shall systematically omit the variables t ∈ (0, T ) and x ∈ Ω, in front of the various functions appearing in this section.

Let ρ and λ be fixed in (0, +∞). We set v := e λΦρ u, in such a way that 2 dxdt with L λ := e λΦρ P e -λΦρ , and we split L λ into the sum

Q e 2λΦρ (P u) 2 dxdt = Q (L λ v)
L λ = L + λ + L - λ , where L + λ := -∆ -λ∂ t Φ ρ -λ 2 |∇Φ ρ | 2 and L - λ := ∂ t + 2λ∇Φ ρ • ∇ + λ∆Φ ρ . (3.4)
a) The first step of the proof is to show that the estimate

Q (L + λ v)L - λ vdxdt + λ (0,T )×γ |∂ ν Φ ρ |(∂ ν v) 2 dσdt ≥ C 0 λ 3 ρ Q |∇Φ ρ | 3 v 2 dxdt -2C 1 λρ Q |∇Φ ρ ||∇v| 2 dxdt + R 0 , (3.5)
holds uniformly in ρ ∈ [ρ 0 , +∞), with

R 0 := λ 2 Q (∂ t |∇Φ ρ | 2 )v 2 dxdt + λ 2 Q ∂ 2 t Φ ρ -∆ 2 Φ ρ v 2 dxdt, (3.6)
where ρ 0 and the two constants C 0 and C 1 are the same as in Lemma 3.1. This can be done with the aid of (3.4), involving

(L + λ v)L - λ v = -(∆v)∂ t v -2λ(∆v)∇Φ ρ • ∇v -λ(∆v)(∆Φ ρ )v -λ(∂ t Φ ρ )v∂ t v -2λ 2 (∂ t Φ ρ )(∇Φ ρ • ∇v)v -λ 2 (∂ t Φ ρ )(∆Φ ρ )v 2 -λ 2 |∇Φ ρ | 2 v∂ t v -2λ 3 |∇Φ ρ | 2 (∇Φ ρ • ∇v)v -λ 3 |∇Φ ρ | 2 (∆Φ ρ )v 2 , (3.7)
through standard computations, and by integrating separately each term appearing in the right hand side of (3.7), with respect to (t, x) over Q.

The first term is easily treated with an integration by parts. Taking into account that v vanishes on Σ and in {0, T } × Ω, we find that

- Q (∆v)∂ t v dxdt = 1 2 Q ∂ t |∇v| 2 dxdt = 0. (3.8)
To examine the second term, we write

∇(∇Φ ρ • ∇v) = H(Φ ρ )∇v + H(v)∇Φ ρ ,
where, in accordance with the notation introduced in Lemma 3.1, H(v) stands for the Hessian matrix of v, with respect to x ∈ Ω, and integrate by parts, getting:

- Q (∆v)∇Φ ρ • ∇v dxdt = Q ∇v • ∇(∇Φ ρ • ∇v) dxdt - Σ (∂ ν v)∇Φ ρ • ∇v dσdt = Q H(Φ ρ )∇v • ∇v dxdt + Q H(v)∇Φ ρ • ∇v dxdt - Σ (∂ ν Φ ρ )(∂ ν v) 2 dσdt. (3.9)
In the last integral, we used the fact, arising from the identity v |Σ = 0, that ∇v = (∂ ν v)ν on Σ, or equivalently, that the tangential derivative of v vanishes on Σ. Moreover, as we have

Q H(v)∇Φ ρ • ∇v dxdt = 1 2 Q ∇Φ ρ • ∇(|∇v| 2 ) dxdt = - 1 2 Q (∆Φ ρ )|∇v| 2 dxdt + 1 2 Σ (∂ ν Φ ρ )|∇v| 2 dσdt = - 1 2 Q (∆Φ ρ )|∇v| 2 dxdt + 1 2 Σ (∂ ν Φ ρ )(∂ ν v) 2 dσdt,
then we infer from (3.9) that

-2λ Q (∆v)∇Φ ρ • ∇v dxdt = 2λ Q H(Φ ρ )|∇v| 2 dxdt -λ Q (∆Φ ρ )|∇v| 2 dxdt -λ Σ (∂ ν Φ ρ )(∂ ν v) 2 dσdt. (3.10)
As for the third term entering the right hand side of (3.7), we obtain

-λ Q (∆v)(∆Φ ρ )v dxdt = λ Q ∇v • ∇ (∆Φ ρ )v dxdt = λ 2 Q ∇(∆Φ ρ ) • ∇v 2 dxdt + λ Q (∆Φ ρ )|∇v| 2 dxdt = - λ 2 Q (∆ 2 Φ ρ )v 2 dxdt + λ Q (∆Φ ρ )|∇v| 2 dxdt, (3.11)
by integrating by parts once more. Next, we find that the fourth term reads

-λ Q (∂ t Φ ρ )v∂ t v dxdt = - λ 2 Q (∂ t Φ ρ )∂ t v 2 dxdt = λ 2 Q (∂ 2 t Φ ρ )v 2 dxdt, (3.12)
while the fifth one can be brought into the form

-2λ 2 Q (∂ t Φ ρ )v∇Φ ρ • ∇v dxdt = -λ 2 Q (∂ t Φ ρ )∇Φ ρ • ∇v 2 dxdt. (3.13)
Quite similarly, the sixth and seventh terms may be rewritten as, respectively,

-λ 2 Q (∆Φ ρ )(∂ t Φ ρ )v 2 dxdt = λ 2 Q ∇Φ ρ • ∇ (∂ t Φ ρ )v 2 dxdt (3.14) = λ 2 Q (∂ t Φ ρ )∇Φ ρ • ∇v 2 dxdt + λ 2 2 Q ∂ t |∇Φ ρ | 2 v 2 dxdt, and
-λ 2 Q |∇Φ ρ | 2 v∂ t v dxdt = - λ 2 2 Q |∇Φ ρ | 2 ∂ t v 2 dxdt = λ 2 2 Q ∂ t |∇Φ ρ | 2 v 2 dxdt. (3.15)
Finally, the two last terms in the right hand side of (3.7), are re-expressed as

-2λ 3 Q |∇Φ ρ | 2 (∇Φ ρ • ∇v)v dxdt = -λ 3 Q |∇Φ ρ | 2 ∇Φ ρ • ∇v 2 dxdt, (3.16)
and

-λ 3 Q (∆Φ ρ )|∇Φ ρ | 2 v 2 dxdt = λ 3 Q ∇Φ ρ • ∇ |∇Φ ρ | 2 v 2 dxdt (3.17) = λ 3 Q ∇|∇Φ ρ | 2 • ∇Φ ρ v 2 dxdt + λ 3 Q |∇Φ ρ | 2 ∇Φ ρ • ∇v 2 dxdt.
Thus, putting (3.7)-(3.17) together, we obtain that

Q (L + λ v)L - λ v dxdt + λ Σ (∂ ν Φ ρ )(∂ ν v) 2 dσdt = λ 3 Q (∇|∇Φ ρ | 2 • ∇Φ ρ v 2 dxdt + 2λ Q H(Φ ρ )|∇v| 2 dxdt + λ 2 Q ∂ 2 t Φ ρ -∆ 2 Φ ρ v 2 dxdt + λ 2 Q ∂ t |∇Φ ρ | 2 v 2 dxdt.
With reference to Points (b) and (c) in Lemma 3.1, this entails for all ρ ∈ [ρ 0 , +∞), that

Q (L + λ v)L - λ v dxdt + λ Σ (∂ ν Φ ρ )(∂ ν v) 2 dσdt ≥ C 0 λ 3 ρ Q |∇Φ ρ | 3 v 2 dxdt -2C 1 λρ Q |∇Φ ρ | 2 |∇v| 2 dxdt + R 0 ,
where R 0 is given by (3.6). Finally, (3.5) follows immediately from (C.iii) and the above estimate.

b) Further, remembering (3.4), we see that

∆v = -L + λ v -λ 2 |∇Φ ρ | 2 v -λ(∂ t Φ ρ )v, whence (∆v) 2 ≤ 3 (L + λ v) 2 + λ 4 |∇Φ ρ | 4 v 2 + λ 2 (∂ t Φ ρ ) 2 v 2 . (3.18)
Next, with reference to Point (a) in Lemma 3.1, we derive from (3.18) that

λ|∇Φ ρ | -1 (∆v) 2 ≤ 3 αλ (L + λ v) 2 + 3λ 3 |∇Φ ρ | 3 v 2 + 3λ|∇Φ ρ | -1 (∂ t Φ ρ ) 2 v 2 , (3.19)
for all ρ ∈ [ρ 0 , +∞). This entails that

Q λ|∇Φ ρ | -1 (∆v) 2 dxdt ≤ 3 αλ Q (L + λ v) 2 dxdt + 3 Q λ|∇Φ ρ | 3 v 2 dxdt + R 1 , (3.20)
with

R 1 := 3λ Q |∇Φ ρ | -1 (∂ t Φ ρ ) 2 v 2 dxdt. (3.21)
Further, taking into account that v |Σ = 0, we get

Q |∇Φ ρ ||∇v| 2 dxdt = - Q |∇Φ ρ |v∆v dxdt + 1 2 Q ∆|∇Φ ρ | v 2 dxdt,
upon integrating by parts. This and the estimate,

ρ 3/2 λ|∇Φ ρ ||v∆v| = λ|∇Φ ρ | -1/2 |∆v| ρ 3/2 λ|∇Φ ρ | 3 2 |v| ≤ 1 2 λ|∇Φ ρ | -1 (∆v) 2 + ρ 3 2 λ|∇Φ ρ | 3 v 2 , yield ρ 3/2 λ Q |∇Φ ρ ||∇v| 2 dxdt ≤ 1 2 Q λ|∇Φ ρ | -1 (∆v) 2 dxdt + ρ 3 2 Q λ|∇Φ ρ | 3 v 2 dxdt + ρ 3/2 2 λ Q ∆|∇Φ ρ | v 2 dxdt.
From this and (3.20)-(3.21), it then follows that

ρ 3/2 λ Q |∇Φ ρ ||∇v| 2 dxdt + 1 2 Q λ|∇Φ ρ | -1 (∆v) 2 dxdt ≤ 3 αλ Q (L + λ v) 2 dxdt + 3 + ρ 3 2 Q λ|∇Φ ρ | 3 v 2 dxdt + R 2 , with R 2 := R 1 + ρ 3/2 2 λ Q ∆|∇Φ ρ | v 2 dxdt. (3.22)
Therefore, by substituting max(ρ 0 , 6 1/3 ) for ρ 0 , we obtain for all ρ ∈ [ρ 0 , +∞), that

ρ 1/2 λ Q |∇Φ ρ ||∇v| 2 dxdt + 1 2 Q λ|∇Φ ρ | -1 (∆v) 2 dxdt ≤ 3 αλ Q (L + λ v) 2 dxdt + ρ 3 Q λ|∇Φ ρ | 3 v 2 dxdt + R 2 .
Putting this together with (3.5), we find

3 αλ Q (L + λ v) 2 dxdt + 2 C 0 Q (L + λ v)L - λ v dxdt + 2λ C 0 γ×(0,T ) |∂ ν Φ ρ |(∂ ν v) 2 dσdt ≥ ρ 1/2 - 4C 1 C 0 ρλ Q |∇Φ ρ ||∇v| 2 dxdt + ρ Q λ|∇Φ ρ | 3 v 2 dxdt + 1 2 Q λ|∇Φ ρ | -1 (∆v) 2 dxdt + R 3 , (3.23) with R 3 := 2R 0 C 0 -R 2 . (3.24)
Then, upon possibly enlarging ρ 0 , in such a way that ρ 1/2 0 -4(C 1 /C 0 ) is lower bounded by a positive constant C 2 , we infer from (3.23), that for all ρ ∈ [ρ 0 , +∞),

3 αλ Q (L + λ v) 2 dxdt + 2 C 0 Q (L + λ v)L - λ v dxdt + 2λ C 0 γ×(0,T ) |∂ ν Φ ρ |(∂ ν v) 2 dσdt ≥ C 2 λ Q |∇Φ ρ ||∇v| 2 dxdt + ρ Q λ|∇Φ ρ | 3 v 2 dxdt + 1 2 Q λ|∇Φ ρ | -1 (∆v) 2 dxdt + R 3 . (3.25) c) Further, since ∂ t v = L - λ v -2λ∇Φ ρ • ∇v -λ(∆Φ ρ )v, by (3.4)
, we find upon arguing as in the derivation (3.19), that

λ|∇Φ ρ | -1 (∂ t v) 2 ≤ 3 αλ (L - λ v) 2 + 12λ|∇Φ ρ ||∇v| 2 + 3λ α (∆Φ ρ ) 2 v 2 ,
which immediately entails

Q λ|∇Φ ρ | -1 (∂ t v) 2 dxdt ≤ 3 αλ Q (L - λ v) 2 dxdt + 12 α λ Q |∇Φ ρ ||∇v| 2 dxdt + R 4 , (3.26)
with

R 4 := 3λ α Q (∆Φ ρ ) 2 v 2 dxdt. (3.27)
Putting (3.25) together with (3.26), we see that

3 αλ Q (L + λ v) 2 dxdt + 2 C 0 Q (L + λ v)L - λ v dxdt + C 2 8αλ Q (L - λ v) 2 dxdt + 2λ C 0 γ×(0,T ) |∂ ν Φ ρ |(∂ ν v) 2 dσdt ≥ C 2 24 Q (λ|∇Φ ρ |) -1 (∂ t v) 2 dxdt + 1 2 Q (λ|∇Φ ρ |) -1 (∆v) 2 dxdt + C 2 λ 2 Q |∇Φ ρ ||∇v| 2 dxdt +ρ Q (λ|∇Φ ρ |) 3 v 2 dxdt + R 5 ,
where we have set

R 5 := R 3 - C 2 24 R 4 . (3.28)
Therefore, bearing in mind that

L λ = L + λ + L - λ , we get that 1 C 0 Q (L λ v) 2 dxdt + 2λ γ×(0,T ) |∂ ν Φ ρ |(∂ ν v) 2 dσdt ≥ C 2 24 Q (λ|∇Φ ρ |) -1 (∂ t v) 2 dxdt + 1 2 Q (λ|∇Φ ρ |) -1 (∆v) 2 dxdt + C 2 λ 2 Q |∇Φ ρ ||∇v| 2 dxdt + ρ Q (λ|∇Φ ρ |) 3 v 2 dxdt + R 5 , (3.29)
provided λ ∈ [C 0 (3 + C 2 )α -1 , +∞).
d) Without restricting the generality of the reasoning, we may assume in the sequel (upon possibly substituting

C 0 (3 + C 2 )α -1 for λ 0 (ρ)) that λ 0 (ρ) ∈ [C 0 (3 + C 2 )α -1 , +∞).
ρ ∈ [ρ 0 , +∞) and λ ∈ [λ 0 (ρ), +∞), that |R 5 | is majorized by ρλ 2 Q |∇Φ ρ | 3 v 2 dxdt,
up to some positive multiplicative constant, which is independent of ρ and λ. Therefore, upon possibly enlarging ρ 0 , we obtain that

|R 5 | ≤ ρ 2 Q (λ|∇Φ ρ |) 3 v 2 dxdt, ρ ∈ [ρ 0 , +∞), λ ∈ [λ 0 (ρ), +∞).
This and (3.29) yield

1 C 0 Q (L λ v) 2 dxdt + 2λ γ×(0,T ) |∂ ν Φ ρ |(∂ ν v) 2 dσdt ≥ C 2 24 Q (λ|∇Φ ρ |) -1 (∂ t v) 2 dxdt + 1 2 Q (λ|∇Φ ρ |) -1 (∆v) 2 dxdt + C 2 λ 2 Q |∇Φ ρ ||∇v| 2 dxdt + ρ 2 Q (λ|∇Φ ρ |) 3 v 2 dxdt, (3.30)
provided ρ ∈ [ρ 0 , +∞) and λ ∈ [λ 0 (ρ), +∞). Next, since v = e λΦρ u, then it holds true that e 2λΦρ |∇u| 2 ≤ 2 |∇v| 2 + λ 2 |∇Φ ρ | 2 v 2
, and it ensues from (3.30) and Point (a) in Lemma 3.1, that

1 C 0 Q (L λ v) 2 dxdt + 2λ γ×(0,T ) |∂ ν Φ ρ |(∂ ν v) 2 dσdt ≥ C 2 24 Q (λ|∇Φ ρ |) -1 (∂ t v) 2 dxdt + 1 2 Q (λ|∇Φ ρ |) -1 (∆v) 2 dxdt + C 2 λ 4 Q e 2λΦρ |∇Φ ρ ||∇u| 2 dxdt + λ 3 2 (ρ -C 2 α -1 ) Q |∇Φ ρ | 3 v 2 dxdt.
Thus, upon possibly substituting C 2 α -1 + 1 for ρ 0 , we immediately get for all ρ ∈ [ρ 0 , +∞) and λ ∈ [λ 0 (ρ), +∞), that

1 C 0 Q (L λ v) 2 dxdt + 2λ γ×(0,T ) |∂ ν Φ ρ |(∂ ν v) 2 dσdt ≥ C 2 24 Q (λ|∇Φ ρ |) -1 (∂ t v) 2 dxdt + 1 2 Q (λ|∇Φ ρ |) -1 (∆v) 2 dxdt + C 2 λ 4 Q e 2λΦρ |∇Φ ρ ||∇u| 2 dxdt + λ 3 2 Q |∇Φ ρ | 3 v 2 dxdt. (3.31)
Further, due to (3.2) and (C.ii), we have

|∂ ν Φ ρ | ≤ C 4 g and |∇Φ ρ | i ≥ C 5 g i for i ∈ {-1, 1, 3}, in Q,
where the two constants C 4 and C 5 depend only on ρ, ψ and α 0 . Therefore, for all ρ ∈ [ρ 0 , +∞) and λ ∈ [λ 0 (ρ), +∞), we deduce from (3.31) the existence of a positive constant C 6 , depending only on ρ, T , ψ and α 0 , such that

Q (L λ v) 2 dxdt + γ×(0,T ) (λg)(∂ ν v) 2 dσdt ≥ C 6 Q (λg) -1 (∂ t v) 2 dxdt + Q (λg) -1 (∆v) 2 dxdt + Q e 2λΦρ (λg)|∇u| 2 dxdt + Q (λg) 3 v 2 dxdt .
Finally, (3.3) follows immediately from this upon remebering that v = e λΦρ u, v |Σ = 0 and (L λ v) 2 = e 2λΦρ (P u) 2 .

Proof of Lemma 3.1

As in Section 3.2, we systematically omit the variables t ∈ (0, T ) and x ∈ Ω in front of the functions g, ψ or Φ ρ , and their derivatives, in this proof.

∇|∇Φ ρ | 2 • ∇Φ ρ = 2|∇Φ ρ |∇|∇Φ ρ | • ∇Φ ρ = 2 ρ|∇Φ ρ | 3 |∇ψ| + |∇Φ ρ | 2 ∇|∇ψ| • ∇Φ ρ |∇ψ| . ( 3
∇|∇Φ ρ | 2 • ∇Φ ρ ≥ 2ρα 0 1 - C ρα 2 0 |∇Φ ρ | 3 ,
and the estimate (b) follows readily from this upon taking ρ 0 ∈ [2α 2 0 , +∞). c) For all natural numbers i and j in {1, 2, . . . , n}, we get that

∂ xi ∂ xj Φ ρ = ρge ρψ ∂ xi ∂ xj ψ + ρ(∂ xi ψ)(∂ xj ψ) = ∂ xi ∂ xj ψ + ρ(∂ xi ψ)(∂ xj ψ) |∇Φ ρ | |∇ψ| ,
directly from (3.2) and (3.32). Thus, using (C.ii), each |∂ xi ∂ xj Φ ρ |, i, j = 1, . . . , n, is upper bounded by ρ|∇Φ ρ |, up to some positive multiplicative constant depending only on ψ and α 0 . As a consequence, there exists C = C(ψ, α 0 ) ∈ (0, +∞), such that

H(Φ ρ )ξ • ξ ≤ Cρ|∇Φ ρ ||ξ| 2 , ξ ∈ R n-1 × R.
This immediately leads to (c).

∆ 2 Φ ρ ≤ C(ψ, α 0 )ρ 4 ge ρψ ≤ C(ψ, T, α 0 )(ρe -ρψ )ρ 3 ge 2ρψ ≤ C(ψ, T, α 0 )ρ 3 ge 2ρψ .
Thus, we have

∆ 2 Φ ρ ≤ C(ψ, T, α 0 )|∇Φ ρ | 3 ,
and inequality (d) follows immediately from this, (3.37) and (3.39)-(3.40).

e) Using (3.2), we get through direct computations, that

∂ t Φ ρ = (2t -T )gΦ ρ and ∂ 2 t Φ ρ (t, x) = 2 1 + (2t -T ) 2 g gΦ ρ .
From this and the basic estimate |Φ ρ | ≤ ge 2ρ ψ L ∞ (Ω) , we derive that

|∂ t Φ ρ | ≤ T g 2 e 2ρ ψ L ∞ (Ω) and ∂ 2 t Φ ρ ≤ 2(4 + T 4 ) T 2 g 3 e 2ρ ψ L ∞ (Ω) . (3.41)
Further, as ∇Φ ρ = ρge ρψ ∇ψ, we have |∇Φ ρ | ≥ ρgα 0 , by (C.ii), then it follows readily from (3.41), that

∂ 2 t Φ ρ + |∇Φ ρ | -1 (∂ t Φ ρ ) 2 ≤ C(T, α 0 )g 3 e 4ρ ψ L ∞ (Ω) ≤ C(T, α 0 )|∇Φ ρ | 3 e 4ρ ψ L ∞ (Ω) , ρ ∈ [1, +∞),
giving the estimate (e).

4 Proof of Theorem 1.2

The proof of Theorem 1.2 is based on an observability inequality, that is derived in the coming section with the aid of the Carleman estimate (3.3).

Observability inequality

The statement we are aiming for, is as follows.

Proposition 4.1 Let γ and γ be the same as in Theorem 1.2. For v 0 ∈ H 1 0 (Ω), let v be the H 2,1 (Q)∩C([0, T ], H 1 0 (Ω))-solution given by Theorem 1.1, to the IBVP (1.3) associated with f = 0. Then, there exists a constant C > 0, depending only on α 0 , ω, γ , and T , such that we have

v(T, •) H 1 (Ω) ≤ C ∂ ν v L 2 ((0,T )×γ) . (4.1)
where the abuse of notation β stands for the function Q

(t, x) → β(x) ∈ L 2 (0, T ; H 1 0 (Ω)). Then, v := ∂ t u is a solution to the system      ∂ t v -∆v = 0 in Q, v(0, •) = β in Ω, v = 0 on Σ, (4.7)
and since β ∈ H 1 0 (Ω), we find that v ∈ H 2,1 (Q) ∩ C([0, T ]; H 1 0 (Ω)) by applying Theorem 1.1. b) Fiber and spectral decompositions. We stick with the notations of Section 2.1 and still denote by A the Dirichlet Laplacian in L 2 (Ω), with domain D(A) = H 1 0 (Ω) ∩ H 2 (Ω). Let F xn be the partial Fourier transform with respect to x n , defined for all ϕ ∈ L 1 (Q), by

F xn ϕ(t, x , k) := (2π) -1/2 R ϕ(t, x , x n )e -ikxn dx n , (t, x ) ∈ (0, T ) × ω, k ∈ R,
and then suitably extended into a unitary operator in L 2 (Q). Due to the translational invariance of the operator A in the infinite direction x n , we have

F xn AF -1 xn = ⊕ R H(k)dk, (4.8)
where

H(k) := A + k 2 and A is the Dirichlet Laplacian in L 2 (ω). Since the multiplier by k 2 is bounded in L 2 (ω), then we have D(H(k)) = D(A ) = H 1 0 (ω) ∩ H 2 (ω).
Further, as ω is bounded, we know that the resolvent of the operator A is compact, and that the spectrum of A is purely discrete. We denote by {λ , ≥ 1} the sequence of (positive) eigenvalues of A , arranged in non-decreasing order and repeated according to their multiplicity. Next, we introduce a Hilbert basis {ϕ , ≥ 1} in L 2 (ω), of eigenfunctions of A , i.e. where E λ := {(k, ) ∈ R × N * ; λ + k 2 ≤ λ} is the set of energies lower or equal to λ. In light of (4.9), this entails that .

β 2 L 2 (Ω) ≤ E λ e 2(
Putting this together with (4.10)-(4.11), we obtain

β 2 L 2 (Ω) ≤ Ce 2λT κ 2 + M 2 λ , (4.12)
where κ := ∂ ν u H 1 (0,T ;L 2 (γ)) ∈ [0, +∞).

Having established (4.12), we investigate each of the three cases κ = 0, κ ∈ 0, e -2T λ1 , and κ ∈ [e -2T λ1 , +∞), separately. We start with κ ∈ 0, e -2T λ1 . In this case, taking λ = -ln κ 2T in (4.12), leads to

β 2 L 2 (Ω) ≤ C κ + | ln(κ)| -1 ≤ C κ 1/2 + | ln(κ)| -1/2 2 , (4.13)
which is exactly the statement (1.7). Moreover, we find β = 0 by sending κ to 0 in (4.13), entailing (1.7) with κ = 0. Finally, for all κ ∈ [e -2T λ1 , +∞), it is apparent that

β L 2 (Ω) ≤ M ≤ M e T λ1 κ 1/2 + | ln(κ)| -1/2 .
Therefore, (1.7) holds for any κ ∈ [0, +∞), and the proof of Theorem 1.2 is complete.

. 1 ) 3 . 1 A

 131 Carleman estimate for P Let γ := γ × R be the same as in Theorem 1.2. With reference to [16, Lemma 1.1] (see also [8, Lemma 1.1]), we pick 1 a function ψ 0 ∈ C 4 (ω), such that (c.i) ψ 0 (x ) > 0 for all x ∈ ω;

  This way, putting Points (d) and (e) in Lemma 3.1, together with (3.6), (3.21), (3.22), (3.24), and (3.27) -(3.28), we find for any

  a) We have ∇Φ ρ = ρge ρψ ∇ψ, (3.32) from the very definition (3.2) of Φ ρ . Thus, using that g(t) ≥ 4T -2 for all t ∈ (0, T ), we deduce the estimate (a) directly from (3.32) and (C.ii). b) With reference to (3.2) and (3.32), we see that ∇|∇Φ ρ | = ρg∇ e ρψ |∇ψ| = ρgρe ρψ (|∇ψ|∇ψ + ∇|∇ψ|) = ρ|∇ψ|∇Φ ρ + |∇Φ ρ | ∇|∇ψ| |∇ψ| , and hence

≤ Cα - 1 0

 1 |∇Φ ρ |, by (C.ii), where C = C(ψ) is a positive constant depending only on ψ, in virtue of (C.ii). Therefore, (3.33) yields

A ϕ = λ ϕ , ≥ 1 .R 2

 12 Then, putting v(•, •, k) := F xn v(•, •, k) and β(•, k) := F xn β(•, k) for all k ∈ R, we find upon applying the transform F xn to both sides of (4.7), that     ∂ t v(•, •, k) + H(k)v(•, •, k) = 0 in (0, T ) × ω, v(0, •, k) = β(•, k) in ω, v(•, •, k) = 0 on (0, T ) × ∂ω. Therefore, each function (0, T ) t → v k, (t) := v(t, •, k), ϕ L 2 (ω) , for (k, ) ∈ R×N * := {1, 2, . . .}, is a solution to the differential equation v k, + (λ + k 2 )v k, = 0 in (0, T ), with initial data v k, (0) = β k, := β(•, k), ϕ L 2 (ω). As a consequence, we havev k, (t) = β k, e -(λ +k 2 )t , t ∈ [0, T ], (k, ) ∈ R × N * .For further use, we notice from the above identity thatβ k, = e (λ +k 2 )T v k, (T ), (k, ) ∈ R × N * .(4.9)c) Splitting energies. Let us introduce the measure µ := ∈N * δ on R, where δ denotes the delta Dirac measure at , in such a way thatβ 2 L 2 (Ω) = R 2 |β k, |2dµ( )dk, by the Plancherel formula. Thus, for all fixed λ ∈ (λ 1 , +∞), it holds true thatβ 2 L 2 (Ω) = E λ |β k, | 2 dµ( )dk + \E λ |β k, | 2 dµ( )dk,

  λ +k 2 )T |v k, (T )| 2 dµ( )dk + 1 λ R 2 (λ + k 2 )|β k, | 2 dµ( )dk (λ + k 2 )|β k, | 2 dµ( )dk ≤ e 2λT v(T, •) 2 L 2 (Ω) + 1 λ R 2 (λ + k 2 )|β k, | 2 dµ( )dk. (4.10)Further, we haveR 2 (λ + k 2 )|β k, | 2 dµ( )dk = R H(k) 1/2 β(•, k) 2 L 2 (ω) dk = A 1/2 β 2 L 2 (Ω) = ∇β 2L 2 (Ω) n , in virtue of (4.8), and consequentlyR 2 (λ + k 2 )|β k, | 2 dµ( )dk ≤ β 2 H 1 (Ω) ≤ M 2 . (4.11) Moreover, by applying Proposition 4.1 to the solution v of the IBVP (4.7), we get that v(T, •) H 1 (Ω) ≤ C ∂ ν v L 2 ((0,T )×γ) ≤ C ∂ ν u H 1 (0,T ;L 2 (γ))

	≤ e 2λT	R 2	|v k, (T )| 2 dµ( )dk +	1 λ R 2

This is where the assumption that ∂Ω be C 4 is needed.

Proof. Let us pick a function η ∈ C ∞ ([0, T ]; [0, 1]), obeying η(t) = 0 if t ∈ 0, T 4 , and η(t) = 1 if t ∈ 3T 4 , T , in such a way that w := ηv is solution to the following system:

Then, we have w(T,

, from (1.4), and consequently

since η(T ) = 1 and η vanishes in 0, T 4 ∪ 3T 4 , T . The next step of the proof is to apply the Carleman estimate (3.3) to v. For ρ = ρ 0 and λ = λ 0 (ρ), we get that e λΦρ (λg)

where c 1 is a positive constant depending only on α 0 , ω, γ , and T .

Further, since g(t) ≥ 4 T 2 for all t ∈ (0, T ), and

× Ω, by (3.2), we see that

On the other hand, for all (t, x) ∈ (0, T )×γ, we have Φ ρ (t, x) ≤ -c 2 g(t), where c 2 := e 2ρ ψ L ∞ (Ω)e ρ ψ L ∞ (Ω) ∈ (0, +∞), according to (3.2), which entails

with c 3 := sup r∈(0,+∞) r 1/2 e -c2r ∈ (0, +∞).

From this and (4.4)-(4.5), it then follows that

where c 4 is a positive constant depending only on α 0 , ω, γ , and T . Finally, we obtain Proposition 4.1 by combining (4.3) with (4.6).

Armed with Proposition 4.1, we may now complete the proof of Theorem 1.2.

Completion of the proof

Due to [START_REF] Choulli | Some stability estimates in determining sources and coefficients[END_REF]Remark,pp. 367] and the hypothesis σ(0) = 0, we may assume without loss of generality, that σ(t) = 1 for all t ∈ [0, T ], in the sequel.

a) Time differentiation of the solution. For β ∈ H 1 0 (Ω), we denote by u the H 2,1 (Ω)∩C([0, T ], H 1 0 (Ω))solution given by Theorem 1.1, to the IBVP


Adrien Boiret
email: adrien.boiret@inria.fr

Raphaela Palenta
email: palenta@in.tum.de

Deciding Equivalence of Linear Tree-to-Word Transducers in Polynomial Time

Keywords: Tree Transducer, Deciding Equivalence, Partial Normal Form

We show that the equivalence of linear top-down tree-toword transducers is decidable in polynomial time. Linear tree-to-word transducers are non-copying but not necessarily order-preserving and can be used to express XML and other document transformations. The result is based on a partial normal form that provides a basic characterization of the languages produced by linear tree-to-word transducers.

Introduction

Tree transformations are widely used in functional programming and document processing. Tree transducers are a general model for transforming structured data like a database in a structured or even unstructured way. Consider the following internal representation of a client database that should be transformed to a table in HTML. Deterministic top-down tree transducers can be seen as functional programs that transform trees from the root to the leaves with finite memory. Transformations where the output is not produced in a structured way or where, for example, the output is a string, can be modeled by tree-to-word transducers.

In this paper, we study deterministic linear tree-to-word transducers (ltws), a subset of deterministic tree-to-word transducers that are non-copying, but not necessarily order-preserving. Processing the subtrees in an arbitrary order is important to avoid reordering of the internal data for different use cases. In the example of the client database the names may be needed in different formats, e.g. <s a l u t a t i o n > <name> <surname> <surname >, <name> < t i t l e > <surname> < t i t l e > <surname >, <name>

The equivalence of unrestricted tree-to-word transducers was a long standing open problem that was recently shown to be decidable [START_REF] Seidl | Equivalence of deterministic top-down tree-tostring transducers is decidable[END_REF]. The algorithm by [START_REF] Seidl | Equivalence of deterministic top-down tree-tostring transducers is decidable[END_REF] provides an co-randomized polynomial algorithm for linear transducers. We show that the equivalence of ltws is decidable in polynomial time and provide a partial normal form.

To decide equivalence of ltws, we start in Section 3 by extending the methods used for sequential (linear and order-preserving) tree-to-word transducers (stws), discussed in [START_REF] Staworko | Equivalence of deterministic nested word to word transducers[END_REF]. The equivalence for these transducers is decidable in polynomial time [START_REF] Staworko | Equivalence of deterministic nested word to word transducers[END_REF]. Moreover a normal form for sequential and linear tree-toword transducers, computable in exponential time, is known [START_REF] Laurence | Normalization of sequential top-down tree-to-word transducers[END_REF][START_REF] Boiret | Normal form on linear tree-to-word transducers[END_REF]. Two equivalent ltws do not necessarily transform their trees in the same order. However, the differences that can occur are quite specific and characterized in [START_REF] Boiret | Normal form on linear tree-to-word transducers[END_REF]. We show how they can be identified. We use the notion of earliest states, inspired by the existing notion of earliest sequential transducers [START_REF] Laurence | Normalization of sequential top-down tree-to-word transducers[END_REF]. In this earliest form, two equivalent stws can transform subtrees in different orders only if they fulfill specific properties pertaining to the periodicity of the words they create. Computing this normal form is exponential in complexity as the number of states may increase exponentially. To avoid this size increase we do not compute these earliest transducers fully, but rather locally. This means we transform two ltws with different orders to a partial normal form in polynomial time (see Section 4) where the order of their transformation of the different subtrees are the same. ltws that transform the subtrees of the input in the same order can be reduced to sequential tree-to-word transducers as the input trees can be reordered according to the order in the transformation.

Due to space constraints some proofs are omitted. The full version of the paper can be found at http://arxiv.org/abs/1606.03758.

Related Work. Different other classes of transducers, such as tree-to-tree transducers [START_REF] Engelfriet | Tree transducers, L systems and twoway machines[END_REF], macro tree transducers [START_REF] Engelfriet | Macro tree transducers[END_REF] or nested-word-to-word transducers [START_REF] Staworko | Equivalence of deterministic nested word to word transducers[END_REF] have been studied. Many results for tree-to-tree transducers are known, e.g. deciding equivalence [START_REF] Maneth | Deciding equivalence of top-down XML transformations in polynomial time[END_REF], minimization algorithms [START_REF] Maneth | Deciding equivalence of top-down XML transformations in polynomial time[END_REF] and Gold-style learning algorithms [START_REF] Lemay | A learning algorithm for top-down XML transformations[END_REF]. In contrast, transformations where the output is not generated in a structured way like a tree are not that well understood. In macro-tree transducers, the decidability of equivalence is a well-known and long-standing question [START_REF] Engelfriet | Some open question and recent results on tree transducers and tree languages[END_REF]. However, the equivalence of linear size increase macro-tree transducers that are equivalent to MSO definable transducers is decidable [START_REF] Engelfriet | Macro tree translations of linear size increase are MSO definable[END_REF][START_REF] Engelfriet | The equivalence problem for deterministic MSO tree transducers is decidable[END_REF].

Preliminaries

Let Σ be a ranked alphabet with Σ (n) the symbols of rank n. Trees on Σ (T Σ ) are defined inductively: if f ∈ Σ (n) , and t 1 , ..., t n ∈ T Σ , then f (t 1 , ..., t n ) ∈ T Σ is a tree. Let ∆ be an alphabet. An element w ∈ ∆ * is a word. For two words u, v we denote the concatenation of these two words by uv. The length of a word w is denoted by |w|. We call ε the empty word. We denote a -1 the inverse of a symbol a where aa -1 = a -1 a = ε. The inverse of a word w = u 1 . . . u n is w

-1 = u -1 n . . . u -1 1 .
A context-free grammar (CFG) is defined as a tuple (∆, N, S, P ), where ∆ is the alphabet of G, N is a finite set of non-terminal symbols, S ∈ N is the initial non-terminal of G, P is a finite set of rules of form A → w, where A ∈ N and w ∈ (∆ ∪ N ) * . A CFG is deterministic if each non-terminal has at most one rule.

We define the language L G (A) of a non-terminal A recursively: if A → u 0 A 1 u 1 ...A n u n is a rule of P , with u i words of ∆ * and A i non-terminals of N , and w i a word of L G (A i ), then u 0 w 1 u 1 ...w n u n is a word of L G (A). We define the context-free language L G of a context-free grammar G as L G (S).

A straight-line program (SLP) is a deterministic CFG that produces exactly one word. The word produced by an SLP (∆, N, S, P ) is called w S .

We denote the longest common prefix of all words of a language L by lcp(L).

Its longest common suffix is lcs(L).

A word u is said to be periodic of period w if w is the smallest word such that u ∈ w * . A language L is said to be periodic of period w if w is the smallest word such that L ⊆ w * .

A language L is quasi-periodic on the left (resp. on the right) of handle u and period w if w is the smallest word such that L ⊆ uw * (resp. if L ⊆ w * u). A language is quasi-periodic if it is quasi-periodic on the right or left. If L is a singleton or empty, it is periodic of period ε. Iff L is periodic, it is quasi-periodic on the left and the right of handle ε. If L is quasi-periodic on the left (resp. right) then lcp(L) (resp. lcs(L)) is the shortest word of L.

Linear Tree-to-Word Transducers

A linear tree-to-word transducer (ltw) is a tuple M = (Σ, ∆, Q, ax, δ) where -Σ is a ranked alphabet, -∆ is an alphabet of output symbols, -Q is a finite set of states, the axiom ax is of the form u 0 q(x)u 1 , where q ∈ Q and u 0 , u 1 ∈ ∆ * , δ is a set of rules of the form q, f → u 0 q 1 (x σ(1) ) . . . q n (x σ(n) )u n where q, q 1 , . . . , q n ∈ Q, f ∈ Σ of rank n, u 0 , . . . , u n ∈ ∆ * and σ is a permutation from {1, . . . , n} to {1, . . . , n}. There is at most one rule per pair q, f . The partial function M q of a state q on an input tree f (t 1 , . . . , t n ) is defined inductively as

-u 0 M q1 (t σ(1) ) . . . M qn (t σ(n) )u n , if q, f → u 0 q 1 (x σ(1) ) . . . q n (x σ(n) )u n ∈ δ -undefined, if q, f is not defined in δ.
The partial function M of an ltw M with axiom u 0 q(x)u 1 on an input tree t is defined as M (t) = u 0 M q (t)u 1 . Two ltws M and M are equivalent if M = M . A sequential tree-to-word transducer (stw) is an ltw where for each rule of the form q, f → u 0 q 1 (x σ(1) )u 1 . . . q n (x σ(n) )u n , σ is the identity on 1 . . . n.

We define accessibility of states as the transitive and reflexive closure of appearance in a rule. This means state q is accessible from itself, and if q, f → u 0 q 1 (x σ(1) ) . . . q n (x σ(n) )u n , and q is accessible from q , then all states q i , 1 ≤ i ≤ n, are accessible from q .

We denote by dom(M ) (resp. dom(q)) the domain of an ltw M (resp. a state q), i.e. all trees t ∈ T Σ such that M (t) is defined (resp. M q (t)). We only consider ltws with non-empty domains and assume w.l.o.g. that no state q in an ltw has an empty domain by eliminating transitions using states with empty domain.

We denote by L M (resp. L q ) the range of M (resp. M q ), i.e. the set of all images M (t) (resp. M q (t)). The languages L M and L q for each q ∈ Q are all context-free languages. We call a state q (quasi-)periodic if L q is (quasi-)periodic.

Note that a word u in a rule of an ltw can be represented by an SLP without changing the semantics of the ltw. Therefore a set of SLPs is added to the transducer and a word on the right-hand side of a rule is represented by an SLPs. The decidability of equivalence of stws in polynomial time still holds true with the use of SLPs.

The results of this paper require SLP compression to avoid exponential blowup. SLPs are used to prevent exponential blow-up in [START_REF] Plandowski | The complexity of the morphism equivalence problem for contextfree languages[END_REF], where morphism equivalence on context-free languages is decided in polynomial time.

The equivalence problem for sequential tree-to-word transducer can be reduced to the morphism equivalence problem for context-free languages [START_REF] Staworko | Equivalence of deterministic nested word to word transducers[END_REF]. This reduction relies on the fact that STWs transform their subtrees in the same order. As ltws do not necessarily transform their subtrees in the same order the result cannot be applied on ltws in general. However, if two ltws transform their subtrees in the same order, then the same reduction can be applied. To formalize that two ltws transform their subtrees in the same order we introduce the notion of state co-reachability. Two states q 1 and q 2 of ltws M 1 , M 2 , respectively, are co-reachable if there is an input tree such that the two states are assigned to the same node of the input tree in the translations of M 1 , M 2 , respectively.

Two ltws are same-ordered if for each pair of co-reachable states q 1 , q 2 and for each symbol f ∈ Σ, neither q 1 nor q 2 have a rule for f , or if

q 1 , f → u 0 q 1 (x σ1(1) ) . . . q n (x σ1(n) )u n and q 2 , f → v 0 q 1 (x σ2(1) ) . . . q n (x σ2(n) )v n are rules of q 1 and q 2 , then σ 1 = σ 2 .
If two ltws are same-ordered the input trees can be reordered according to the order in the transformations. Therefore for each ltw a tree-to-tree transducer is constructed that transforms the input tree according to the transformation in the ltw. Then all permutations σ in the ltws are replaced by the identity. Thus the ltws can be handled as stws and therefore the equivalence is decidable in polynomial time [START_REF] Staworko | Equivalence of deterministic nested word to word transducers[END_REF].

Theorem 1. The equivalence of same-ordered ltws is decidable in polynomial time.

Linear Earliest Normal Form

In this section we introduce the two key properties that are used to build a normal form for linear tree-to-word transducers, namely the earliest and eraseordered properties. The earliest property means that the output is produced as early as possible, i.e. the longest common prefix (resp. suffix) of L q is produced in the rule in which q occurs, and as left as possible. The erase-ordered property means that all states that produce no output are ordered according to the input tree and pushed to the right in the rules.

An ltw is in earliest form if each state q is earliest, i.e. lcp(L q ) = lcs(L q ) = ε, and for each rule q, f → u 0 q 1 (x σ(1) ) . . . q n (x σ(n) )u n , for each i,

1 ≤ i ≤ n, lcp(L qi u i ) = ε.
In [1, Lemma 9] it is shown that for each ltw M an equivalent earliest ltw M can be constructed in exponential time.

Intuitively, if lcp(L q ) = v = ε (resp. lcs(L q ) = v = ε) then q is constructed with L q = v -1 L q (resp. L q = L q v -1 ) and q(x) is replaced by vq (x) (resp. q (x)v). If lcp(L q u) = v = ε
and v is a prefix of u = vv then we push v through L q by constructing q with L q = v -1 L q v and replace q(x)u by vq (x)v .

Note that the construction to build the earliest form M of an ltw M creates a same-ordered M . Furthermore, if a state q of M and a state q of M are coreachable, then q is an "earliest" version of q, where some word u was pushed out of the production of q to make it earliest, and some word v was pushed through the production of q to ensure that the rules have the right property: there exists u, v ∈ ∆ * such that for all t ∈ dom(q), M q (t) = v -1 u -1 M q (t)v.

Theorem 2. For each ltw an equivalent same-ordered and earliest ltw can be constructed in exponential time.

The exponential time complexity is caused by a potential exponential size increase in the number of states as it is shown in [7, Example 5].

We call a state q that produces only the empty word, i.e. L q = {ε}, an erasing state. As erasing states do not change the transformation and can occur at any position in a rule we need to fix their position for a normal form.

An ltw M is erase-ordered if for each rule q, f → u 0 q 1 (x σ(1) ) . . . q n (x σ(n) )u n in M , if q i is erasing then for all j ≥ i, q j is erasing, σ(i) ≤ σ(j) and u j = ε.

We test whether L q = {ε} in polynomial time and then reorder a rule according to the erase-ordered property. If an ltw is earliest it is still earliest after the reordering.

Lemma 3 (extended from [1, Lemma 18]). For each (earliest) ltw an equivalent (earliest) erase-ordered ltw can be constructed in polynomial time.

Example 4. Consider the rule q 0 , f → q 1 (x 4 )q 2 (x 3 )q 1 (x 2 )q 4 (x 1 ) where q 2 translates trees of the form f n (g), n ≥ 0 to (abc) n , q 4 translates trees of the form f n (g), n ≥ 0 to (abc) 2n , q 1 translates trees of the form f n (g), n ≥ 0 to ε. Thus the rule is not erase-ordered. We reorder the rule to the equivalent and eraseordered rule q 0 , f → q 2 (x 3 )q 4 (x 1 )q 1 (x 2 )q 1 (x 4 ).

If two equivalent ltws are earliest and erase-ordered, then they are not necessarily same-ordered. For example, the rule q, f → q 4 (x 1 )q 2 (x 3 )q 1 (x 2 )q 1 (x 4 ) is equivalent to the rule in the above example but the two rules are not sameordered. However, in earliest and erase-ordered ltws, we can characterize the differences in the orders of equivalent rules: Just as two words u, v satisfy the equation uv = vu if and only if there is a word w such that u ∈ w * and v ∈ w * , the only way for equivalent earliest and erase-ordered ltws to not be sameordered is to switch periodic states.

Theorem 5 ([1]

). Let M and M be two equivalent erase-ordered and earliest ltws and q, q be two co-reachable states in M , M , respectively. Let q, f → u 0 q 1 (x σ1(1) ) . . . q n (x σ1(n) )u n and q , f → v 0 q 1 (x σ2(1) ) . . . q n (x σ2(n) )v n be two rules for q, q . Then for k < l such that σ 1 (k) = σ 2 (l), all q i , k ≤ i ≤ l, are periodic of the same period and all

u j = ε, k ≤ j < l, -for k, l such that σ 1 (k) = σ 2 (l), M q k = M q l .
As the subtrees that are not same-ordered in two equivalent earliest and erase-ordered states are periodic of the same period the order of these can be changed without changing the semantics. Therefore the order of these subtrees can be fixed such that equivalent earliest and erase-ordered ltws are sameordered. Then the equivalence is decidable in polynomial time, see Theorem 1. However, building the earliest form of an ltw is in exponential time.

To circumvent this difficulty, we will show that the first part of Theorem 5 still holds even on a partial normal form, where only quasi-periodic states are earliest and the longest common prefix of parts of rules q(x)u with L q u being quasi-periodic is the empty word. Theorem 6. Let M and M be two equivalent erase-ordered ltws such that all quasi-periodic states q are earliest, i.e. lcp(q) = lcs(q) = ε for each part q(x)u of a rule where L q u is quasi-periodic, lcp(L q u) = ε Let q, q be two co-reachable states in M , M , respectively and q, f → u 0 q 1 (x σ1(1) ) . . . q n (x σ1(n) )u n and q , f → v 0 q 1 (x σ2(1) ) . . . q n (x σ2(n) )v n be two rules for q, q . Then for k < l such that σ 1 (k) = σ 2 (l), all q i , k ≤ i ≤ l, are periodic of the same period and all u j = ε, k ≤ j < l.

Partial Normal Form

In this section we introduce a partial normal form for ltws that does not suffer from the exponential blow-up of the earliest form. Inspired by Theorem 6, we wish to solve order differences by switching adjacent periodic states of the same period. Remember that the earliest form of a state q is constructed by removing the longest common prefix (suffix) of L q to produce this prefix (suffix) earlier.

It follows that all non-earliest states from which q can be constructed following the earliest form are quasi-periodic.

We show that building the earliest form of a quasi-periodic state or a part of a rule q(x)u with L q u being quasi-periodic is in polynomial time. Therefore building the following partial normal form is in polynomial time. Definition 7. A linear tree-to-word transducer is in partial normal form if 1. all quasi-periodic states are earliest, 2. it is erase-ordered and 3. for each rule q, f → u 0 q 1 (x σ(1) ) . . .

q n (x σ(n) )u n if L qi u i L qi+1 is quasi-periodic then q i (x σ(i) )u i q i+1 (x σ(i+1)
) is earliest and σ(i) < σ(i + 1).

Eliminating Non-Earliest Quasi-Periodic States

In this part, we show a polynomial time algorithm to build an earliest form of a quasi-periodic state. From which an equivalent ltw can be constructed in polynomial time such that any quasi-periodic state is earliest, i.e. lcp(L q ) = lcs(L q ) = ε. Additionally, we show that the presented algorithm can be adjusted to test if a state is quasi-periodic in polynomial time.

As quasi-periodicity on the left and on the right are symmetric properties we only consider quasi-periodic states of the form uw * (quasi-periodic on the left). The proofs in the case w * u are symmetric and therefore omitted here. In the end of this section we shortly discuss the introduced algorithms for the symmetric case w * u.

To build the earliest form of a quasi-periodic state we use the property that each state accessible from a quasi-periodic state is as well quasi-periodic. However, the periods can be shifted as the following example shows.

Example 8. Consider states q, q 1 and q 2 with rules q, f → aq 1 (x 1 )c, q 1 , f → aaq 2 (x 1 )ab, q 2 , f → q 2 (x 1 )abc, q 2 , g → abc. State q accepts trees of the form f n (g), n ≥ 2, and produces the language aaa(abc) n , i.e. q is quasi-periodic of period abc. State q 1 accepts trees of the form f n (g), n ≥ 1, and produces the language aa(abc) n ab, i.e. q 1 is quasi-periodic of period cab. State q 2 accepts trees of the form f n (g), n ≥ 0 and produces the language (abc) n+1 , i.e. q 2 is (quasi-)periodic of period abc.

We introduce two definitions to measure the shift of periods. We denote by

ρ n [u] the from right-to-left shifted word of u of shift n, n ≤ |u|, i.e. ρ n [u] = u -1 uu where u is the prefix of u of size n. If n ≥ |u| then ρ n [u] = ρ m [u] with m = n mod |u|.
For two quasi-periodic states q 1 , q 2 of period u = u 1 u 2 and u = u 2 u 1 , respectively, we denote the shift in their period by s(q 1 , q 2 ) = |u 1 |.

The size of the periods of a quasi-periodic state and the states accessible from this state can be computed from the size of the shortest words of the languages produced by these states. Lemma 9. If q is quasi-periodic on the left with period w, and q accessible from q, then q is quasi-periodic with period ε or a shift of w. Moreover we can calculate the shift s(q, q ) in polynomial time.

We now use these shifts to build, for a state q in M that is quasi-periodic on the left, a transducer M q equivalent to M where each occurrence of q is replaced by its equivalent earliest form, i.e. a periodic state and the corresponding prefix.

Algorithm 1. Let q be a state in M that is quasi-periodic on the left. M q starts with the same states, axiom, and rules as M .

-For each state p accessible from q, we add a copy p e to M q .

-For each rule p, f → u 0 q 1 (x σ(1) ) . . . q n (x σ(n) )u n in M with p accessible from q, we add a rule p e , f → u p q e 1 (x σ( 1) )q e 2 (x σ(2) ) . . . q e n (x σ(n) ) with u p = ρ s(q,p) lcp(p) -1 u 0 lcp(q 1 ) . . . lcp(q n )u n in M q .

-We delete state q in M q and replace any occurrence of q(x) in a rule or the axiom of M q by lcp(q)q e (x).

Note that lcp(p) -1 u 0 lcp(q 1 ) . . . lcp(q n )u n is equivalent to deleting the prefix of size |lcp(p)| from the word u 0 lcp(q 1 ) . . . lcp(q n )u n . Intuitively, to build the earliest form of a state q that is quasi-periodic on the left we need to push all words and all longest common prefixes of states on the right-hand side of a rule of q to the left. Pushing a word to the left through a state needs to shift the language produced by this state. We explain the algorithm in detail on state q from Example 8.

Example 10. Remember that q produces the language aaa(abc) n , n ≥ 2 and q 1 , q 2 accessible from q produce languages aa(abc) n ab, n ≥ 1 and (abc) n+1 , n ≥ 0, respectively. Therefore lcp(q) = aaaabcabc, lcp(q 1 ) = aaabcab and lcp(q 2 ) = abc. We start with state q. As there is only one rule for q the longest common prefix of q and the longest common prefix of this rule are the same and therefore eliminated.

q e , f → ρ s(q,q) [lcp(q) -1 alcp(q 1 )c]q e 1 (x 1 ) → ρ s(q,q) [(aaaabcabc) -1 aaaabcabc]q e 1 (x 1 ) → q e 1 (x 1 ) As there is only one rule for q 1 the argumentation is the same and we get q e 1 , f → q e 2 . For the rule q 2 , f we calculate the longest common prefix of the right-hand side lcp(q 2 )abc = abcabc that is larger than the longest common prefix of q 2 . Therefore we need to calculate the shift s(q, q 2 ) = s(q, q 1 ) + s(q 1 , q 2 ) = |c| + |ab| = 3 as q 1 is accessible from q in rule q, f and q 2 is accessible from q 1 in rule q 1 , f . This leads to the following rule.

q e 2 , f → ρ s(q,q2) [lcp(q 2 ) -1 lcp(q 2 )abc]q e 2 (x 1 ) → ρ 3 [(abc) -1 abcabc]q e 2 (x 1 ) → abcq e 2 (x 1 ) As the longest common prefix of q 2 is the same as the longest common prefix of the right-hand side of rule q 2 , g we get q e 2 , g → ε. The axiom of M q is lcp(q)q e (x 1 ) = aaaabcabcq e (x 1 ). Lemma 11. Let M be an ltw and q be a state in M that is quasi-periodic on the left. Let M q be constructed by Algorithm 1 and p e be a state in M q accessible from q e . Then M and M q are equivalent and p e is earliest.

To replace all quasi-periodic states by their equivalent earliest form we need to know which states are quasi-periodic. Algorithm 1 can be modified to test an arbitrary state for quasi-periodicity on the left in polynomial time. The only difference to Algorithm 1 is that we do not know how to compute lcp(p) in polynomial time and s(q, p) does not exist. We therefore substitute lcp(p) by some smallest word of L p and we define a mock-shift s (q, p) as follows s (q, q) = 0 for all q, if q, f → u 0 q 1 (x σ(1) ) . . . q n (x σ(n) )u n , we say s (q, q i ) = |u i w qi+1 . . . w qn u n |, where w q is a shortest word of L q , if s (q 1 , q 2 ) = n and s (q 2 , q 3 ) = m then s (q 1 , q 3 ) = n + m. If several definitions of s (q, p) exist, we use the smallest. If p is accessible from a quasi-periodic q, then s (q, p) = s(q, p). Algorithm 2. Let M = (Σ, ∆, Q, ax, δ) be an ltw and q be a state in M . We build an ltw T q as follows.

-For each state p accessible from q, we add a copy p e to T q .

-The axiom is w q q e (x) where w q is a shortest word of L q .

-For each rule p, f → u 0 q 1 (x σ(1) ) . . . q n (x σ(n) )u n in M with p accessible from q, we add a rule p e , f → u p q e 1 (x σ(1) )q e 2 (x σ(2) ) . . . q e n (x σ(n) )

in T q , where u p is constructed as follows.

• We define u = u 0 w 1 . . . w n u n , where w i is a shortest word of L qi .

• Then we remove from u its prefix of size |w |, where w is a shortest word of L p . We obtain a word u . • Finally, we set u p = ρ s (q,p) [u ].

As the construction of Algorithms 1 and 2 are the same if the state q is quasi-periodic, M q and T q are equivalent if q is quasi-periodic. Moreover, q is quasi-periodic if M q and T q are equivalent. Lemma 12. Let q be a state of an ltw M and T q be constructed by Algorithm 2. Then M and T q are same-ordered and q is quasi-periodic on the left if and only if M q = T q and q e is periodic.

As M and T q are same-ordered we can test the equivalence in polynomial time, cf. Theorem 1. Moreover testing a CFG for periodicity is in polynomial time and therefore testing a state for quasi-periodicity is in polynomial time.

Algorithm 2 can be applied to a part q(x)u of a rule to test L q u for quasiperiodicity on the left. In this case for each rule q, f → u 0 q 1 (x σ(1) ) . . . q n (x σ(n) )u n a rule q, f → u 0 q 1 (x σ(1) ) . . . q n (x σ(n) )u n u is added to M and each occurrence of the part q(x)u in a rule of M is replaced by q(x). We then apply the above algorithm to q and test M q and T q for equivalence and qe for periodicity.

We introduced algorithms to test states for quasi-periodicity on the left and to build the earliest form for such states. These two algorithms can be adapted for states that are quasi-periodic on the right. There are two main differences. First, as the handle is on the right the shortest word of a language L that is quasi-periodic on the right is lcs(L). Second, instead of pushing words through a periodic language to the left we need to push words through a periodic language to the right.

Hence, we can test each state q of an ltw M for quasi-periodicity on the left and right. If the state is quasi-periodic we replace q by its earliest form. Algorithm 1 and 2 run in polynomial time if SLPs are used. This is crucial as the shortest word of a CFG can be of exponential size. However, the operations that are needed in the algorithms, namely constructing the shortest word of a CFG and removing the prefix or suffix of a word, are in polynomial time using SLPs, cf. [START_REF] Lohrey | The Compressed Word Problem for Groups[END_REF]. Theorem 13. Let M be an ltw. Then an equivalent ltw M where all quasiperiodic states are earliest can be constructed in polynomial time.

Switching Periodic States

In this part we obtain the partial normal form by ordering periodic states of an erase-ordered transducer where all quasi-periodic states are earliest. Ordering means that if the order of the subtrees in the translation can differ, we choose the one similar to the input, i.e. if q(x 3 )q (x 1 ) and q (x 1 )q(x 3 ) are equivalent, we choose the second order. We already showed how we can build a transducer where each quasi-periodic state is earliest and therefore periodic. However, we need to make parts of rules earliest such that periodic states can be switched as the following example shows.

Example 14. Consider the rule q, h → q 1 (x 2 )bq 2 (x 1 ) where q 1 , q 2 have the rules q 1 , f → bcabcaq 1 (x), q 1 , g → ε, q 2 , f → cabq 2 (x), q 2 , g → ε. States q 1 and q 2 are earliest and periodic but not of the same period as a subword is produced in between. We replace the non-earliest and quasi-periodic part q 1 (x 2 )b by their earliest form. This leads to q, h → bq e 1 (x 2 )q 2 (x 1 ) with q e 1 , f → cabcabq e 1 (x), q e 1 , g → ε. Hence, q e 1 and q 2 are earliest and periodic of the same period and can be switched in the rule.

To build the earliest form of a quasi-periodic part of a rule q(x)u each occurrence of this part is replaced by a state q(x) and for each rule q, f → u 0 q 1 (x σ(1) ) . . . q n (x σ(n) )u n a rule q, f → u 0 q 1 (x σ(1) ) . . . q n (x σ(n) )u n u is added. Then we apply Algorithm 1 on q to replace q and therefore q(x)u by their earliest form. Iteratively this leads to the following theorem.

Theorem 15. For each ltw M where all quasi-periodic states are earliest we can build in polynomial time an equivalent ltw M such that each part q(x)u of a rule in M where L q u is quasi-periodic is earliest.

In Theorem 6 we showed that order differences in equivalent erase-ordered ltws where all quasi-periodic states are earliest and all parts of rules q(x)u are earliest are caused by adjacent periodic states. As these states are periodic of the same period and no words are produced in between these states can be reordered without changing the semantics of the ltws.

Lemma 16. Let M be an ltw such that -M is erase-ordered, all quasi-periodic states in M are earliest and each q i (x σ(i) )u i in a rule of M that is quasi-periodic is earliest. Then we can reorder adjacent periodic states q i (x σ(i) )q i+1 (x σ(i+1) ) of the same period in the rules of M such that σ(i) < σ(j) in polynomial time. The reordering does not change the transformation of M .

We showed before how to construct a transducer with the preconditions needed in Lemma 16 in polynomial time. Note that replacing a quasi-periodic state by its earliest form can break the erase-ordered property. Thus we need to replace all quasi-periodic states by its earliest form before building the eraseordered form of a transducer. Then Lemma 16 is the last step to obtain the partial normal form for an ltw.

Theorem 17. For each ltw we can construct an equivalent ltw that is in partial normal form in polynomial time.

Testing Equivalence in Polynomial Time

It remains to show that the equivalence problem of ltws in partial normal form is decidable in polynomial time. The key idea is that two equivalent ltws in partial normal form are same-ordered.

Consider two equivalent ltws M 1 , M 2 where all quasi-periodic states and all parts of rules q(x)u with L q u is quasi-periodic are earliest. In Theorem 6 we showed if the orders σ 1 , σ 2 of two co-reachable states q 1 , q 2 of M 1 , M 2 , respectively, for the same input differ then the states causing this order differences are periodic with the same period. The partial normal form solves this order differences such that the transducers are same-ordered.

Lemma 18. If M and M are equivalent and in partial normal form then they are same-ordered.

As the equivalence of same-ordered ltws is decidable in polynomial time (cf. Theorem 1) we conclude the following.

Corollary 19. The equivalence problem for ltws in partial normal form is decidable in polynomial time.

To summarize, the following steps run in polynomial time and transform a ltw M into its partial normal form.

1. Test each state for quasi-periodicity. If it is quasi-periodic replace the state by its earliest form. 2. Build the equivalent erase-ordered transducer. 3. Test each part q(x)u in each rule from right to left for quasi-periodicity on the left. If it is quasi-periodic replace the part by its earliest form. 4. Order adjacent periodic states of the same period according to the input order. This leads to our main theorem.

Theorem 20. The equivalence of ltws is decidable in polynomial time.

Acknowledgement

We would like to thank the reviewers for their very helpful comments and suggestions.

This work was partially supported by a grant from CPER Nord-Pas de Calais/FEDER DATA Advanced data science and technologies 2015-2020


Ali Israr

Siyan Zhao

Kyna Mcintosh

Zachary Schwemler

Adam Fritz

John Mars

Job Bedford

Christian Frisson

Ivan Huerta

Maggie Kosek

Babis Koniaris

Kenny Mitchell

Stereohaptics: A Haptic Interaction Toolkit for Tangible Virtual Experiences

Introduction

With a recent rise in the availability of affordable head mounted gear sets, various sensory stimulations (e.g., visual, auditory and haptics) are integrated to provide seamlessly embodied virtual experience in areas such as education, entertainment, therapy and social interactions. Currently, there is an abundance of available toolkits and application programming interfaces (APIs) for generating the visual and audio content. However, such richness in hardware technologies and software tools is missing in designing haptic experiences. Current solutions to integrate haptic effects are limited due to: i) a user's rigid adaptation to new hardware and software technologies, ii) limited scalability of the existing tools to incorporate haptic hardware and applications, iii) inflexible authoring capabilities, iv) missing infrastructure for storing, playback and distribution, and v) and unreliable hardware for long term usage.

We propose "Stereohaptics", a framework to create, record, modify, and playback rich and dynamic haptic media using audio based tools. These tools are well established, mainstream and familiar to a large population in entertainment, design, academic, and the DIY communities, and already available for sound synthesis, recording, and playback. We tune these audio-based tools to create haptic media on user's bodies, distribute it to multiple slave units, and share it over the Internet. Applicable to the framework, we introduce a toolkit, the Stereohaptics toolkit, which uses off-the-shelf speaker technologies (electromagnetics, piezoelectric, electrostatic) and audio software tools to generate and embed haptic media in a variety of multisensory settings. This way, designers, artists, students and other professionals who are already familiar with sound production processes can utilize their skills to contribute towards designing haptics experiences. Moreover, using the audio infrastructure, application designers and software developers can create new applications and distribute haptic content to everyday users on mobile devices, computers, toys, game controllers and so on.

Studio workshop

The goals of this studio is to educate and familiarize attendees (students, artists, designers and specifically the sound media workforce) with the technologies and tools common in the sound design settings, and utilize these techniques to create dynamic haptic experiences. Attendees will go through a number of hands-on activities to familiarize themselves with sound actuation technologies (such as voice coil speakers and subwoofers, piezo actuators, electrostatic speakers), audio interface tools (e.g. puredate, webaudio, Max/msp), sensors (accelerometers, potentiometers, etc) and hardware plugins (keyboard, joysticks, body trackers, etc.), generate haptic media and embed them in applications. For the purpose of this studio, we will focus on virtual and augmented reality scenarios. Attendees will add haptic feedback to events and activities in simple gameplay and educational settings.

Why Stereohaptics?

Many computing devices are already equipped with two (stereo) audio channels linked to the left and right side speakers. We utilize these two channels to excite two actuators. Therefore, the stereo channel of an attendee's computer (or laptop) is directly used for haptic generation. Two, recent research shows that two or more vibrating actuators create a variety of moving illusory percepts on and across the body [START_REF] Israr | Surround Haptics: sending shivers down your spine[END_REF][START_REF] Israr | Po2: augmented haptics for interactive gameplay[END_REF]. Moreover, these illusions are modeled parametrically to control varying the size, speed, direction and quality of haptic effects. We use these models in our toolkit and allow attendees to set attributes of sensation using sliders, knobs, dials, switches, and/or with an incoming data stream. These effects can be tuned to events, activities and audio-visual content of the games to produce coherent multisensory experience for users. Finally, the two-channel audio/haptic framework can be scaled up to accommodate multiple actuators, such as in a grid configuration of vibrating actuators, and allows users to create surround haptics experiences [START_REF] Zhao | Stereo Haptics: Designing Haptic Interactions using Audio Tools[END_REF].

Architecture

The architecture of a typical audio framework and that of Stereohaptics is shown in Figure 1. A laptop computer runs an audio synthesizer tool that outputs analog waveform from the audiooutput (speaker) channel and senses analog measurements through *e-mail:israr@disneyresearch.com www.stereohaptics.com Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for thirdparty components of this work must be honored. For all other uses, contact the Owner/Author. Copyright is held by the owner/author(s). SIGGRAPH '16 Studio, July 24-28, 2016, Anaheim, CA, ACM 978-1-4503-4373-2/16/07. http://dx.doi.org/10.1145/2929484.2970273 the audio input (microphone) channel. These input-output signals are conditioned through the Stereohaptics hardware board that comprises of common operational and audio amplifier circuitry. The output of the board is connected to off-the-shelf speakers mounted on a user's body, and the input to the board is connected to an analog sensor measuring the user's activity. The audio input channel can be stored, modified and routed to the audio output channel or to other communication channels connected to the laptop computer.

Schedule

The studio will host 16 attendees in two 1.5-hour sessions. • Group activity: Attendees are divided into groups of four with mix talent and background. Each group will be provided with a visual game, hardware and tools, and a computing platform with relevant software and plugins. Each group will add haptic media to the events and activities in the games. (65 min)

• Presentations: Each group will pitch the idea and present it to all attendees of the workshop, 5 min each. (20 min)

• Conclusion: Short survey and goodbye (5 min)

Use cases and applications

Stereohaptics toolkit allows haptic design more accessible to designers and artists. It reaches out to the population of people who already possesses skills to design audio and sound content. Without acquiring new skills, these folks will generate and design haptic feedback. Specifically, this will contextualize visual and auditory content in Virtual Reality. Furthermore, Stereohaptics opens up the possibility of easy distribution and broadcasting of haptic media. As all haptic content created with Stereohaptics is in the audio format, it allows users to playback and share haptic content on computing devices already equipped with the input-output audio channels.

Possible use case applications of the toolkit feature

Enhanced multimedia playback

Interactive gameplay

Bringing touch into audio-visual immersion Social exchanged through networks (e.g. through Skype)

Learning goals

Participants will first learn haptics by experience: they will feel how it affects their sensations, rather than having to guess or imagine the effects of such stimuli by watching video tutorials, where haptics is transduced by audio or visual workarounds and artifacts.

After the studio workshop, attendees will have gained experience on how to design and prototype haptic media using off-the-shelf hardware and software.

More about the toolkit, course material and up to date information on Stereohaptics, please visit: www.stereohaptics.com.

Previous workshops and what's new in Siggraph

This studio workshop builds upon a series of previous iterations: the first installment of Stereohaptics has been hosted at the ACM TEI 2016 conference on February 14th 2016 [START_REF] Zhao | Stereo Haptics: Designing Haptic Interactions using Audio Tools[END_REF]. A subsequent instance of Stereohaptics was hosted at the Web Audio Conference 2016 on April 6th 2016 [START_REF] Frisson | WebAudio-Haptics: Tutorial on Haptics with Web Audio[END_REF], with a shift towards web audio technologies bridging designers from audio-, visual-and hapticsdesign communities through a shared web-based set of protocols and standards. In the Siggraph 2016 Studio, we extend the use of Stereohaptics in Virtual Reality and Augmented Reality settings, extend the library of actuators and sensors, and target the audience for Siggraph that are closely related to educational, gaming and entertainment industries.

Figure 2 .

 2 Figure 2. The Stereohaptics Toolkit used in workshop

Figure 1 .

 1 Figure 1. Architecture of a typical audio framework (top) and the Stereohaptics framework (bottom)

Session 1 :Session 2 :

 12 Introduction and familiarity (1 hours 30 min) • Introduction: Haptics perception and technologies. (15 min) • Introduction of Stereohaptics toolkit, its main components, actuators and tools. (5 min) • Hands on activity: setup audio systems on personal laptop and familiarity with various haptic technologies. (30 min) • Introduction to haptic illusions and playing with its control parameters and exploring locations on the body (20 min.) • Hands on activity: set up sensors and use them to control haptic effects. (20 min) Creative gameplay (1 hours 30 min)

Our toolkit is scalable, 1 )

 1 by utilizing multiple Stereohaptic units in a single framework (Fig 3, left) and 2) by using a multichannel I/O audio device supporting more audio inputs and outputs (Fig 3, right). The Stereohaptics framework is broad and used to create a wide variety of user experiences as shown in Figure 4.

Figure 4 .

 4 Figure 4. Applications of the Stereohaptics framework.

Figure 3 .

 3 Figure 3. Scalability of the Stereohaptics Toolkit (a) multiple Stereohaptics units (left) and (b) Stereohaptics with multiple input-output.


Christian Frisson
email: christian.frisson@umons.ac.be

Thomas Pietrzak
email: thomas.pietrzak@univ-lille1.fr

Siyan Zhao
email: siyanz@andrew.cmu.edu

Zachary Schwemler
email: zschweml@andrew.cmu.edu

Ali Israr
email: israr@disneyresearch.com

WebAudioHaptics: Tutorial on Haptics with Web Audio

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.