Laurent Prévot
email: laurent.prevot@lpl-aix.fr

Jan Gorisch
email: jan.gorisch@lpl-aix.fr

Verbal feedback: Positionning and acoustics of French "ouais" and "oui"

Introduction

Feedback items are among the most frequent forms in dialogue.

Feedback has been described as a crucial ingredient of talk-in-interaction [?, ?, ?] . The instruction giver explains a path that is displayed on his map to the instruction follower whose map does not contain a path [START_REF] Anderson | The HCRC Map Task corpus[END_REF].

Lexical material can be semi-controlled by the landmarks that are displayed on the maps. The material was selected with respect to findings on read speech [START_REF] Astésano | Structural influences on initial accent placement in French[END_REF].

A dialogue evolves between the participants that involves besides descriptions clarifications, clarification requests, feedback, etc.

Several Languages, including Italian, Japanese, Occitan have been recorded in the Map Task situation. French was missing.

The remote condition involves merely the interaction over the auditive channel [START_REF] Bard | Aix Map-Task: A (rather) new French resource for prosodic and discourse studies[END_REF]. Most natural interactions however take place face-to-face. An audio-visual condition was found necessary.

Lexical material

A subset of lexical material from work on elicited speech [START_REF] Astésano | Structural influences on initial accent placement in French[END_REF] is introduced in the names of landmarks.

They concern the role of Initial Accent in syntactic and prosodic structure making in French.

Example: One set of lighthouses at the top of a cliff with tall buoys tilting on a choppy sea (les lumières et les balises vertigineuses: broad adjective scope) and another sketch with lighthouses at sea level and tall buoys (les lumières et les balises vermeilles: narrow adjective scope).

The likelihood of an Initial Accent on "balises" might change with the length of the conjoined nouns or with the syntax, depending on the adjective scope.

Experimental Design

Standard rules of Map Task experiments apply [START_REF] Anderson | The HCRC Map Task corpus[END_REF].

Task: collaborate in order to reproduce on the Instruction Follower's map a route that is pre-printed on the Instruction Giver's version.

Participants may say anything necessary to accomplish their communicative goals.

Remote condition: Participants cannot see each other.

Example on Feedback

Conversational Feedback is the focus of the project CoFee

Verbal feedback, e.g. ouais, that appears in a line of transcription is indicated by ">"

Basic quantitative information

Relative frequency of feedback items per condition.

Conclusions and ongoing work

The Aix Map Task corpus is a resource for speech analysis:

• structured in terms of the selection of lexical items for intonation research

• rich in spontaneity of task-oriented dialogue

Orthographically transcribed and aligned on word level

Ongoing work improves the transcription and adds annotation of visual properties for the analysis of non-verbal feedback.

Duration

  and Number of tokens per condition audio-only face-to-face duration 6608s ≈ 1h50 8287s ≈ 2h18 # tokens 39792 26706

Acknowledgements

This research was supported by two funds: The remote condition was recorded and transcribed thanks to the EU Marie Curie grant HPMF-CT-2000-00623. It was further developed by additional funding from the ANR project "Conversational Feedback": ANR-12-JCJC-JSH2-006-01 (cofee.hypotheses.org). Many thanks to Bernard Teston, Thierry Legou, Noël Nguyen, Cheryl Frenck-Mestre, Mariapaola d'Imperio, Robert Espesser, Louis Seimandi, Annelise Coquillon, Ludovic Jankowski, Alice Turk, Eddie Dubourg, Ziggy Campbell.


Laurent Prevot

Yao Yao

Arnaud Gingold

Bernard Bel

Kam Yiu

Joe Chan

Toward a scary comparative corpus: The Werewolf Spoken Corpus

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

Toward a scary comparative corpus

The Werewolf Spoken Corpus

Laurent Prévot 1 , Yao Yao 2 , Arnaud Gingold

Objectives

• Explore linguistic and cultural variation is non-cooperative multilogue situation (deceptive speech, persuasive speech, competitive speech)

• First step: gather data and check first variables (overlap, turn-taking, amount of speech) variations across speaker situation

Data curation

The Werewolf pilot corpus and its annotations were stored and described so as to allow a wide dissemination

• http://hdl.handle.net/11041/ ortolang-000900

• http://hdl.handle.net/11041/ ortolang-000908).

[3] Jonathan Ginzburg and Raquel Fernández. Action at a distance: the difference between dialogue and multilogue. In Proceedings of DIALOR, volume 5, 2005.

[4] Hayley Hung and Gokul Chittaranjan. The IDIAP wolf corpus: exploring group behaviour in a competitive role-playing game. In Proceedings of the international conference on Multimedia, pages 879-882. ACM, 2010.

Elicitation Protocol

• Role: 2 Werewolf, 6 villagers, 1 game master

• Alternation of night / day phases night: werewolves decide to make disappear a villager (silent)

day: everyone vote to kill someone (discussion phase)

• Game ends when either all villagers or werewolves have been killed

Recording Setting

French side Basic info about a game

• So far 4 games for each language, 7-27 minute per game Actual Speaking Duration (s) # of simultaneous speakers (%),1Hz) Illustration

[ 5 ]

 5 Adam Janin, Don Baron, Jane Edwards, Dan Ellis, David Gelbart, Nelson Morgan, Barbara Peskin, Thilo Pfau, Elizabeth Shriberg, Andreas Stolcke, et al. The icsi meeting corpus. In Acoustics, Speech, and Signal Processing, 2003. Proceedings.(ICASSP'03). 2003 IEEE International Conference on, volume 1, pages I-364. IEEE, 2003.

  1 , Bernard Bel 1 , Kam Yiu Joe Chan 2 1 Aix Marseille Université, Laboratoire Parole et Langage, France 2 The Hong Kong Polytechnic University, Chinese and Bilingual Studies, Hong Kong

	Context
	• dilogue and multilogue differ significantly
	in terms of dialogue structure [3]
	• Not much multilogue corpora available
	• No comparable multilogue corpus avail-
	able, see however [4] for English
	• Existing multilogues [1, 5, 2] have been
	created within cooperative communicative
	situation
	• Not much quantitative / systematic study
	of cross-linguistic / intercultural variation
	of this kind of natural data

• More theoretically: how different sources of variation blends within actual perfomances

; Record and analyse a comparable corpus of Werewolf social game in France and in Hong Kong.

Acknowledgements

This work has been carried out thanks to the support of the A*MIDEX Variamu project (ANR-11-IDEX-0001-02), the Ortolang (ANR-11-EQPX-0032) French Government program and of the Faculty of Humanities of The Hong Kong Polytechnic University. We would like to thank all the students in Aix and Hong-Kong that participated in the recordings and in the transcription.


Manjesh K Hanawal
email: mhanawal@inria.fr

Eitan Altman
email: eitan.altman@inria.fr

Rajesh Sundaresan
email: rajeshs@ece.iisc.ernet.in

Game Theoretic Analysis of Collusions in Nonneutral Networks

This paper studies the impact of exclusive contracts between a content provider (CP) and an internet service provider (ISP) in a nonneutral network. We consider a simple linear demand function for the CPs. We study when an exclusive contract is beneficial to the colluding pair and evaluate its impact on the noncolluding players at equilibrium. For the case of two CPs and one ISP we show that collusion may not always be beneficial. We derive an explicit condition in terms of the advertisement revenues of the CPs that tells when a collusion is profitable to the colluding entities.

INTRODUCTION

Recently there were several debates to allow internet service providers (ISP) to charge content providers (CPs) for providing the last mile connectivity. The proponents of network neutrality are in favor of the current neutral network where CPs do not pay ISP for connectivity to the end users. This neutrality principle also meant that packets could not be discriminated according to their origin or destination, the application, or the protocol they use.

Those opposing the neutrality argue that (i) some applications (such as peer-to-peer (P2P) streaming applications) require costly resources, and (ii) if a neutral policy is pursued, there would be no incentive for investing in the infrastructure of the network in order to upgrade it. In a nonneutral network, discrimination of packets can mean a selective blocking of packets, selective throttling of flows (allocating less throughput to some flows), preferential treatment coming from exclusive agreements between the access provider and some content or service providers, and discriminatory of charging. For detailed discussion on the network neutrality debate see [START_REF] Musacchio | A two-sided market analysis of provider investment incentives with an application to the net-neutrality issue[END_REF], [START_REF] Altman | Net neutrality and quality of service[END_REF] and the references therein.

In this paper we consider the nonneutral regime where ISP can charge the CPs. This regime can prompt the CPs to make an exclusive agreement with ISP to get a preferential treatment for their content. However, a CP and an ISP will be willing to consider an agreement only if it leads to improvement in their revenues. Such collusions were studied in the context of routing games [START_REF] Hayrapetyan | The effect of collusion in congestion games[END_REF]- [START_REF] Altman | Revisiting Collusion in Routing Games: a Load Balancing Problem[END_REF]. It is often observed in * The work of the two first authors was supported by the ECOSCELL ANR project. The third author was supported by the Indo-French Centre for Promotion of Advanced Research (IFCPAR), Project No. 4000-IT-A.

Copyright is held by author/owner(s). these networks that the subset of players that collude may end up with a worse performance than without collusion, and can also degrade the social performance. To capture this degradation or improvement in social performance a metric called price of collusion is proposed in [START_REF] Hayrapetyan | The effect of collusion in congestion games[END_REF]. Extending this line of thought several other performance metrics related to collusion were proposed in [START_REF] Altman | Revisiting Collusion in Routing Games: a Load Balancing Problem[END_REF] to quantify the effect of collusion on those involved in the collusion and those are not involved. We use these performance metrics to study the effect of collusion in nonneutral network. The paper is organized as follows. In Section 2 we introduce the model for the nonneutral network with multiple CPs. In Section 3 we allow an exclusive contract between a CP and ISP and establish existence of equilibrium. Section 4 quantifies the impact of collusion on the colluding and the noncolluding players. Finally, we end with concluding remarks and a brief discussion on ongoing work in Section 5. The recipe of the proofs is same as those in [START_REF] Altman | Nonneutral network and the role of bargaining power in side payments[END_REF].

MODEL AND PRIOR WORK

In [START_REF] Altman | Nonneutral network and the role of bargaining power in side payments[END_REF] we proposed a simple model to capture interaction between a single ISP and a CP and extended it to include several CP's. The model with multiple CPs is as follows. Several groups of internauts wish to access content from CPs. There is one CP per internaut group. All their access requests go through the ISP. The CPs and the ISP charge the internauts for access. In addition, the CPs get additional revenue from advertisers. The ISP has a known bargaining power when negotiating payment with a CP. See Fig. 1 The revenue per unit demand of CP i, given by

p c i + p a i -p d i . rISP,i
The revenue per unit demand of ISP coming from content provided by CP i, given by p s i +p d i .

UISP

The revenue or utility of the ISP, given by

∑ i di(p s , p c )(p s i + p d i ).

UCP,i

The revenue or utility of the CP, given by di(p s , p c )(

p c i + p a i -p d i ).
The case of a single-CP and single-ISP was quite easy [START_REF] Altman | Nonneutral network and the role of bargaining power in side payments[END_REF]. The demand was a function of the sum of the CP and ISP prices, and decreased linearly with the sum. In the multiple-CP single-ISP case, there was a possibility of positive correlation in demand for a particular CP's content with respect to other contents' prices. See [START_REF] Altman | Nonneutral network and the role of bargaining power in side payments[END_REF] for details. The demand can be summarised as follows.

As in [START_REF] Altman | Nonneutral network and the role of bargaining power in side payments[END_REF]- [START_REF] Altman | Nonneutral network and the role of bargaining power in side payments[END_REF], we write

p s = (p s 1 , p s 2 , • • • , p s n ) and p c = (p c 1 , p c 2 , • • • , p c n )
to denote the price set by the ISP and CPs respectively. The vector p = p s + p c denotes the total price charged to the internauts. The positive correlation in demand with respect to others' prices was modeled via

di(p s , p c ) =   D0 -α(p s i + p c i ) + β ∑ j:j̸ =i (p s j + p c j )   (1)
provided each of the demands are strictly positive. Here α > 0, and β > 0 is the sensitivity parameter for the increase in demand for CP i content per unit increase in price of CP j's content, for j ̸ = i. When the prices p s and p c are constrained to lie in the region of strictly positive demand for all contents, i.e., di(p s , p c ) > 0 for all i = 1, 2 • • • , n, we can write the demand vector compactly as

D0En -An(p s + p c ) > 0, ( 2
)
where An is a matrix of size n×n with diagonal elements as α and off-diagonal elements as -β, and En is a column matrix of size n × 1 with all elements equal to 1. We further argued in [START_REF] Altman | Nonneutral network and the role of bargaining power in side payments[END_REF] that for the total demand to be negatively correlated with the average price per unit demand ∑ n i=1 (p s i + p c i )/n, we must have (n -1)β ≤ α. This assumption also resulted in the concavity of the utility of the ISP in p s . We continue to make this assumption in this paper.

As before we assume that p s i and p c i can be negative, i.e., the ISP and CP can pay the internauts for their patronage, with a consequent increase in demand. While (1) was good so long as all the demands were strictly positive, the positive correlation in di with respect to pj disappears as soon as dj equals zero. Further increase in the price of CP j content keeps dj at zero, there is no freeing of ISP capacity, and consequently no increase in demand di, i.e., positive correlation disappears. This subtlety required a refinement of the demand function which was studied [START_REF] Altman | Nonneutral network and the role of bargaining power in side payments[END_REF].

In [START_REF] Altman | Nonneutral network and the role of bargaining power in side payments[END_REF] we considered a game between ISP and CP with the following sequence of actions.

• The ISP bargains with each of the CPs, separately and simultaneously, over the payment p d from the CP to the ISP. This can be positive or negative. In bargaining with CP i, the ISP shall bring only that revenue into consideration which is generated by internauts connected to CP i.

• All the CPs choose their price p c i . The ISP chooses the vector p s . All these actions are taken simultaneously.

• The internauts react to the prices and set their demands as per the discussion in the previous subsection.

We analyzed this game of n + 1 players, derived the equilibrium prices and the equilibrium demand. Our aim in the current work is to extend the analysis to the case when some of the players collude by means of an exclusive contract.

EXCLUSIVE CONTRACT

Suppose now that one of the CP makes an exclusive contract with the ISP. The ISP and the colluding CP make a joint decision on the price charged to the internauts. This situation also arises when the ISP himself provides content. Without loss of generality assume that CP 1 makes an exclusive contract with the ISP, i.e., and together they decide the price p s 1 + p c 1 to charge from user group 1. The total revenue obtained by CP 1 together with ISP is p s 1 + p c 1 + p a 1 which they share among themselves in some mutually agreed fashion. We denote the colluding pair as ISP and their utility U ISP . Recall that p d 1 denotes the price that CP 1 will pay to the ISP. Because of exclusive contract this price does not affect U ISP . The utility of each of the n players is as follows:

U ISP (p s 1 + p c 1 , p s 2 , • • • , p s n , p c 2 , • • • , p c n ) = [D0 -α(p s 1 + p c 1 ) + β ∑ j̸ =1 (p s j + p c j )](p s 1 + p c 1 + p a 1 ) + ∑ i̸ =1 [D0 -α(p s i + p c i ) + β ∑ j̸ =i (p s j + p c j )](p s i + p d i ), (3)
and for i = 2, 3,

• • • , n, UCP,i(p s 1 + p c 1 , p s 2 , • • • , p s n , p c 2 , • • • , p c n ) = [D0 -α(p s i + p c i ) + β ∑ j̸ =i (p s j + p c j )](p c i + p a i -p d i ). ( 4
)
It is easy to verify that U ISP is a concave function of p s :=

(p s 1 + p c 1 , p s 2 , • • • , p s n ) for a given p a := (p a 1 , p a 2 , • • • , p a n ) and p d := (p d 2 , p d 3 , • • • , p d n )
, and for each for i = 2, 3, • • • , n, UCP,i is a concave function p c i . Indeed, Hessian matrix of U ISP is -2An which is negative definite. For notational convenience we write X = (An-1 + 2αIn-1) -1 and µ = 2α -2β 2 (n -1)/(α -(n -2)β). The following theorem establish the existence of equilibrium prices and some of its properties.

Theorem 1. Assume α > (n -1)β and consider the case when CP 1 enters into an exclusive contract with the ISP. Among the profiles with strictly positive demand, a strictly pure strategy Nash equilibrium exists if and only if

D0En -

[ -α/2 + β 2 /2E T XE + βαE T X β/2E -β/2An-1E -αAn-1X ] - D0 [ α 2(α-(n-1)β) -βE T XE -β(β + α)/µE T A -1 n-1 E -β 2(α-(n-1)β) + (β + α)/µE + An-1XE/2
] is made up of strictly positive entries: Further the equilibrium prices satisfy the following properties

• The equilibrium is unique upto free choice of p d ,

• The equilibrium prices are

p s 1 + p c 1 = -p a 1 2 + D0 2(α -(n -1)β) , ( 5
)
for i = 2, 3, . . . , n,

p s i = gi -p d i and p c i = hi + p d i , ( 6
)
where constants gi and hi depends only on p a , D0, α, β

• The demand vector, the revenue per unit demand and therefore the total revenues collected by ISP and CP does not depend on p d .

Remarks: 1) From ( 5), the equilibrium price of the colluding pair depends on only its advertisement revenues and is independent of other price quantities. As the number of CPs increase, the colluding pair charges a higher price from its internauts at equilibrium. 2) p d has no influence on internaut's per unit demand price. We may have anticipated this given our previous observation of influence of p d on internaut's price when there was no exclusive contract (See [5][Thm. 3]).

With the expressions for the equilibrium prices we proceed to analyze how a collusion between the ISP and a CP affects their own payoff and that of the noncolluding CP's. For simplicity we restrict attention to two CP's.

PRICE OF COLLUSION

In this section we study the impact of a single collusion formed between a CP 1 and ISP. We may study this as game with two players, the super ISP denoted ISP consisting of CP 1 and the ISP as player 1 and CP 2 as player 2. Let U ISP and UCP,2 denote the utility of the colluding pair and that of the noncolluding player respectively in the game with a single coalition.

In the case when there is indeed a collusion between CP 1 and the ISP, straightforward simplification of the equilibrium prices evaluated in Theorem 1 can be shown to yield the following prices for the two CP case [START_REF] Altman | Nonneutral network and the role of bargaining power in side payments[END_REF].

  p s 1 + p c 1 p s 2 p c 2   =   0 -1/2 0 -1 τ /6 1/3 1 -τ /3 -2/3   •   p d 2 p a 1 p a 2   + D0 6α   3/(1 -τ ) (2 + τ )/(1 -τ ) 2   , (7)
where τ = β/α and τ ∈ [0, 1). Then the net price per unit demand on the internauts is given by

[ p s 1 + p c 1 p s 2 + p c 2 ] = [ -1/2 0 -τ /6 -1/3 ] • [ p a 1 p a 2 ] + D0 6α(1 -τ ) [ 3 (4 -τ ) ] , (8)
and thus p d 2 has no influence on the internauts' equilibrium price per unit demand. For the case of no exclusive contract we computed the equilibrium prices for the positive demand in [START_REF] Altman | Nonneutral network and the role of bargaining power in side payments[END_REF], which we recall below

p s = -p d + 1 3(1 -τ 2 /9) [ 1 τ /3 τ /3 1 ] p a + D0 3α(1 -τ )(1 -τ /3) E2, ( 9
)
p c = p d - 2 3(1 -τ 2 /9) [ 1 τ /3 τ /3 1 ] p a + D0 3α(1 -τ /3) E2. ( 10
)
This resulted in the following internauts prices

[ p s 1 + p c 1 p s 2 + p c 2 ] = - 1 3(1 -τ 2 /9) [ 1 τ /3 τ /3 1 ] • [ p a 1 p a 2 ] + 2D0(1 -τ /2) 3α(1 -τ )(1 -τ /3) E2. (11)
With the explicit equilibrium prices for the case of exclusive contract and no exclusive contract we can compare utilities in both cases. In particular, we are interested in the following questions:

• Does the colluding pair improve their total revenue by agreeing to cooperate?

• how does this collusion affect the total revenues of the noncolluding player.

In this regard we use two relevant definitions proposed in [START_REF] Altman | Revisiting Collusion in Routing Games: a Load Balancing Problem[END_REF], namely, individual single collusion price (ISCP) and single collusion externality price (SCEP). When there is only one coalition formation ISCP is defined as the ratio of the total utility of the colluding players before and after collusion at equilibrium. Similarly, for a given single collusion SCEP is defined as the ratio of the total utility of the noncolluding players before and after collusion at equilibrium. Let (p s , p c ) and (p s , p c ) denote the equilibrium prices for the cases of no exclusive contract and exclusive contract respectively. In the present case with single coalition denoted by ISP = {ISP, CP1}, the performance metrics ISCP and SCEP are given by

ISCP(ISP) = UISP(p s , p c ) + UCP,1(p s , p c ) U ISP (p s , p c ) , ( 12
) SCEP(ISP) = UCP,2(p s , p c ) UCP,2(p s , p c ) . ( 13
)
Using equilibrium prices in ( 7)-(8) the utilities in the case of exclusive contract can be directly computed. After simple manipulation they can be written as

U ISP = ( D0(3 + τ ) 6 + αp a 1 (3 -τ 2 ) 6 - βp a 2 3 ) • ( p a 1 2 + D0 2α(1 -τ ) ) + ( D0 3 - αp a 1 τ 3 + α p a 2 3 ) • ( p a 1 τ 6 + p a 2 3 + D0(2 + τ ) 6α(1 -τ )
) ,( 14)

UCP,2 = α ( D0 3α + p a 2 3 -p a 1 (τ /3) ) 2 . ( 15
)
Similarly, using equilibrium prices in (9)-(11) the utilities in the case of no exclusive contract can be computed as

UISP + UCP = ( D0 3 -τ + α (9 -τ 2 ) ( -2p a 1 τ + (3 -τ 2 )p a 2 ) ) • ( p a 1 τ + 3p a 2 (9 -τ 2 ) + D0 α(1 -τ )(3 -τ ) ) + ( D0 3 -τ + α (9 -τ 2 ) ( -2p a 2 τ + (3 -τ 2 )p a 1
) )

• ( p a 1 (6 -τ 2 ) -p a 2 (τ ) (9 -τ 2 ) + 2D0(2 -τ ) α(1 -τ )(3 -τ ) ) , ( 16
) UCP,2 = α ( D0 α(3 -τ ) + 1 (9 -τ 2 ) ( (3-τ 2 )p a 2 -2τ p a 1 ) ) 2 . ( 17
)
We first evaluate the impact of collusion between ISP and CP 1 on the noncolluding pair. By comparing (15) and ( 17) the following observation is immediate.

Proposition 2. SCEP(ISP) ≥ 1 if and only if

p a 2 ≤ 3 -τ 2 2τ p a 1 + D0(3 + τ ) α(2τ ) . ( 18
)
Thus if the advertisement revenues (p a 1 , p a 2 ) satisfies the relation (18) CP 1 going for an exclusive contract will lead the noncolluding CP to incur loss.

Remarks: 1) In [START_REF] Altman | Nonneutral network and the role of bargaining power in side payments[END_REF], we observed that when (18) holds both the user group pay less per unit demand. Hence though the collusion between ISP and CP 1 hurts the noncolluding CP it benefits the internauts.

2) It is a simple to verify that under the condition (18) collusion results in the reduction of demand from CP 2.

To compare the performance of the colliding pair we evaluate ISCP(ISP) by dividing ( 16) by ( 14). ISCP(ISP) is shown in Figure 2. In this figure we observe that colluding pair benefits if (18) holds. However, if the condition (18) is not satisfied, then the colluding pair are not gaining compared to the case of no collusion. Thus making an exclusive contract is not always beneficial. This observation is made in several earlier work in the context of routing games, for example see [START_REF] Altman | Revisiting Collusion in Routing Games: a Load Balancing Problem[END_REF]. Further, collusion always hurts one of the player, colluding pair or noncolluding player unless equality holds in (18).

CONCLUSION AND FUTURE WORK

We considered a nonneutral network in which ISP can charge the CPs for connecting them to the end users. In such networks we studied the case where a CP can collude with the ISP by making an exclusive contract. In this contract the colluding pair maximize the sum of their utility. We showed that such collusion may not be beneficial to the colluding pair. They will benefit if the advertisement revenue of the noncolluding ISP is low. Otherwise, they will not benefit but the noncolluding will improve its revenues.

In future, we plan to consider other forms of cooperation between a CP and the ISP. An example is the Nash bargaining solution in which the colluding pair try to maximize the product of their utilities or the α-fair sum of their utilities [START_REF] He | Pricing and revenue sharing strategies for internet service providers[END_REF].

Figure 1 :

 1 Figure 1: Monetary flow in a nonneutral network with multiple CPs.

Figure 2 :

 2 Figure 2: Individual Single collusion price for ISP

  for a payment flow diagram. The parameters of this game are given in the following table.

	Parameter Description
	n	Number of content providers.
	p s i	Price per unit demand paid by the users to the
		ISP for connection to CP i. This can be posi-
		tive or negative.
	p c i	Price per unit demand paid by the users to CP
		i. This too can be positive or negative.
	p a i	Advertising revenue per unit demand, earned by the CP. This satisfies p a i ≥ 0.
	p d i	Price per demand paid by the CP to the ISP.
		This can be either positive or negative.
	p x	Vectors of aforementioned prices, where x is
		one of s, c, a, d.
	di(p s , p c )	Demand for CP i as a function of the prices.
		See (1) below and the following discussion.
	rCP,i


L Grammont

M Ahues

H Kaboul

An Extension of the Product Integration Method to L 1 with Applications in Astrophysics

Keywords:

We consider a Fredholm integral equation of the second kind in L 1 ([a, b], C), with a weakly singular kernel. Sufficient conditions are given for the existence and uniqueness of the solution. We adapt the product integration method proposed in C 0 ([a, b], C) to apply it in L 1 ([a, b], C), and discretize the equation. To improve the accuracy of the approximate solution, we use different iterative refinement schemes which we compare one to each other. Numerical evidence is given with an application in Astrophysics.

Introduction

We consider a Banach space X. Let T be the integral operator defined by [START_REF] Ahues | An L 1 ([a, b], C) refined projection approximate solution of the radiation transfer equation in stellar atmospheres[END_REF] ∀x ∈ X, ∀s ∈ [a, b], T x(s) := b a L(s, t)H(s, t)x(t)dt, where (s, t) → H(s, t) is not smooth. For z in the resolvent set of T , re(T ), and y in X we consider the Fredholm integral problem of the second kind [START_REF] Ahues | Iterative refinement schemes for an ill-conditioned transfer equation in astrophisics[END_REF] Find ϕ ∈ X s.t. (T -zI)ϕ = y, where I denotes the identity operator on X.

To approximate the solution of this equation, we define a finite rank approximation T n of T , so that the approximate equation (T n -zI)ϕ n = y or (T n -zI)ϕ n = y n , where y n is an approximation of y, be uniquely solvable and the sequence of approximate solutions ϕ n converges to the exact solution ϕ when n tends to +∞.

Among them, different classes of methods rely on a sequence of projections π n converging pointwise to the identity operator I. For example the Galerkin operator is defined by T n = π n T π n , the projection operator by T n = π n T , the Sloan operator by T n = T π n and the Kulkarni operator by T n = T π n + π n T -π n T π n (see [START_REF] Atkinson | The Numerical Solution of Integral Equations of the Second Kind[END_REF], [START_REF] Kulkarni | A Superconvergence result for solutions of compact operator equations[END_REF]). These approximations of T are all ν-convergent to T (see [START_REF] Ahues | Spectral Computations for Bounded Operators[END_REF]). This property ensures existence and uniqueness of ϕ n , and convergence to ϕ.

In the case of the space X := C 0 ([a, b], C) methods based upon numerical quadrature have been proposed, such as Nyström, truncated Nyström and subtraction of the singularity approximations (see [START_REF] Anselone | Singularity substraction in the numerical solution of integral equations[END_REF]).

In C 0 ([a, b], C), we also encounter the so-called product integration method (see [START_REF] Atkinson | The Numerical Solution of Integral Equations of the Second Kind[END_REF]). In this space, the assumptions are as follows: If h n := b -a n , then t n,i = a + ih n , for i = 0, 1, . . . , n.

For x ∈ C 0 ([a, b], C) and s ∈ [a, b], the linear interpolation scheme is given by t → [L(s, t)x(t)] n := 1 h n [(t n,i -t)L(s, t n,i-1 )x(t n,i-1 ) + (t -t n,i-1 )L(s, t n,i )x(t n,i )] ,

for i = 1, . . . , n, and t ∈ [t n,i-1 , t n,i ].

T n is defined by replacing L(s, t)x(t) with [L(s, t)x(t)] n in [START_REF] Ahues | An L 1 ([a, b], C) refined projection approximate solution of the radiation transfer equation in stellar atmospheres[END_REF].

In this method T n is a bounded finite rank linear operator defined in C 0 ([a, b], C) and hence it is compact. Under hypotheses (H1) and (H2), for z ∈ re(T ) and for n large enough, T n -zI is invertible and its inverse is uniformly bounded, (see [START_REF] Atkinson | The Numerical Solution of Integral Equations of the Second Kind[END_REF]).

In this paper we extend the product integration method to the space X := L 1 ([a, b], C). It will appear that the properties of the method in

C 0 ([a, b], C) are preserved in L 1 ([a, b], C).
In Section 2, we present our method and we prove the existence and uniqueness of the approximate solution and its convergence to the exact solution.

Section 3 is devoted to the numerical implementation of our algorithm. The choice of the integer n is limited by the capacity of the computer. The linear system to be solved is of the order of n. So, it is interesting to improve the accuracy of the approximate solution by applying some iterative refinement schemes.

Section 4 is devoted to these schemes.

In Section 5, we test our approximation with an academic example.

In Section 6, we apply our method to a problem belonging to Astrophysics. Our method is compared with the projection method proposed by Titaud in [START_REF] Ahues | An L 1 ([a, b], C) refined projection approximate solution of the radiation transfer equation in stellar atmospheres[END_REF] and [START_REF] Titaud | Analyse et Résolution Numérique de L'Equation de Transfert[END_REF].

2 Main result: The product integration method in

L 1 ([a, b], C)
We use the following notations: • The modulus of continuity of a continuous function on [a, b] is defined as

• The norm in L 1 ([a, b], C) is denoted
(5) w(x, h) := sup u,v∈[a,b],|u-v|≤|h| |x(u) -x(v)|.
• The modulus of continuity of a continuous function on

[a, b] × [a, b] is defined as (6) w 2 (f, h) := sup u,v∈[a,b] 2 , u-v ≤|h| |f (u) -f (v)|. If x ∈ L 1 ([a, b], C) then (7) lim h-→0 w 1 (x, h) = 0. If x ∈ C 0 ([a, b], C) then (8) lim h-→0 w(x, h) = 0. If f ∈ C 0 ([a, b] 2 , C) then (9) lim h-→0 w 2 (f, h) = 0.
The aim of this section is to define the approximate operator T n . The approximate solution of (2) will be, if it exists and is unique, the solution ϕ n of ( 10)

(T n -zI)ϕ n = y.
T n is constructed so that ϕ n -→ ϕ. It is well known that a collectively compact convergence of T n towards T guarantees the convergence of ϕ n towards ϕ.

Let us recall the collectively compact convergence :

Definition 1 T n and T are bounded linear operators from X into X.

The pointwise convergence, denoted by

T n p -→ T , means that ∀x ∈ X, T n x -T x → 0.
The collectively compact convergence is denoted by

T n cc -→ T : If T is compact T n p -→ T,
and for some positive integer n 0 , the set

W := ∪ n≥n 0 {T n x : x ∈ X, x ≤ 1} is relatively compact in X.
We begin by proving that T is a compact bounded linear operator from L 1 ([a, b], C) into itself. Then we propose an approximate operator T n which is a collectively compact convergent to T . Endly, we give an error estimation for the approximate solution in terms of the kernel, the norm of the exact solution, its oscillation in L 1 ([a, b], C) and the mesh size.

The proof of the compactness in L 1 ([a, b], C) relies on the Kolmogorov-Riesz-Fréchet theorem which is recalled here below.

As usual, if A is a set of functions, we define

A| Ω := {f | Ω : f ∈ A},
where f | Ω is the restriction of f to the subdomain Ω.

Theorem 1 (Kolmogorov-Riesz-Fréchet Theorem) Let F be a bounded set in

L p (R q , C), 1 ≤ p < ∞. If (11) lim h →0 τ h f -f p = 0 uniformly in f ∈ F, where
τ h f := f (. + h),
then the closure of F| Ω is compact in L p (Ω, C) for any measurable set Ω ⊂ R q with finite measure.

Proof : See [START_REF] Brezis | Functional Analysis, Sobolev Spaces and Partial Differential Equations[END_REF]. As one finds a lot of different versions of this theorem in the litterature, we propose a proof of it in the Appendix in the case q = 1, p = 1 and Ω = [a, b].

Now, the assumptions are as follows:

(P1) L ∈ C 0 ([a, b] × [a, b], C). Let c L := sup (s,t)∈[a,b] 2 |L(s, t)|.
(P2) H verifies:

(P2.
Proof : For h > 0, 0 ≤ b b-h |H(s, t)|ds ≤ b b-h | H(s + h, t) -H(s, t)|ds ≤ b a | H(s + h, t) - H(s, t)|ds ≤ w H (h).

Proof :

For all x ∈ L 1 ([a, b], C),

T x 1 = b a | b a L(s, t)H(s, t)x(t)dt|ds ≤ b a b a |L(s, t)||H(s, t)||x(t)|dtds ≤ c L b a |x(t)| b a |H(s, t)|dsdt ≤ c L c H x 1 , so T is defined from L 1 ([a, b], C) into itself.
The proof of the compactness of T relies on the Kolmogorov-Riesz-Fréchet theorem where p = 1, q = 1 and Ω = [a, b].

We introduce the operator T given by

T x(s) := T x(s) for s ∈ [a, b], 0 for s / ∈ [a, b].
Let A and S be the following subsets of L 1 (R, C) and L 1 ([a, b], C) respectively:

A := { T x : x ∈ L 1 ([a, b], C), x 1 ≤ 1}, S := {T x : x ∈ L 1 ([a, b], C), x 1 ≤ 1}. A is a bounded subset of L 1 (R, C). Indeed T x 1 = T x 1 ≤ c L c H x 1 ≤ c L c H . Let us prove that lim h→0 τ h f -f 1 = 0 uniformly in f ∈ A.
For h > 0,

τ h T x -T x 1 = b a | T x(s + h) -T x(s)|ds = b-h a |T x(s + h) -T x(s)|ds + b b-h |T x(s)|ds. Hence b b-h |T x(s)|ds = b b-h | b a L(s, t)H(s, t)x(t)dt|ds ≤ c L x 1 (H, h) ≤ c L (H, h), and b-h a |T x(s + h) -T x(s)|ds = b-h a | b a L(s + h, t)H(s + h, t) -L(s, t)H(s, t) x(t)dt|ds ≤ b-h a | b a |L(s + h, t)||(H(s + h, t) -H(s, t)||x(t)|dtds + b-h a | b a |H(s, t)||L(s + h, t) -L(s, t)||x(t)|dtds ≤ c L x 1 w H (h) + c H x 1 w 2 (L, h) ≤ c L w H (h) + c H w 2 (L, h). So (14) τ h T x -T x 1 ≤ x 1 (c L w H (h) + c H w 2 (L, h) + c L (H, h)) .
For h < 0, we have similar bounds.

Then

τ h f -f 1 → 0 as h → 0 uniformly in f ∈ A. From the Kolmogorov-Riesz-Fréchet theorem S = A| [a,b] is relatively com- pact so T is compact.
Let us define the approximate operator T n . Let ∆ n be the partition defined by (3). For x ∈ L 1 ([a, b], C), we define the operator

t → Q n (x, s, t) := 1 h n (t n,i -t)L(s, t n,i-1 )+(t-t n,i-1 )L(s, t n,i ) 1 h n t n,i t n,i-1
x(u)du

for i = 1, . . . , n, and t ∈ [t n,i-1 , t n,i ].
The approximate operator T n is given by:

(15) ∀x ∈ L 1 ([a, b], C), ∀s ∈ [a, b], T n x(s) := b a Q n (x, s, t)H(s, t)dt,
which can be rewritten as

(16) T n x(s) = n i=1 c n,i w n,i (s),
where, for i = 1, . . . , n,

c n,i := 1 h n t n,i t n,i-1
x(u)du, and

w n,i (s) := t n,i t n,i-1 Q n (1, s, t)H(s, t)dt.
To prove that T n cc -→ T , the following lemmas are needed.

Lemma 2 For i = 1, . . . , n, b a |w n,i (s)|ds ≤ h n c L c H . (17) For h ∈ R + , b b-h |w n,i (s)|ds ≤ h n c L (H, h), (18) (19) b-h a w n,i (s + h) -w n,i (s) ds ≤ h n c H w 2 (L, h) + h n c L w H (h). Proof : For t ∈ [t n,i-1 , t n,i ], Q n (1, s, t) = 1 h n (t n,i -t)L(s, t n,i-1 ) + (t -t n,i-1 )L(s, t n,i ) |Q n (1, s, t)| ≤ c L h n |t n,i -t| + |t -t n,i-1 | = c L . Hence, by Fubini's theorem b a |w n,i (s)|ds ≤ c L b a t n,i t n,i-1 |H(s, t)|dtds, ≤ c L h n c H , and b b-h |w n,i (s)|ds ≤ c L b b-h t n,i t n,i-1 |H(s, t)|dtds, ≤ c L h n (H, h). Also b-h a w n,i (s + h) -w n,i (s) ds ≤ b-h a t n,i t n,i-1 Q n (1, s + h, t)H(s + h, t) -Q n (1, s, t)H(s, t)dt d ≤ b-h a t n,i t n,i-1 (Q n (1, s + h, t) -Q n (1, s, t))H(s + h, t) dtds + b-h a t n,i t n,i-1 Q n (1, s, t)(H(s + h, t) -H(s, t)) dtds ≤ h n w 2 (L, h) sup t∈[a,b] b a H(s, t) ds +c L h n sup t∈[a,b] b-h a ( H(s + h, t) -H(s, t) ds ≤ h n c H w 2 (L, h) + h n c L w H (h).
This ends the proof.

Lemma 3 For x ∈ L 1 ([a, b], C), (20)
n i=1 t n,i t n,i-1 |x(u) -c n,i |du ≤ 2w 1 (x, h n ),
where

w 1 (x, h n ) is defined by (4). For t ∈ [a, b], (21)
Q n (1, s, t) -L(s, t) ≤ w 2 (L, h n ).
Proof :

For i = 1, . . . , n, t n,i t n,i-1 |x(u) -c n,i |du ≤ 1 h n t n,i t n,i-1 t n,i t n,i-1 |x(u) -x(v)|dvdu = 2 h n t n,i t n,i-1 t n,i v |x(u) -x(v)|dudv = 2 h n t n,i t n,i-1 t n,i -v 0 |x(τ + v) -x(v)|dτ dv ≤ 2 h n t n,i t n,i-1 hn 0 |x(τ + v) -x(v)|dτ dv ≤ 2 h n hn 0 t n,i t n,i-1 |x(τ + v) -x(v)|dvdτ.
Hence

n i=1 t n,i t n,i-1 |x(u) -c n,i |du ≤ 2 h n hn 0 b a |x(τ + v) -x(v)|dvdτ ≤ 2 sup τ ∈[0,hn] t n,i t n,i-1 |x(τ + v) -x(v)|dv = 2w 1 (x, h n ).
For i = 1, . . . , n, and t ∈ [t n,i-1 , t n,i ],

Q n (1, s, t) -L(s, t) ≤ 1 h n (t n,i -t)( L(s, t n,i-1 ) -L(s, t) ) + (t -t n,i-1 )( L(s, t n,i ) -L(s, t)) (22) ≤ sup s∈[a,b] w(L(s, .), h n ) 1 h n (t n,i -t) + (t -t n,i-1 ) (23) ≤ w 2 (L, h n ), (24)
and the proof is complete.

Theorem 3 T n is a compact linear operator from L 1 ([a, b], C) into itself and T n cc -→ T. Proof : Due to (17) in Lemma 2, for x ∈ L 1 ([a, b], C), T n x 1 ≤ c L c H x 1 so T n is a linear bounded operator from L 1 ([a, b], C) into itself. As T n is a linear bounded operator of finite rank, it is compact. Let us prove that T n p -→ T . Lemma 3 implies that T n x -T x 1 = b a n i=1 c n,i t n,i t n,i-1 Q n (1, s, t)H(s, t)dt - b a L(s, t)H(s, t)x(t)dt ds = b a n i=1 t n,i t n,i-1 c n,i Q n (1, s, t) -L(s, t)x(t) H(s, t)dt ds = b a n i=1 t n,i t n,i-1 Q n (1, s, t) -L(s, t) x(t) +Q n (1, s, t) c n,i -x(t) H(s, t)dt ds ≤ b a n i=1 t n,i t n,i-1 Q n (1, s, t) -L(s, t) |x(t)||H(s, t)|dtds + b a n i=1 t n,i t n,i-1 |Q n (1, s, t)||c n,i -x(t)||H(s, t)|dtds ≤ c H x 1 w 2 (L, h n ) + c H c L n i=1 t n,i t n,i-1 |c n,i -x(t)|dt ≤ c H x 1 w 2 (L, h n ) + 2c H c L w 1 (x, h n ).

Hence (25)

T

n x -T x 1 ≤ c H x 1 w 2 (L, h n ) + 2c H c L w 1 (x, h n ).
So we have T n p -→ T . To prove the relatively compactness of S n := {T n x : n ≥ 1, x ∈ L 1 ([a, b], C), x 1 ≤ 1} we follow the same scheme as in the proof of the compactness of T . We define the operator

Tn x(s) := T n x(s) for s ∈ [a, b], 0 for s / ∈ [a, b],
and A n as the following subset of L 1 (R, C)

A n := { Tn x : x ∈ L 1 ([a, b], C), x 1 ≤ 1}.
A n is a bounded subset of L 1 (R, C). Indeed, (26)

Tn x 1 = T n x 1 ≤ c L c H x 1 ≤ c L c H .
Let us prove that lim

h→0 τ h f -f 1 = 0 uniformly in f ∈ A n .
For h > 0,

τ h Tn x -Tn x 1 = b a | Tn x(s + h) -Tn x(s)|ds = b-h a |T n x(s + h) -T n x(s)|ds + b b-h |T n x(s)|ds.
Hence, by (18

) in Lemma 2, b b-h |T n x(s)|ds ≤ n i=1 |c n,i | b b-h |w n,i (s)|ds ≤ 1 h n x 1 h n c L (H, h) ≤ c L (H, h),
and because of (19

) in Lemma 2, b-h a |T n x(s + h) -T n x(s)|ds ≤ b-h a n i=1 c n,i w n,i (s + h) -w n,i (s) ds ≤ n i=1 c n,i (h n c H w 2 (L, h) + h n c L w H (h)). ≤ x 1 (c H w 2 (L, h) + c L w H (h)) ≤ c H w 2 (L, h) + c L w H (h).

Hence (27)

τ h Tn x -Tn x 1 ≤ x 1 (c H w 2 (L, h) + c L w H (h) + c L (H, h)) .
For h < 0, we have similar bounds.

Then

τ h f -f 1 → 0 as h → 0 uniformly in f ∈ A n . From the Kolmogorov-Riesz-Fréchet theorem, A n | [a,b] is relatively compact so T n cc -→ T.
Proposition 1 Let z ∈ re(T ). For n large enough, T n -zI is invertible and it exists a positive number c z > 0 such that

(28) (T n -zI) -1 1 ≤ c z .
Proof : It is a consequence of the collectively compact convergence (see [START_REF] Anselone | Collectively Compact Operator Approximation Theory and Application to Integral Equations[END_REF]).

Theorem 4 For z ∈ re(T ), and under hypotheses (P1) and (P2), for n large enough, the approximate operator equation ( 10) has a unique solution ϕ n satisfying the following error bound:

(29) ϕ -ϕ n 1 ≤ c z c H ( ϕ 1 w 2 (L, h n ) + 2c L w 1 (ϕ, h n )) .
Proof : According to (25) in the proof of Theorem 3,

ϕ -ϕ n ≤ (T n -zI) -1 1 (T -T n )ϕ 1 ≤ c z c H ( ϕ 1 w 2 (L, h n ) + 2c L w 1 (ϕ, h n )) ,
which ends the proof.

Remark

Often in practice, the kernel H is of convolution type. Let us fix a = 0 and b = 1. We suppose that there is a function g such that

H(s, t) = g(|s -t|)
where g is a weakly singular function defined on ]0, 1]. This means that g satisfies the following properties:

(30) lim s→0 + g(s) = +∞ (31) g ∈ C 0 (]0, 1], R) ∩ L 1 ([0, 1], R) (32)
g ≥ 0 and g is a decreasing function in ]0, 1].

Proposition 2 When the factor H in the kernel of the operator T is of weakly singular convolution type, then H verifies all the conditions imposed by the product integration methods.

Proof :

(H2.1) ∀s ∈ [0, 1], we have

1 0 ψ(t)dt = τ 0 ψ(t)dt + ξ τ ψ(t)dt + s ξ ψ(t)dt + 1 s ψ(t)dt = τ 0 ψ(t)dt + 2 ξ τ ψ(t)dt + 1 τ ψ(t)dt = τ 0 g(τ -t) -g(s -t)dt + 2 ξ τ g(t -τ ) -g(s -t)dt + 1 s g(t -s) -g(t -τ )dt = G(τ ) -G(s) + G(s -τ ) + 2G( s -τ 2 ) -2G(s -τ ) +2G( s -τ 2 ) + G(1 -s) + G(s -τ ) -G(1 -τ ) = 4 s-τ 2 0 g(σ)dσ - s τ g(σ)dσ - 1-τ 1-s g(σ)dσ ≤ 4 s-τ 2 0 g(σ)dσ, hence, (33) ω H (h) = sup |s-τ |≤h 1 0 |g(|s -t|) -g(|τ -t|)|dt ≤ 4 h 2 0 g(σ)dσ, so lim h-→0 + ω H (h) = 0. (P2.2) Let us prove that, for h > 0, lim h→0 + sup t∈[0,1] 1 0 |g(|s + h -t|) -g(|s -t|)|ds = 0. For t ∈ [0, 1], 1 0 |g(|s + h -t|) -g(|s -t|)|ds = 1 0 |g(|t -h -s|) -g(|t -s|)|ds, ≤ ω H (h), so lim h-→0 + w H (h) = lim h-→0 + 1 0 |g(|s + h -t|) -g(|s -t|)|ds = 0,
which ends the proof.

Iterative refinement

Recall that z = 0 because T is compact and z ∈ re(T ). Consider that the solution of ( 2) is approximated by G n (z)y, where G n (z) is an approximate inverse of T -zI. The accuracy of G n (z)y may be improved using the following iterative refinement schemes:

x (0) n := G n (z)y, x (k+1) n := x (0) + (I -G n (z)(T -zI))x (k) n . (34)
In [START_REF] Titaud | Analyse et Résolution Numérique de L'Equation de Transfert[END_REF], G n (z) has been one of the following operators : Scheme A (Atkinson):

G n (z) := R n (z) := (T n -zI) -1 , Scheme B (Brakhage): G n (z) := 1 z (R n (z)T -I),
Scheme C (Titaud):

G n (z) := 1 z (T R n (z) -I).
Their convergence properties and error bounds have already been studied in terms of T , T n and R n (z) (see [START_REF] Titaud | Analyse et Résolution Numérique de L'Equation de Transfert[END_REF] pp 40-41). If ϕ is the solution of (2), Scheme A (Atkinson):

x (k) n -ϕ 1 ϕ 1 ≤ R n (z)(T n -T ) k+1 1 ,
Scheme B (Brakhage):

x (k) n -ϕ 1 ϕ 1 ≤ 1 z R n (z)(T n -T )T k+1 1 ,
Scheme C (Titaud):

x (k) n -ϕ 1 ϕ 1 ≤ 1 z T R n (z)(T n -T ) k+1 1 .
Let us state error estimations for these three refinement schemes for the approximate operator T n defined by (15) in this paper.

Theorem 5 For T n defined by (15), the following error bounds are satisfied: Scheme A (Atkinson):

x (2 -1) n -ϕ 1 ϕ 1 ≤ m z E(h n ) , x (2 ) n -ϕ 1 ϕ 1 ≤ 2d z c H c L m z E(h n ) ,
Scheme B (Brakhage):

x (2 -1) n -ϕ 1 ϕ 1 ≤ d z z 2 E(h n ) 2 , x (2 ) n -ϕ 1 ϕ 1 ≤ d z z 2 +1 E(h n ) 2 +1 ,
Scheme C (Titaud):

x (2 -1) n -ϕ 1 ϕ 1 ≤ d z z 2 (2c 2 H c 2 L )E(h n ) 2 -1 , x (2 ) n -ϕ 1 ϕ 1 ≤ d z z 2 +1 (2c 2 H c 2 L )E(h n ) 2 ,
where

(35) E(h n ) := 3c 2 H c L w 2 (L, h n ) + 2c H c 2 L w H (h n ) + 2c H c 2 L (H, h n ), and
m z := 2d 2 z + 2c H c L d 3 z , (36) d z := max(c z , R(z) ). ( 37
)
Proof : Using ( 25) ,

(T -T n )T x ≤ c H T x w 2 (L, h n ) + 2c H c L w 1 (T x, h n ) ≤ c H w 2 (L, h n ) T x + 2c H c L w 1 (T x, h n ). As w 1 (T x, h n ) = sup |u|∈[0,hn] τ u T x -T x 1 ,
and due to ( 14),

(T -T n )T x ≤ c H w 2 (L, h n ) T x + 2c H c L x 1 (c L w H (h n ) + c H w 2 (L, h n ) + c L (H, h n )) ≤ x 1 3c 2 H c L w 2 (L, h n ) + 2c H c 2 L w H (h n ) + 2c H c 2 L (H, h n ) ≤ x 1 E(h n ). Using (25), (T -T n )T n x ≤ c H T n x w 2 (L, h n ) + 2c H c L w 1 (T n x, h n ). As T n x 1 ≤ c L c H x 1 , w 1 (T n x, h n ) = sup |u|∈[0,hn] τ u Tn x -Tn x 1 ,
and because of ( 27),

(T -T n )T n x ≤ c 2 H c L w 2 (L, h n ) x 1 + 2c H c L x 1 (c L w H (h n ) + c H w 2 (L, h n ) + c L (H, h n )) ≤ x 1 3c 2 H c L w 2 (L, h n ) + 2c H c 2 L w H (h n ) + 2c H c 2 L (H, h n ) ≤ x 1 E(h n ). • Scheme A As (T n -T )R n (z)T = (T n -T )R n (z)(T -T n )T R ( z) + (T n -T )T R ( z)
, and according to (28),

R n (z)(T n -T ) 2 = R n (z)(T n -T )R n (z)T n + R n (z)(T n -T )R n (z)T = R n (z)(T n -T )T n R n (z) + R n (z)(T n -T )R n (z)T ≤ c 2 z (T n -T )T n + c z (T n -T )R n (z)(T -T n )T R ( z) + (T n -T )T R ( z) .
We have

R n (z)(T n -T ) 2 ≤ d 2 z (T n -T )T n + 2c H c L d 3 z (T -T n )T + d 2 z (T n -T )T ≤ (2d 2 z + 2c H c L d 3 z )E(h n ) ≤ m z E(h n ). Then R n (z)(T n -T ) 2 1 ≤ m z E(h n ) , so x (2 -1) n -ϕ 1 ϕ 1 ≤ m z E(h n ) , and
x (2 ) n -ϕ 1 ϕ 1 ≤ 2d z c H c L m z E(h n ) . • Scheme B As 1 z R n (z)(T n -T )T 2 1 ≤ d z z 2 E(h n ) 2 , then x (2 -1) n -ϕ 1 ϕ 1 ≤ d z z 2 E(h n ) 2 ,
and

x (2 ) n -ϕ 1 ϕ 1 ≤ d z z 2 +1 E(h n ) 2 +1 . • Scheme C As 1 z T R n (z)(T n -T ) k+1 = 1 z k+1 T R n (z) (T n -T )T R n (z) k (T n -T ), 1 z T R n (z)(T n -T ) k+1 1 ≤ d z z k+1 (2c 2 H c 2 L ) (T n -T )T k 1 ≤ d z z k+1 (2c 2 H c 2 L )E(h n ) k , so x (2 -1) n -ϕ 1 ϕ 1 ≤ d z z 2 (2c 2 H c 2 L )E(h n ) 2 -1 ,
and

x (2 ) n -ϕ 1 ϕ 1 ≤ d z z 2 +1 (2c 2 H c 2 L )E(h n ) 2 .
This concludes the proof.

Remark 1

The upperbound of Scheme B appears to be the optimal one among the three error bounds. It improves slightly upon the one of Scheme C and is twice better than the one of Scheme A.

Numerical Implementations

The approximate equation is

T n ϕ n -zϕ n = y, i.e. ( 38
) ∀s ∈ [a, b], n i=1 w n,j (s) 1 h n t n,j t n,j-1 ϕ n (u)du -zϕ n (s) = y(s).
By calculating the average over [t n,i-1 , t n,i ], i = 1, . . . , n, of each member of the equation, we obtain a linear system of the form (A -zI)x = d, where

A(i, j) := 1 h n t n,i t n,i-1 w n,j (s)ds, i, j = 1, . . . , n, (39)
d(i) := 1 h n t n,i t n,i-1 y(s)ds, i = 1, . . . , n, (40)
x(i) := 1 h n t n,i t n,i-1 ϕ n (s)ds, i = 1, . . . , n. (41)
After solving the linear system, the approximate solution can be written as

ϕ n (s) = 1 z n i=1
w n,j (s)x(i) -y(s) .

To measure the quality of the approximation we calculate the relative residual

r(ϕ n ) := (T -zI)ϕ n -y 1 y 1 .
In practice the evaluation of T is often not possible, so we replace it with T m where m >> n and we caculate the average over [t m,i-1 , t m,i ], i = 1, . . . , m, of (T -zI)ϕ n -y and of y. We obtain two vectors of size m, and we caculate the vector norm in (C m , • 1 ).

Numerical Illustration

As an academic example we have taken

- 1 0 ln(|s -t|)ϕ(t)dt -ϕ(s) = y(s),
with unique solution ϕ(s) = s 2 . The estimations of the relative residual with m = 100 for the projection method proposed by Titaud in [START_REF] Titaud | Analyse et Résolution Numérique de L'Equation de Transfert[END_REF] and the L 1 ([a, b], C) product integration method are shown in Table 1. We observe that the L 1 ([a, b], C) product integration method is faster than the projection method.

n Projection method Integration product method 10 0.0968 0.0246 20 0.0499 0.0087 50 0.0211 0.0018 Table 1: Relative residuals Figure 1 shows the profile of the matrix A defined by (39). It is a full matrix.

In Figure 2 we chose n = 100, m = 1000 for a relative residual tolerance of 10 -12 . We note that Scheme B is the fastest one to reach the tolerance.

The theoretical Remark 1 of Section 3 is confirmed by this numerical experiment.

An Application in Astrophysics

The radiative transfer problem is a system of differential equations coupled with a Fredholm integral equation of the second kind. It describes the energy conserved by a beam radiation traveling, such that a beam of radiation can lose or gain energy through absorbing, scattering and emitting medium. Let τ * be the optical width of the medium, (see [START_REF] Chevallier | Exact results in modeling planetary atmospheres-I. Gray atmospheres[END_REF]). An example of this equation is

(s) 2 τ * 0 E 1 (|s -t|)ϕ(t)dt -ϕ(s) = y(s),
where E 1 is the first integral exponential function: The relative residual associated to the approximate solution ϕ n obtained by the projection method and the product integration method proposed in this paper are shown in Table 2. We observe that the product integration method converges faster than the projection method. For n ≥ 100, the computation of ϕ n is prohibitively costly so that we will use the refinement schemes introduced in Section 3 to compute the final approximate solution.

∀ν ≥ 1, E ν (s) := 1
In Figure 4 we chose n = 100, m = 1000 for a relative residual tolerance of 10 -12 . We note that Scheme C is the fastest one to reach the tolerance. This confirms the results obtained in [START_REF] Almeida | A numerical study of iterative refinement schemes for weakly singular integral equations[END_REF].

Remark 2 In this application, Scheme C is apparently faster than Scheme B. This could be explained by the difference between the profiles of the corresponding auxiliary matrices A (see Figure 1 and Figure 3). To simplify the notation, . 1 denotes the norm in L 1 (Ω, C) and also the norm in L 1 (R, C). . ∞ denotes the norm in C 0 (Ω, C) and also the norm in C 0 (R, C). As L 1 (Ω, C) is a complete space, we just need to prove that F| Ω is precompact i.e.: For any ε > 0 there exist functions

f 1 , f 2 , . . . , f N ∈ L 1 (Ω, C) such that F| Ω ⊂ ∪ N i=1 B 1 (f i , ε), where B 1 (f i , ε) denotes the open ball in L 1 (Ω, C) centered in f i and of radius ε.
The proof consists in constructing the functions f i . The main idea of the proof is to apply a convolution regularization process to deal with continuous functions and to be able to apply the Arzela-Ascoli theorem.

Step 1: Regularization process Let us consider the regularizing sequence defined by

ρ n (x) := nρ(nx), where ρ(x) := k exp(- 1 1 -x 2 ) for |x| ≤ 1, 0 otherwise,
and k is a constant such that ρ 1 = 1. For all n ∈ N, ρ n is infinitely differentiable. If * denotes the convolution product, and if f ∈ L 1 (R, C), ρ n * f is a regularization of f in the sense that it is smooth: ρ n * f is infinitely differentiable. We know that ρ n * f ∈ L 1 (R, C) and also ρ n * f -→ f in L 1 (R, C). We prove a stronger result under assumption (11):

(42) Hence for all f ∈ F,

ρ n * f -→ f uniformly in f ∈ F in L 1 (R, C).
ρ n * f -f 1 ≤ sup |y|≤ 1 n τ y f -f 1 .
According to assumption [START_REF] Titaud | Analyse et Résolution Numérique de L'Equation de Transfert[END_REF], for all ε > 0, ∃N 0 ∈ N :

n ≥ N 0 ⇒ ρ n * f -f 1 ≤ ε, for all f ∈ F.
Step 2: Application of Arzela-Ascoli theorem to H n := {ρ n * f : f ∈ F}| Ω

Here n is fixed. Due to the regularization properties, H n is a subset of C 0 (Ω, C). Let us prove that H n is bounded in C 0 (Ω, C) equiped with the infinity norm . ∞ . As F is bounded in L 1 (R, C),

ρ n * f ∞ ≤ ρ n ∞ f 1 ≤ M ρ n ∞ ,
where

M := sup f ∈F f 1 .
Let us prove that H n is equicontinuous. Let

≤ ∇ρ n ∞ |x 1 -x 2 | f 1 , ≤ M ∇ρ n ∞ |x 1 -x 2 |,
where ∇ρ n is the gradient of ρ n . According to Arzela-Ascoli theorem, H n is relatively compact in C 0 (Ω, C) so it is precompact.

Step 3: Construction of the functions f i As H n is precompact, for ε > 0 there exist functions f i ∈ C 0 (Ω, C), i = 1, . . . , N, such that

H n ⊂ ∪ N i=1 B ∞ (f i , ε)
, where where B ∞ (f i , ε) denotes the ball in C 0 (Ω, C) centered in f i and of radius ε, i.e:

∀ρ n * f ∈ H n , ∃f i ∈ C 0 (Ω, C) : ρ n * f -f i ∞ < ε.
Step

4: Conclusion

Let us show that F| Ω is precompact. Let ε > 0 and f ∈ F| Ω . According to the step 1, ∃N 0 ∈ N :

n ≥ N 0 ⇒ ρ n * f -f 1 ≤ ε, forall f ∈ F.
Let us fix n ≥ N 0 . According to the step 3, there exists i ∈ {1, . . . , N }, such that ρ n * f -f i ∞ < ε.

We have

f -f i 1 ≤ ρ n * f -f 1 + ρ n * f -f i 1 , (43)
ρ n * f -f i 1 = b a ρ n * f (x) -f i (x) dx ≤ (b -a) ρ n * f -f i ∞ < (b -a)ε.

(

  H1) L ∈ C 0 ([a, b] × [a, b], C).(H2) H verifies:(H2.1) c H := sup s∈[a,b] b a |H(s, t)|dt is finite, (H2.2) lim h→0 ω H (h) = 0, where ω H (h) := sup |s-τ |≤|h|, s,τ ∈[a,b] b a |H(s, t) -H(τ, t)|dt.Let ∆ n , defined by(3) a =: t n,0 < t n,1 < • • • < t n,n := b,be a uniform grid of [a, b].

by x 1 •

 1 := b a |x(s)|ds. The subordinated operator norm is also denoted by . 1 . The oscillation of a function x in L 1 ([a, b], C), relatively to a parameter h is defined by (4) w 1 (x, h) := sup |u|∈[0,|h|] b a |x(v + u) -x(v)|dv, where x is extended by 0 outside [a, b].

Theorem 2

 2 According to the assumption (P2.2), sup t∈[a,b] b b-h |H(s, t)|ds → 0 as h → 0 + . This ends the proof. Under the assumptions (P1) and (P2), the operator T is linear from L 1 ([a, b], C) into itself and compact in L 1 ([a, b], C).

(H2. 2 )

 2 )dτ < +∞. (P2.1) is also verified because the variables s and t play symmetric roles. Let us prove that, for h > 0-t|) -g(|τ -t|)|dt = 0. Let ψ be the function defined by t → ψ(t) = |g(|s -t|) -g(|τ -t|)|. Suppose that τ < s. It's easy to prove that ψ have an axial symmetry with respect to ξ = s + τ 2 , over the interval [τ, s]. Let G(t) := t 0 g(s)ds.

Then

Figure 1 :

 1 Figure 1: Matrix A of the academic illustration

Figure 2 :

 2 Figure 2: Residual convergence with the three refinement schemes of the academic illustration

0e

  -s/µ µ 2-ν dµ, and the function describes the albedo. In our numerical example (s) = 0.7 exp(-s) and y(s) = -0.3 for s ∈ [0, 50[, 0 for s ∈ [50, 100].

Figure 3 :

 3 Figure 3: Matrix A of the Astrophysics application Figure 3 shows the profile of the matrix A defined by (39). It is a sparse matrix.

Figure 4 :

 4 Figure 4: Residual convergence with the three refinement schemes in the Astrophysics application

≤ 1 n - 1 n 1 n - 1 n 1 n τ y f -f 1 = sup |y|≤ 1 n

 111111 |ρ n * f (x) -f (x)| |f (x -y) -f (x)|ρ n (y)dy, so that for all f ∈ F, R |ρ n * f (x) -f (x)|dx ≤ R |f (x -y) -f (x)|ρ n (y)dxdy = τ y f -f 1 .

x 1 , x 2

 12 ∈ ω |ρ n * f (x 1 ) -ρ n * f (x 2 )| = ρ n (x 1 -y) -ρ(x 2 -y) f (y)dy ≤ |ρ n (x 1 -y) -ρ(x 2 -y)||f (y)|dy

Hence f -f i 1 ≤

 1 (1 + b -a)ε. (44) So F| Ω ⊂ ∪ N i=1 B 1 (f i , (1 + b -a)ε), and F| Ω is relatively compact.

Table 2 :

 2 Relative residuals

	n Projection method Integration product method
	10	0.0267	0.0172
	20	0.0252	0.0145
	50	0.0151	0.0075

Acknowledgements

This research has been partially supported by the Indo French Center for Applied Mathematics (IFCAM).


Michelangelo Bucci
email: michelangelo.bucci@gmail.com

Gwenaël Richomme

Left greedy palindromic length

particular case where the palindromic length is replaced with the left greedy palindromic length.

Introduction

A fundamental question in Combinatorics on Words is how words can be decomposed into smaller words. For instance, readers can think to some topics presented in the first Lothaire's book [START_REF] Lothaire | Combinatorics on Words[END_REF] like Lyndon words, critical factorization theorem, equations on words, or to the theory of codes [START_REF] Berstel | Theory of codes[END_REF][START_REF] Berstel | Codes and Automata[END_REF], or to many related works published since these surveys. As another example, let us mention that in the area of Text Algorithms some decompositions like Crochemore or Lempel-Ziv factorizations play an important role [START_REF] Crochemore | Recherche linéaire d'un carré dans un mot[END_REF][START_REF] Lempel | On the complexity of finite sequences[END_REF]. These factorizations have been extended to infinite words and, for the Fibonacci word, some links have been discovered with the Wen and Wen's decomposition in singular words [START_REF] Berstel | Crochemore factorization of Sturmian and other infinite words[END_REF] (see also [START_REF] Ghareghani | On z-factorization and cfactorization of standard episturmian words[END_REF] for a generalization to Sturmian words and see [START_REF] Wen | Some properties of the singular words of the Fibonacci word[END_REF][START_REF] Levé | Conjugation of standard morphisms and a generalization of singular words[END_REF] for more on singular words).

In [START_REF] Frid | On palindromic factorization of words[END_REF], A. Frid, S. Puzynina and L.Q. Zamboni defined the palindromic length of a finite word w as the least number of palindromes needed to decompose w. More precisely the palindromic length of w is the least number k such that w = π 1 • • • π k with π 1 , . . . , π k palindromes. As in [START_REF] Frid | On palindromic factorization of words[END_REF] we denote by |w| pal the palindromic length of w. For instance |abaab| pal = 2 as abaab = a.baab. They conjectured that if the palindromic lengths of factors of an infinite word w are bounded (we will say that w has bounded palindromic lengths of factors) then w is ultimately periodic (that is has the form uv ω for some words u and v). By a counting argument, they proved that any infinite word with bounded palindromic lengths of factors contains k-powers for arbitrary integers k (it may be emphasized that this condition is true even if we bound the palindromic lengths of prefixes of the infinite word). Moreover, if the word is aperiodic (i.e., not ultimately periodic), each position of the word must be covered by infinitely many runs. In Section 2, we show that the previous conjecture can be restricted to words having infinitely many palindromic prefixes and that, with this restriction, one should expect words to be periodic instead of being ultimately periodic. Moreover we show how to prove the conjecture when palindromic lengths of prefixes are bounded by 2, enumerating the possible forms of palindromic prefixes of an infinite word of such kind.

Let us mention two main difficulties in proving the previous conjecture in the general case. Firstly, when the palindromic lengths of prefixes of an infinite word are not bounded, the function that associates to each integer k the length of the smallest prefix with palindromic length k might grow very slowly. For instance, let us consider the Fibonacci infinite word: as it is the fixed point of the morphism ϕ defined by ϕ(a) = ab and ϕ(b) = a, by [START_REF] Frid | On palindromic factorization of words[END_REF], the palindromic lengths of prefixes are not bounded. Actually, if m(k) denotes the length of the least nonempty prefix of the Fibonacci word with palindromic length k, one can verifies that m(1) = 1, m(2) = 2, m(3) = 9, m(4) = 62, m(5) = 297, m(6) = 1154, m(7) = 5473 and so on. The second problem lies in the fact that a word may have several minimal palindromic factorizations and the palindromic factorizations of a word and of its longest proper prefix are not related. For instance, both words aabaab and aabaaba have palindromic length 2; the first word has two corresponding palindromic factorizations (aabaa.b and aa.baab) and it is the longest proper prefix of aabaaba, which admits only one unrelated decomposition into two palindromes (a.abaaba). To cope with this, in Section 3, we introduce the notion of left greedy palindromic length, which is the number of palindromes in the palindromic decomposition obtained considering iteratively the longest palindromic prefix as the first element. We show that if the left greedy palindromic lengths of prefixes of an infinite word w having infinitely many palindromic prefixes are bounded then w is periodic. As it also implies that palindromic lengths of factors of w are bounded, this proves the Frid, Puzynina and Zamboni's conjecture in a special case.

Around the conjecture on palindromic lengths

The result by A. Frid, S. Puzynina and L.Q. Zamboni stating that any infinite word with bounded palindromic lengths of factors contains k-powers for arbitrary integers k is valid also for infinite words with bounded palindromic lengths of prefixes. Although it is an open question whether having bounded palindromic lengths of prefixes implies having bounded palindromic lengths of factors, it seems interesting to consider both properties. For any integer k ≥ 1, we denote by BPLF(k) (resp. BPLP(k)) the set of all infinite words such that |u| pal ≤ k for all their factors u (resp. all their prefixes u). We denote by BPLF the union of sets BPLF(k) and by BPLP the union of sets BPLP(k). Of course, for any integer k, BPLF(k) ⊆ BPLP(k), and BPLF ⊆ BPLP.

It is clear that sets BPLP(1) and BPLF(1) are equal and contain only words on the form a ω with a a letter. One can observe that, for two different letters a and b and two positive integers i and j, |ab j a i b| pal = 2 when i = 1 or j = 1, and, |ab j a i b| pal = 3 when i ≥ 2 and j ≥ 2. Moreover |ba i ba j b| pal = 3 if i = j, i ≥ 1 and j ≥ 1. It follows that words of BPLF(2) \ BPLF(1) are the words on the form a i (ba j ) ω with i = 0 if j = 0. Determining words in BPLP( 2) is more tedious. Before explaining a way to do it, we restrict our attention to words having infinitely many palindromic prefixes. Next lemma explain the interest of such a restriction. For any word w, we denote by w its mirror image.

Lemma 2.1. Let w be a word in BPLP.

All suffixes of w belong to BPLP.

2. There exists a suffix w of w having infinitely many palindromic prefixes.

3. If w have infinitely palindromic prefixes and is ultimately periodic, then w is periodic.

Moreover there exists two palindromes (possibly one empty) such that w = (π 1 π 2 ) ω .

Proof.

1. Let a be a letter and p be a finite word.

If ap = π 1 π 2 • • • π k with π 1 , . . . , π k palindromes, then p = π 2 . . . π k if π 1 = a, and p = π 1 aπ 2 . . . π k if π 1 = aπ 1 a.
Thus if aw belongs to BPLP(k), w belongs to BPLP(k + 1). In particular if aw ∈ BP LP then w ∈ BP LP . This implies that any suffix of an element of BPLP also belongs to BPLP.

Let I

0 = {0} and for k ≥ 1, let I k = {i | ∃j ∈ I k-1 , w[j + 1..i] is a palindrome}. Note
that for k ≥ 1, I k is the set of all lengths of prefixes of w that can be decomposed into k palindromes. If all suffixes of w have only a finite number of palindromic prefixes, then it can be checked quite directly by induction that for all k ≥ 0, I k is finite. This contradicts the fact that w belongs to BPLP. Thus there exists a smallest integer k ≥ 1 such that I k is infinite. So there exists j ∈ I k-1 , such that w[j + 1.

.∞] has infinitely many palindromic prefixes.

3. If w = uv ω , there exists a conjugate x of v such that for any integer k ≥ 1, there is a palindromic prefix of w ending with x k . Thus, for all k ≥ 1, xk is a prefix of w and w = xω . Now assume u = ε. From what precedes there exists a prefix π 1 of v such that w has infinitely many prefixes on the form

v k π 1 with k ≥ 1: w ∈ (π 1 π 2 ) ω . Let π 2 such that v = π 1 π 2 .
We let readers verify that π 1 and π 2 are palindromes.

From now on, A denotes an alphabet and P(A ω ) denotes the set of all infinite words having infinitely many palindromic prefixes. Previous lemma allows to reformulate Frid, Puzynina and Zamboni's conjecture: if w is an infinite word in BPLF ∩ P(A ω ) then w is periodic. We suspect that also any infinite word in BPLP ∩ P(A ω ) is periodic. Previous lemma also suggests that any infinite word in P(A ω ) ∩ BP LP should be uniformly recurrent, but a direct proof of this fact is an open problem.

We now provide a characterization of words in BPLP(2) ∩ P(A ω ).

Lemma 2.2. An infinite word w over an alphabet A beginning with the letter a and having infinitely many palindromic prefixes is in BPLP(2) if and only if it has one of the following forms (b is a letter different from a):

1. w = a ω ;

2. w = (a i ba j ) ω for some integers i ≥ 1, j ≥ 1;

3. w = (a i b j ) ω for some integers i ≥ 1, j ≥ 1;

4. w = ((ab) i a) ω for some integer i ≥ 2.

A first step for the proof of the lemma is next result.

Lemma 2.3. Any infinite word in BPLP(2) ∩ P(A ω ) contains at most two different letters.

Proof. Assume that w contains at least three letters. Then it has a prefix on the form pc with p containing exactly two different letters a and b, and with c a letter different from a and b.

Inequality |pc| pal ≤ 2 implies |p| pal = 1. Let pcxp be the shortest palindromic prefix of w having pc as a prefix (cx ends with c). Assume a is the first letter of p. There exists an integer n ≥ 1 and a word y such that p = a n by. Let u = pcxỹ. We let readers verify that |u| pal = 3.

In order to prove Lemma 2.2, we consider the possible palindromic prefixes of w. By next(u) we denote the set of all palindromes over {a, b} having u as a proper prefix, such that all proper palindromic prefixes are prefixes of u and such that |p| pal ≤ 2 for all their prefixes p. For instance next(a i ) = {a i+1 } ∪ next(a i b)

Lemma 2.4. For any integer i ≥ 1,

1. next(a i b) = {a i b j a i | j ≥ 1} ∪ {a i (ba j ) k ba i | k ≥ 1, 1 ≤ j < i}; 2. next(a i (ba j ) k ba i ) = ∅ when 1 ≤ j < i, k ≥ 1; 3. next(a i (b j a i ) k a) = ∅ when j ≥ 2 and k ≥ 1; 4. next(a i (b j a i ) k b) = {a i (b j a i ) k+1 } when j ≥ 1 and k ≥ 1; 5. next(a i (ba i ) k a) = ∅ when i ≥ 2 and k ≥ 2; 6. next(a i ba i+1 ) = {a i ba i+j ba i | j ≥ 1}. 7. next(a i (ba i+j ) k ba i ) = {a i (ba i+j ) k+1 ba i } when j ≥ 1, k ≥ 1; 8. next(a(ba) k a) = {(a(ba) k ) 2 } when k ≥ 2. 9. next((a(ba) k ) α ) = {(a(ba) k ) α+1 } when k ≥ 2 and α ≥ 2
The combinatorial proof of each item of the previous lemma, which is rather tedious, but not difficult, is omitted for lack of space.

Proof of Lemma 2.2. The if part is straightforward. Let w be an infinite word in BPLP(2) ∩ P(A ω ) beginning with the letter a. By Lemma 2.3, w contains at most two different letters. Let b be the second possible letter. For some integer i ≥ 1, w begins with a i b. By Items 1 and 2 of Lemma 2.4, for some integer j ≥ 1, w begins with a i b j a i . Assume w = (a i b j ) ω . Let k ≥ 1 be the maximal integer such that a i (b j a i ) k is a prefix of w. By Item 4 of Lemma 2.4, w begins with a i (b j a i ) k a for some k ≥ 1. By Item 3 of Lemma 2.4, j = 1. Assume k = 1. By Item 6 of Lemma 2.4 there exists an integer j ≥ 1 such that w begins with a i b i+j ba i . Thus by Item 7 of Lemma 2.4, w = (a i ba j ) ω . Assume from now on that k ≥ 2. By Item 5 of Lemma 2.4, i = 1 and by Items 8 and 9 of Lemma 2.4, w = (a(ba) k ) ω .

Maybe the main interest of previous proof is the idea of studying the links between successive palindromic prefixes of the considered infinite words. Determining BPLF(3) seems much more difficult, as a simple case analysis seems unfeasible for the large number of cases and the fact that words, such as (abac) ω , that contain three different letters must be considered.

Left greedy palindromic length

As explained in the introduction, we introduce a new measure of complexity for finite words, the left greedy palindromic length, and show that if a word w in P(A ω ) is such that the left greedy palindromic lengths of its prefixes are bounded, then w is periodic.

The left greedy palindromic length of a word w is defined inductively by: |w| As a consequence, if for an infinite word w there exists an integer K such that |p| LgP al ≤ K for any prefix p of w, then also |p| pal ≤ K. We have the stronger property:

Property 3.2. If for an infinite word w there exists an integer K such that |p| LgP al ≤ K for any prefix p of w, then also |u| pal ≤ 2K for any factor u of w.

Proof. Let u be a factor of w and let p be such that pu is a prefix of w. By hypothesis, there exist π 1 , . . . , π k palindromes such that 1 ≤ k ≤ K and pu = π 1 • • • π k . Let x, y be the words and i be the integer such that π i = xy and u = yπ i+1 • • • π k . The word ỹ is a prefix of the palindrome π i . Hence π 1 • • • π i-1 ỹ is a prefix of w. By hypothesis, there exist palindromes π 1 , . . . , π k such that k ≤ K and

π 1 • • • π i-1 ỹ = π 1 • • • π k .
As, by definition, palindromes π j and π j have to be chosen as the longest palindromic prefixes of respectively

π j • • • π k and π j • • • π k , it follows that π 1 = π 1 , . . . , π i-1 = π i-1 and ỹ = π i • • • π k . Hence u = π k • • • π i π i+1 • • • π k is the product of at most 2K palindromes.
One can observe that the words in P(A ω ) such that |p| LgP al ≤ 2 for any prefix p are necessarily words of the form a ω or (ab k ) ω (a and b are letters). Indeed for any integer k, n ≥ 1,

|a i b k a| LgP al = 3 if i ≥ 2, |(ab k ) n a i b| LgP al = 3 if i ≥ 2 and |(ab k ) n ab i a| LgP al = 3 if i = k.
Now we state our main result.

Theorem 3.3. If the left greedy palindromic lengths of prefixes of a word w ∈ P(A ω ) are bounded, then w is periodic.

As a consequence of Lemma 2.1, we have as a corollary that if the left greedy palindromic lengths of prefixes of a word w are bounded, then w is ultimately periodic.

The proof of Theorem 3.3 is an adaptation of the proof of next result which is nothing else than Theorem 3.3 in the special case of words containing infinitely many different letters.

Lemma 3.4. For any infinite word w over an infinite alphabet having infinitely many palindromic prefixes, the set {|p| LgP al | p prefix of w} is unbounded.

Proof. Let (π n ) n≥0 be the sequence of palindromic prefixes of w (all palindromic prefixes of w occur in the sequence and (|π n |) n≥0 is (strictly) increasing). Let n be an integer such that a letter α occurs in π n+1 but not in π n . Then π n+1 = π n ππ n . Let p be a proper prefix of π n :

|π n πp| LgP al = 2 + |p| LgP al (1)
Indeed, one can observe first that by definition of n and palindromes (π i ) i≥0 , π n is the longest palindromic prefix of π n πp. Now we have to verify that π is the longest palindromic prefix of πp. Let us write π = xαy with |x| α = 0 and assume that πz is a palindromic prefix of πp. As π n = ps = zts for words s and t, and as π n and π n+1 are palindromes, we deduce that αx is a suffix of z and st xα is a prefix of π n+1 . As |s tx| α = 0 (as

|π n | α = 0), necessarily |t| = |p|.
As w contains infinitely many letters, Equation (1) implies the lemma.

In the adaptation of the previous proof to Theorem 3.3, the infinite alphabet is replaced with infinitely many powers of a given word. The existence of such powers is guaranteed by an inductive hypothesis. More precisely, given an infinite word w, let MaxLgPalPref(w) be the supremum of the set {|p| LgP al | p prefix of w}. Our proof of Theorem 3.3 acts by induction on MaxLgPalPref(w). The only infinite words such that all their nonempty prefixes are of left greedy palindromic length 1 are words on the form a ω . Assume that K is an integer such that, for any infinite word x in P(A ω ), MaxLgPalPref(x) ≤ K implies that x is periodic. Let w be such that MaxLgPalPref(w) = K + 1.

Lemma 3.5. There exist nonempty palindromes u and v, a length increasing sequence (π i ) i≥0 of palindromes and a strictly increasing sequence of integers ( i ) i≥1 such that π -1 i-1 π i begins with (uv) i u for all i ≥ 1.

Proof. Let (π i ) i≥1 be the length increasing sequence of palindromic prefixes of w. Let i be an integer and let p be any word such that π i p is a proper prefix of π i+1 . By definition of the sequence (π j ) j≥1 , we have |π i p| LgP al = 1 + |p| LgP al ≤ K + 1. So for all proper prefixes p of π -1 i π i+1 we have|p| LgP al ≤ K. One can prove that the sequence (|π i+1 | -|π i |) i≥1 is not decreasing and unbounded. Thus by König's lemma (see [START_REF] Lothaire | Algebraic Combinatorics on Words[END_REF]Prop. 1.2.3]), there exists an infinite word w such that each of its prefixes p is a prefix of π -1 j π j+1 for some j ≥ 1. From what precedes MaxLgPalPref(w ) = K and, by hypothesis, w is periodic.

As w ∈ P(A ω ), also w ∈ P(A ω ). Thus by Item 3 of Lemma 2.1, w = (uv) ω for two palindromes u and v. There exist two sequences of integers ( i ) i≥1 and (j i ) i≥0 such that (uv) i u is a prefix of π -1 j i π j i +1 which itself is a prefix of π -1 j i π j i+1 . The sequence ( i ) i≥1 can be chosen strictly increasing. Replacing (π i ) i≥0 by the sequence (π j i ) i≥0 ends the proof.

When w is not periodic, the previous fact implies that the set of factors of the form (uv) u not preceded by uv and not followed by vu is infinite. This set plays the role of an infinite alphabet, and, not trivially, the proof of Lemma 3.4 can be adapted to state a contradiction.

(f 1 = a, f 2 = ab, f n = f n f n-1 for n ≥ 3). Z.-X.
Wen and Z.-Y. Wen [START_REF] Wen | Some properties of the singular words of the Fibonacci word[END_REF] introduced the notion of singular words for the Fibonacci word. Let (π n ) n≥2 be the sequence of these singular words and let α n β n denotes the length 2 suffix of f n (with α n , β n letters): π n = αf n β -1 . Moreover (see [START_REF] De Luca | A combinatorial property of the Fibonacci word[END_REF] By Lemma 2.1 one can see that for a periodic word in BPLP, the value of min(|u| LgP al , |u| RgP al )-|u| pal taken over factors u of w cannot be arbitrarily large. Finally to summarize this paper, observe that that the Frid, Puzynina and Zamboni's conjecture could be stated as follows. For an infinite word w having infinitely many palindromic prefixes, the following assertions are equivalent:

1. w has bounded palindromic lengths of factors;

2. w has bounded palindromic lengths of prefixes;

3. w has bounded left greedy palindromic lengths of factors; 4. w has bounded left greedy palindromic lengths of prefixes; 5. w is periodic; 6. w = (uv) ω for two palindromes u and v.

Equivalence between assertions 3 to 6 are proved in this paper. Indeed Equivalence between assertions 5 and 6 is provided by item 3 of Lemma 2.1. Clearly assertion 6 implies assertions 3 which implies assertion 4. Finally Theorem 3.3 states that assertion 4 implies assertion 5.

Clearly assertion 6 implies assertions 1 which implies assertion 2. That assertion 1 or assertion 2 implies assertion 6 stays an open problem.

2 . 3 . 1 .

 231 LgP al = 0 when w is the empty word, |w| LgP al = 1 + |u| if w = πu with π the longest palindromic prefix of w. For instance, |abaa| LgP al = 2 and |abaab| LgP al = 3. Similarly, we define the right greedy palindromic length |w| RgP al considering at each step the longest palindromic suffix: |abaa| RgP al = 3 and |abaab| RgP al = Property For any word u, |u| pal ≤ min(|u| LgP al , |u| RgP al ).

  ), for n ≥ 2, f n = B n α n β n where B n is the nth nonempty bispecial factor. All singular words are primitive palindromes. Moreover π n is the longest palindromic suffix of B n α n . Thus one can verify that |α n B n | LgP al = |B n α n | RgP al = n while |α n B n | pal = |B n α n | pal = 2. Taking two fresh letters c and d, letting u n = α n B n cdB n α n , we obtain |u n | LgP al = n + 4 = |u n | RgP al while |u n | pal = 6.

4 Conclusion

 4 Property 3.1 is that, for any word u, |u| pal ≤ min(|u| LgP al , |u| RgP al ). The next example shows that the value of min(|u| LgP al , |u| RgP al ) -|u| pal can be arbitrarily large. Let f n be the nth Fibonacci word

Acknowledgment

This work was partially done while the first author was visiting the LIRMM. Many thanks to ANR-09-BLAN-0164 EMC for funding this visit.