Richard Faure

Verbs of speaking and verbs of thinking

In this paper, I address the differences between verbs of speaking (VOS) and verbs of thinking (VOT) with respect to complementation. I argue that even if in a language these two types of verbs share the same construction, that does not allow us to say that they fall into the same class. A cross between Functional Grammar and Generative Grammar provides us with a refined syntactic structure, where, crucially, functional hierarchy is relative rather than absolute. This allows us to deal with different word orders. The proposal is that the verbs in question always undergo a kind of "functionalization", a process that is related to Cinque's 2004 view of restructuring and makes them acquire certain features of function operators like adverbials. Syntactically, VOS and VOT turn out to occupy separate functional slots. Going back to our starting point, that accounts for observed differences in complement type such as finite-and non-finiteness, absolute or relative temporality etc.

Introduction 1.Issue

This paper is mainly concerned with the syntax and the semantics of declarative predicates or verbs of speaking like say, tell and so on, and with their relation with verbs of thinking (think, believe…). At first sight, there are few differences between (1) and (2). Say and think take the same complement that, and there is no factivity effect, that is the speaker need not believe the content of the that-clause.

(1)

Mary says that Paul is her friend.

(2)

Mary thinks that Paul is her friend.

But this is not so clear-cut in every language. Look for example at Classical Greek data provided in (3), ( 4) and ( 5).

(3) Leg-ôn hoti Phormiôn ouden-Ø say-PTCP.PRS.NOM.M.SG COMP Phormion-NOM nothing-ACC.N poi-ei t-ôn dikai-ôn. do-IND.PRS.3SG the-GEN.N.PL fair-GEN.N.PL 1 'Saying that Phormion does not do anything fair.' (4)

… leg-ont-a mêdena heteron einai to-n say-PTCP-PRS.ACC.M.SG nobody-ACC.M else-ACC .M be-INF.PRS the-ACC Nikodêm-ou fone-a, all' Aristarcho-n. 2 Nikodêmos-GEN murderer-ACC.M.SG but Aristarchos-ACC 'Saying that nobody else is Nikodemos' murderer but Aristarchos.'

(5)

Nomiz-ô fauloter-ous einai t-ou deont-os. 3 believe-IND.PRS.1SG (them) baser-ACC.PL be-INF.PRS the.GEN necessary-GEN. 'I think that they are too base.' Legô 'say' takes as complement either a hoti (that) clause, which is excluded after verbs of thinking, or an Accusativus cum Infinitivo (AcI), which is the construction expected with verbs like believe or think. On the contrary, in French, as in English and many other modern European languages, both classes of predicates select for a que/that clause.

Therefore several questions arise :

What is the difference in Greek between verbs of thinking and verbs of speaking, if any ? Do the two constructions reflect a semantic difference in the nature of the complements ? What does this difference tell us about these two classes of verbs ?

Preliminary remarks

At first glance, (1) expresses Mary's utterance of her thought (2). However, she can also express something that is not her real thought, but a pretence. Pragmatically, she commits herself to the truth of her utterance, but given that it is an implicature, it can be easily deleted, especially in reported speech as (6). It has been a long-standing question whether believing is part of speaking or not (see for example [START_REF] Lyons | Semantics[END_REF], who thought that they were inseparable). It the answer is no, it is possible that the present discussion is irrelevant.

(6)

Mary says that Paul is her friend, but she doesn't actually think so.

Assuming however that they are in some way related, where is the starting point for our investigation ? Turning back to our first statement, the difference resides in whether the thought is uttered or not, that is in a speech act feature that is found with say.

From this point on, two tracks present themselves. Either we treat verbs of speaking and verbs of thinking as two classes with sets of properties that are irreducible to one another, or we can analyse verbs of speaking as complex predicates [think + utter feature]. Despite the abovementioned debate, it seems that the two classes have much in common, and that the first approach would give rise to more issues than it can resolve. We will then follow the second track. This first theoretical step does not tell us how to deal with this 'utter'-feature.

Accounting for this feature in terms of syntactic selection is not possible since say and think in Greek share a construction. Nor is it possible to call for semantic selection until a long examination given the complications we have seen above. Therefore, what I propose is to begin with the assumption that speaking is just thinking and express one's own thought. Our first task will then be to pinpoint where this feature is conveyed. Fortunately, we are not working in an unexplored area. The idea that something is added to a thinking process appeals to a hierarchical organization. Here are the hypotheses that can be drawn from this basic proposal.

Hypotheses

i) The syntactic structure of the complement of verbs of thinking lacks a layer. This layer would be the site where the 'utter'-feature is checked. This has mainly been developed in frameworks such as cartographic approach. The possibility of using a complementizer with speech act predicates (henceforth SAPs) in Classical Greek would be related to a higher level in the left-periphery of the clause, namely the (illocutionary) force-level. This has been argued for other verb classes in McCloskey (2006) or [START_REF] Haegeman | Conditionals, factives and the left periphery[END_REF], to cite but a few. This would lead us to a structure like ( 7) and ( 8), for a verb of speaking, and like (9), for a verb of thinking where the missing structure has been struck through. The size of the missing structure remains of course to be clarified along with what the whole structure has to look like, which is not as straightforward as it seems when we see the most current structure proposed for the left-periphery of the clause. For example, the two just mentioned accounts are rather different in this respect. ( 7)

Independent clause : [Force Top Foc Top Fin IP …] (8) Say [Force Top Foc Top Fin IP …] (9)
Think [Force Top Foc Top Fin IP …] ii) The selection differences are the manifestation of semantic differences. In Functional Grammar (henceforth FG), for instance, the clause is divided into several functional layers that correspond to several operators. The syntactic mapping of these layers is not clear in this framework, but the semantic component is highly supported by the scope of adverbials. SAPs select for a complement corresponding to an entity of a higher type than verbs of thinking. This complement is therefore realized differently as can be seen from ( 10) through ( 12). ( 10)

Independent clause : [E(X(e …))] 4 (11) Say [E(X(e …))] (12) Think [X(e …)]
These two approaches are not incompatible of course, though not necessary to one another. But before going further, let us see why both proposals are problematic.

A further issue

Neither theory is concerned with the fact that postulating a speech act feature in the syntactic structure or in the meaning of the complement is somehow redundant with the meaning carried by the embedding verb of speaking. This verb specifies the type of the illocutionary force. So, this information does not have to take place in the complement, or, at least, this must be justified by, say, a split in this feature, or the presence of two subfeatures, it is not yet clear. Such an observation requires us to formulate other hypotheses. Indeed, if the illocutionary force is carried by the matrix verb, it should not be represented in the embedded clause. Therefore, the embedded clause should lack a layer or a feature compared to an independent clause. We end up with a structure like (13), ( 14) and (15), to be made precise as in the preceding hypotheses. If it is right, that principle carries over to the structure of verb of thinking complements and provides us with something like ( 16) or ( 17), for reasons to be made precise later, but which can be roughly formulated as a lack of the epistemic layer. i) The syntactic structure of the complement of verbs of thinking lacks a layer compared to that of verbs of speaking which corresponds to an independent clause. This layer would be the site where the 'utter'-feature is checked.

ii) An independent clause is the only syntactically complete clause. A verb of speaking conveys an 'utter'-feature, hence its complement lacks the corresponding layer. This reasoning carries over to verbs of thinking, but with two missing layers : the 'utter'-feature site and the epistemic site.

iii) The selection differences are the manifestation of semantic differences. Verbs of thinking lack a semantic speech feature, which is reflected by a difference in construction selection. Their complement is not a speech act, but a proposition. 7 iv) The selection differences are the manifestation of semantic differences. Verbs of speaking bear the feature 'illocutionary-force'-declarative. Therefore their complement is a proposition. Verbs of thinking bear an epistemic feature, therefore their complement is a State of Affairs. 7 We end up with four hypotheses.

Claim and organization of the paper

The paper is organized as follows : I begin with an examination of the first two hypotheses. I shall look in detail at the left-periphery of the clause and the cartographic approaches, and conclude that it is still too messy to obtain an accurate structure. I turn then to some Spanish data in order to highlight a relevant difference between declarative, on the one hand, and interrogative and order SAPs, on the other hand. At this point, Spanish data do not shed much light on the subject. I address then the last two hypotheses and the functional part of the study and explore what the adverbs can tell us about the internal layering of the embedded clause. It turns out that the hypothesis iv) is borne out. Finally, I point to the theoretical contribution of the study, and try to fix the puzzle of Greek data. Throughout the study I keep in mind the following questions: If there is a difference between speaking and thinking predicates, why does legô 'say' accept two constructions ? Does this difference also exist in languages that have one and only type of complementation ?

A truncated split-CP structure ? (McCloskey 2006), (Haegeman 2006)

An incomplete or truncated structure has already been claimed for, for example in McCloskey (2006) or [START_REF] Haegeman | Conditionals, factives and the left periphery[END_REF]. Let us see if their proposals apply to our issue.

He points out that after certain verbs a topicalized element can appear above the complementizer that, whereas this is impossible with others, at least in Irish English and in Italian. The contrasts are between (18)-( 19) and [START_REF] Demonte | 21 See the hierarchy under (47). 22 It marks anteriority. 23 Xenophon[END_REF] The basic idea is that sentences like [START_REF] Demonte | 21 See the hierarchy under (47). 22 It marks anteriority. 23 Xenophon[END_REF] and ( 22) lack the uppermost level of the left periphery. A kind of truncation has taken place. Therefore the TopP above FocP is no longer an available landing site for any fronted element, which leads to the ungrammaticality of ( 20) and ( 22). This correlates with the CP recursion, where the topicalized element occurs between the two complementizers. In (23) the underlined verb inversion is argued to be a way to mark another C place in Irish English, given the equivalence between ( 18) and ( 19), where, with the same verb ask, if as well as the inversion, occurs under the fronted adverbial clause.

(23) Patsy asked him if, when he was sent to college, was it for a clergyman or a solicitor. (McCloskey 2006: 104) In this paper, McCloskey is mainly concerned with questions. For him (McCloskey 2006: 110-112), the presence of if in the highest position of the structure is the syntactic counterpart of the semantic operator QUEST, proposed by [START_REF] Krifka | For a structured meaning account of questions and answers[END_REF]. The boundary would then be between interrogative and resolutive verbs, which lack the QUEST operator. We are therefore dealing here with a parallel similar to ours. In McCloskey's paper, it is between questioning and answering predicates ; in ours, it is between declarative predicates and verbs of thinking. In fact, the following contrast holds : [START_REF]On 272 AcI in Herodotus' histories, only 9 are introduced by something else than legousi "one said" or legetai "it is said[END_REF] Patsy tells him that 1 , when she was in college, that 2 she could not stand anybody. (25) * Patsy thinks that 1 , when Peter was in college, that 2 Peter could not stand anybody. (26) Patsy thinks that 2 Peter could not stand anybody when Peter was in college.

The interpretation would then be that the structure layers above that in (26) are missing and that these missing layers contain a slot for the illocutionary force marker. 8 It is the same for McCloskey's data, where the uppermost level is missing with verbs introducing an answer, namely a fact. 9 But the parallel is not as robust as it appears at first glance, given that the propositional content of verbs of thinking does not entertain the same relation with SAPs as resolutive verbs with respect to questioning ones. The question and the answer are complementary, while the relation between the two types of that-clauses is far from being straightforward. It resembles more a kind of inclusion relation.

Furthermore there is a worse objection to McCloskey's hypothesis, provided by his own data. He shows that the negative, interrogative and nonveridical environnements improve greatly the acceptability of the sentences with a resolutive verb. Look at ( 27 (27) * I remember who did they hire. (28) ? Do you remember who did they hire? (29) ? I don't remember who did they hire.

(30) *You remember when they were in Dery if they lived in Rosemont? (31) ? Do you remember when they were in Dery if they lived in Rosemont?

(32) Do you remember when they were in Dery did they live in Rosemont?

As argued in the last part of his paper, the factors for CP truncation or completeness are more semantic or even pragmatic than merely syntactic and related to the selectional properties of certain verbs. The division is not between two classes of verbs, but between two environments, and therefore cannot apply to our issue. [START_REF] Haegeman | Conditionals, factives and the left periphery[END_REF] proposal is close to McCloskey's. Going into it would take us too far. In few words, she proposes that there may be gaps in the structure, depending on the embedding verb. The reason why we do not keep this theory is that if we are dealing with gaps, we lose the descriptive advantage of a layered structure that can be truncated, or at least, all the tests must be rephrased, given that they are, as far as I understand them, based on the ordering of the constituents. Further research is then needed in this domain, and possibly a parametrization.

Declarative and other SAPs: what Spanish data tell us

The cartographic approach, though appealing, cannot help us in determining the declarative complement nature, propositional ou illocutional. We can then change our viewpoint and turn towards the predicates that we can assume belong to the same class and are comparable : interrogative, order and declarative SAPs. Look at the following Spanish data : (33) is possible with or without que, whereas (34) and 0 are impossible with que. The que preceding the interrogative is limited to questioning verbs that are SAPs. It is even excluded after a non SAP inquiry verb (34). ( 36) shows that the negation does not help. The split is then not the same as in McCloskey (2006). Now, if you look at (37), it turns out that que can also optionally occur with a verb of order, which is also a SAPs. As argued in [START_REF] Lahiri | Questions and answers in embedded contexts[END_REF], que is then a 'quotation marker'. But we are not dealing with a direct quotation marker. It is rather a 'reporting marker', given that the sequence of tense is possible. This fact is striking. The parallel between order and questioning predicates induces that what they embed is not a reduced structure, but an entire speech act. Why cannot it appear with declarative SAPs ? According to [START_REF] Demonte | Force and finiteness in the Spanish complementizer system[END_REF], this is due to phonetical constraints, since sentences like (39) are possible, with complementizer recursion. In (38), a kind of haplology takes place, which is precluded in (39) by the intervening topic. Declarative SAPs pattern with the other SAPs and embed a full structure, namely the whole speech act, and not a proposition.

(37) Orden-ó/dij
( Moreover, if the first que were a quotation marker, it is not clear to me why it is the second que that is optional. It is the first one that should be optional as in (37) and (33). This is borne out by (41), where the topic is below the optional que, while in (39) it is above. Finally, in (33), ( 37) and ( 40) que and the interrogative item qué have a clear different role, as opposed to (39) where the second que seems to be more a resumption of the first, a kind of repair strategy, than a special function bearer.

An alternative interpretation would be following Roberts (2004: 305). For him the complementizer has as default value 'declarative'. It does not hence need any further element to be made precise. In 4.5 we make another proposal based on (38) and the presence of one and only que.

Purely syntactic analyses have not allowed us to make a decision. Let us attempt to address the problem on the syntax/semantics interface side.

Adverbs in embedded clauses and the syntax-semantic layering of the clause in the frame of Functional Grammar

Framework

It has been reckoned for a long time that the order of the adverbs in the sentence is not free, but corresponds to a subjacent layering of the sentence. The sentence structure is more or less fine-grained, depending on the chosen theory (cf. Cinque 1999, Dik and[START_REF] Dik | 15 Without a pause after[END_REF]). [START_REF] Schweikert | The position of prepositional modifiers in the adverbial space[END_REF], based on [START_REF] Cinque | Adverbs and functional heads: A cross-linguistic perspective[END_REF], offers a way to reconcile the two approaches.

A survey of Functional Grammar

Basically, in FG [START_REF] Dik | The hierarchical structure of the clause and the typology of adverbial satellites[END_REF][START_REF] Dik | The Theory of Functional Grammar. Part 1: The structure of the clause ; Part 2: Complex and Derived Constructions[END_REF] it is proposed that the clause has four different layers :

1) core predication, 2) state of affairs, 3) proposition, 4) speech act.

Here is a summary of FG, extremely simplified. A basic core predication gets by means of an operator further specification (time, place and so on) that transforms it into a state of affairs. This state of affairs gets a truth value (and many other properties) and becomes a proposition. Finally, the proposition gets an illocutionary force and becomes a speech act. If this is true, there may be a manifestation of the boundaries between each layer. This is shown by the difference of modification. Each layer takes as a modifier a different range of adverbials.

In the following, tests 14 are provided for distinguishing between two high layers (interpersonal = speech and modal layers/speaker-oriented/propositional layers ; and representational = state of affairs and core predication layers), and then between two sublayers. The adverbials of the interpersonal level can neither be focalized nor questioned (42) ; they cannot be resumed with the rest of the sentence by a proform. ( 43) is opposed to (44), which is modified by another type of adverbial.

(42) * Does India probably face famine ? (43) * He'll take his umbrella in case you are wondering and so does Ann.

(44) He'll take his umbrella in case it rains and so does Ann.

The adverbials of the representational level can be focalized, they constitute a unity with the core predication and are selectionally tied with the predicate's properties (telicity, control…). I put aside any further examination of the representational level which would be beyond the aim of this paper.

Within the interpersonal level, two sublayers can be distinguished. Some adverbials can appear at the top of any sentences while others cannot (( 45), ( 46)). The former seem then to be able to combine with any type of speech acts. They vouch for the existence of the speech act layer. The latter must be between them and the representational level, namely in the propositional layer.

Proposition satellites in general presuppose the speaker's positive commitment to the truth of the proposition he presents. These satellites are therefore largely restricted to declarative sentences. They can be said to operate inside the illocutionary layer.

Illocutionary satellites, on the other hand, operate outside the illocutionary layer, which is shown in their relative freedom to occur with any kind of sentence type. [START_REF] Dik | The hierarchical structure of the clause and the typology of adverbial satellites[END_REF] This structure can now be refined with [START_REF] Schweikert | The position of prepositional modifiers in the adverbial space[END_REF] assistance.

Schweikert (2005)

Here is the motivation for Schweikert's organization of [START_REF] Cinque | Adverbs and functional heads: A cross-linguistic perspective[END_REF] hierarchy:

Cinque's hierarchy [see below under (47)] of adverbs can be subdivided into three different groups with respect to scope relations. The first group consists of all adverbs sitting in Modvolitional or above. If we find them in front of any thematic role (temporal or lower, not evidentials) they are ambiguous between a wide scope and a narrow scope interpretation. If one PP of the kind under consideration is found to their left, they have only narrow scope over the constituent immediately to right.

The second group -between prospective and habitual aspects-have the above behavior with respect to locative and lower thematic roles. With higher thematic roles they show a different behavior. If they precede these PPs they get only narrow scope interpretation and the sentence get slightly degraded down to ungrammatical.

The third group consists of the lowest part up to Mod ability. All adverbs found here have their unmarked position to the right of all prepositional sentence modifiers. (Schweikert 2005: 214-215 ) It must be added that, in the first class, the adverbials corresponding to MoodPspeech act are obviously higher, but do not show the scope ambiguity of the adverbials just below them. They must thus be characterized as a separate class.

(47) Combining a fine-and a coarse-grained hierarchy.

( Hence, we end up with two hierarchies, a fine-grained and a coarse-grained one. Each level of the coarse-grained divides into a fine-grained structure. But what is especially interesting is that we get four classes, that is exactly the same number as in FG, and that, with completely different evidence and tests, the results are very close, if we except some borderline hesitations, even in native speaker judgements. This hierarchy is therefore highly reliable.

To what extent does the first level of the hierarchy correpond to the division of generative grammar between CP, IP, VP? It is hard to tell. According to Cinque, this is a matter of split-IP. Nevertheless, as we saw above in the examination of [START_REF] Haegeman | Conditionals, factives and the left periphery[END_REF] proposal, what she names 'speaker deixis' and corresponds to MoodPspeechAct to ModPepistemic is located within the low part of the CP. For Cinque (1999: 84), MoodPspeechAct is rather the uppermost part of the IP, albeit it could also move up until Spec, Force. This is based on the position below the focus, but optionally above the uppermost TopP. Moreover, there are good arguments to say that at least some aspectual properties should be part of the VP. Thus, this area remains fuzzy and we prefer adopt the position developed in the next section.

Syntactic mapping

In the introduction and after the examination of the left periphery of the clause, we claimed that the last proposal would be more semantic. However, we have used only syntactic tests so far. What they did, was merely to reveal the semantic layering. Following [START_REF] Ernst | The syntax of adjuncts[END_REF], we assume that as far as the adverbials are concerned, we are dealing with a mapping of the semantics onto the syntax.

Let us have a look at an example to see how this works.

A location adverbial applies to a state of affairs.

An epistemic adverbial applies to a proposition. Now, if one wishes to combine the two adverbials, what will be the ordering ? Let us take an example. Let run(dog) be a core predication. Through the 'state of affairs' operator, it becomes a state of affairs. Then it can be modified by an adverbial like 'in the street'. One gets (49). One can then apply the 'propositional' operator and then modified the obtained proposition with an epistemic adverbial such as probably. One gets (50).

(48) A dog is running.

(49) A dog is running in the street. (50)

A dog is probably running in the street.

Now if we reverse this, we can apply the 'state of affairs' operator. We get (52), apparently unchanged. Then the 'propositional' operator applies. And we can modify it with probably.

But if now we want to add the information 'in the street', you are applying a state of affairs modifier to a proposition. The result is thus predicted to be infelicitous. Indeed, ( 54) and ( 55) are out.

(51) A dog is running.

(52) A dog is running. (53)

A dog is probably running.

(54) *A dog is running in the street probably.

(55) *In the street a dog is probably running. 15 Therefore, the linear ordering of the adverbials is nothing else than the reflection of the ordering of the operators. Adverbials do not have to head the part of the sentence they have scope over, provided that their relative ordering is respected. This means that in (53), probably need not be in front of the sentence.

Results

It is crucial to note that we agree with [START_REF] Cinque | Adverbs and functional heads: A cross-linguistic perspective[END_REF] and [START_REF] Schweikert | The position of prepositional modifiers in the adverbial space[END_REF] on the description yielded by their theories, but not on how they account for it. By transfering some properties assigned to the syntax to the semantics and stressing the primacy of the semantics over the syntax, we can get the right adverb order for free, without facing the issue of different adverb placements, since everything gets relative.

Cinque's (2004) restructuring

A last note will be on [START_REF] Cinque | Restructuring and functional structure[END_REF] application of this hierarchy. In this paper (and some previous ones) he claims that the hierarchy of functional heads is the best way to account for restructuring effects. He argues that:

The verbs that enter the 'restructuring' construction appear to correspond to distinct heads of (3), in the sense that each seems to lexicalize the content of one or another functional head. (…) Only those verbs which happen to match semantically the content of a certain functional head admit of two distinct possibilities. They are either regular verbs, heading a VP (…) or 'functional' directly inserted in the head position of the corresponding functional projection. (Cinque 2004: 1-2) The common idea between Cinque's proposal and restructuring is that with two potential clauses we make one. But they differ crucially on the fact that with restructuring two verbs merge into a single one, whereas in Cinque's theory the first one is downgraded from the status of verb to the status of functional modifier.

Our proposal is an extension of this theory. Instead of inserting the verb in, say, the ModP permission , we inserted it in MoodP speech act , not as a head, but as a modifier. What we look at now is whether we are (always, sometimes, never) dealing with a reconstruction case. We must especially focus on mono-/bi-clausality and the way speech act or epistemic verbs become functional, since it is not straightforward or even counterintuitive.

Hypotheses

I would like to remain agnostic as to where in the IP or CP the adverbials show up. I am only going to use the relative ordering and base hypotheses on it, which are reminiscent of hypotheses iii) and iv) of Section 1.5. A) If the complement of a declarative SAP is a speech act, it should be able to retain the whole range of adverbials. B) If, on the contrary, the SAP bears the illocutionary force, everything that goes along with it should appear in the matrix clause, for example, the speech act adverbials. If this second hypothesis is on the right track, we expect this behavior to be recursive and to apply to lower levels. For example, after a verb of thinking, some (lower than speech act) adverbials are predicted to be excluded.

Data and analyses

In the French sentence (56), the adverb sincèrement is tied with the uppermost level, MoodPspeech act. When embedded under a verb say the result ( 57) is not acceptable. This seems to confirm the second hypothesis. Now, if we enter the high level, into a fine structure, such as the level (2) under (47), we can see that the result is the same. Embedding (58), that contains an evidential adverbial paraît-il 'allegedly' under penser 'think' yields (59), that is an evidential adverbialparaît-ilcannot be embedded under an epistemic operator such as penser 'think', given that the functional order is evidential-epistemic, and not the other way around. This leads us to two conclusions. a) It is the confirmation that the order of the operators and functions matters at the fine-grained level as well as at the four-layer one (what we saw in Section 4.1.1). b) This is an indication that the same reasoning can be applied between a matrix predicate and the structure of the embedded clause as between two adverbials in a root clause.

( Moreover, why is it that (62), where we are dealing with a structure parallel to (61) with a declarative SAP, is fully acceptable? Both questions are addressed in the next section.

Adverbials in matrix clause

The first question has its answer in the very fact that probablement and penser range over the same epistemic area. That make them concurrent, but also allows probablement to become a precision tool for penser. Let us see how. In (60), Probablement may be understood as a further indication about the epistemic state of the matrix subject, by pointing at the part of the embedded clause concerned by the belief state. Furthermore, probablement, as well as probably in English, can have a focus interpretation or at least a narrow scope interpretation, which is not possible with franchement or sincèrement that take in their scope the whole sentence, or change their interpretation to intensity (very) when they have scope on a single element. Cinque (1999: 30-32) also calls for the focus explanation in order to account for anomalous behaviors. One of his argument is that the at issue adverb forms a constituent with the element it precedes. This is borne out by examples like (63), where the adverb is clefted with Anne.

(63) C'est probablement Anne qui a vendu son téléphone.

It is probably Anne who has sold her phone.

It is not clear to me whether the precision and the focus functions can be reduced to a single one. Anyway, be the function simple or twofold, it does not lose its explanatory power, as shown by the following tests.

First of all, (63) can be embedded under penser 'think' (64), whereas the non-cleft version is highly strange to French speakers, even with a stress on Anne, albeit it improves a little the sentence (65).

(64) Jacques pense que c'est probablement Anne qui a vendu son téléphone. Jacques thinks that it is probably Anne who has sold her phone. (65) ? Jacques pense que probablement ANNE a vendu son téléphone.

Jacques thinks that probably Anne has sold her phone.

Second, for the speakers that do not like (60), the examples (66), ( 67) and ( 68) are highly improved or even fine.

(66 In ( 68) and ( 67), probablement has been lowered and placed just to the left of the element it has scope over. In (66), it remains 'in situ' but, as well as only, it can have scope separately on each element downwards. It must be noticed that the scope is on an adverbial PP or a low argument rather than on an argument close to the verb. This phenomenon pertains to the focus effects. There has been an event of 'Anne buying a phone in the train' or of 'Anne buying a phone for her husband', and this event is said to have taken place, respectively for 'her husband' or 'in the train' in Eric's opinion. This translates into the pseudo logical formulas. ( 66) is ambiguous between (69), ( 70) and ( 71 The second question concerned the contrast between ( 61) and ( 62), repeated here as ( 73) and ( 74).

)
(74) would be the outcome of the embedding of (72) under a predicate dire 'say'. One would like to keep the information 'sincerely', but for the aforementioned reasons, the adverb cannot remain in the que/that-clause: (75) is out. It must then rise into the matrix. I claim that this analysis is not accurate. [START_REF] Ernst | The syntax of adjuncts[END_REF] argues that a speech act adverb like frankly is merely a manner adverb that has scope on an implicite performative operator or predicate. This is true, but the only parallel that can be drawn is between ( 77) and ( 78) where the first person is used, for a performative predicate is a first person singular at a present tense. 18 (77) Je te dis franchement que je ne suis pas content. I to you say frankly that I am not satisfied. ( 78) Franchement, je ne suis pas content.

Frankly, I am not satisfied.

However, ( 78) through (81) as well as ( 72), ( 74) and ( 75) have dictinct truth conditions. ( 79) may be true even if Nicolas is not aware that he is frank by saying that he is angry. ( 80) and ( 81) cannot get this interpretation either. Therefore the asymmetry between ( 72) and ( 74), though hidden in some situations, obtains, as well as between ( 60) and ( 61). It has been blurred by the fact that there is another interpretation for (74), but not for (61).

( Frankly, Nicolas is not satisfied.

Consequently, ( 74) and ( 76) are isolated sentences that cannot be derived from ( 72). ( 73) is fully acceptable if probablement is a judgment of the speaker's on Eric's thinking, as well as in ( 74), ( 76) and ( 79) sincèrement and franchement are evaluations of the speaker's over Eric's way of speaking rather than the way Eric or Nicolas intended to utter their statements.

Consequences 4.5.1. Predictions

Going back to the two hypotheses A) and B), B) is borne out. Given that the matrix predicate is in charge of bearing the illocutionary force, it embeds a clause which contains the layers under that of speech act in (47), namely a proposition. This predicts that any other adverb should be able to show up within the complement clause. Let us test it with evaluative, evidential and epistemic adverbs, respectively illustrated by ( 82), ( 83) and ( 84).

( Giving a proof for this assumption and an answer as to why a proposition cannot be quoted as this is far beyond the scope of this paper, but it can be informally captured by the following reasoning. "A dog is running in the street" as a proposition is not the same as as an assertion. As a proposition, it can be true or false. But that does not mean that it has been uttered and shared, namely proposed in a discourse situation by a speaker to a hearer in order for her to add it to her information state. What makes the propositional content of a 'sentence' an assertion is either a speech act operator in a root clause, or, if embedded, the matrix predicate.

Theoretical consequences of the (47) hierarchy and the Greek puzzle

The main contribution of this account is the improvement of the functional hierarchy of the clause. We have taken the first step towards a reconciliation of functional and generative grammars. They are not incompatible in their principles, indeed their concerns are far removed from one another. We saw an application of this new functional hierarchy. Let us have a look at some related applications which bear out this hierarchy.

The tense/time issue

Another application is in the domain of the tense/time problem. In (47) time layers are spread all along the hierarchy. For example, the propositional level contains absolute time level, and therefore finite level, since generally only finite verbs can express the absolute time. The issue then arises as to why some languages allow non finite complementation after verbs of thinking as AcI in Greek, or small clauses elsewhere. The solution is straightforward if we think that, according to our above data, the complement of a verb of thinking should be an event, a situation or a state of affairs, depending on the framework one is working in. If this is true, it has only to undergo the temporal and other constraints corresponding to the third and fourth levels claimed in 4.1.2. Given that a verb of thinking ranks among epistemic operators, the layers between Temp(Past) and AspPcelereative(I) 21 are optional. That is why Comp-clauses and a finite verb can occur as well. But what is thoroughly excluded is a non-finite clause denoting an entity of a lower type than event/state of affairs (for example core predication in FG). This prediction is borne out by the fact that we cannot have, in Classical Greek, a clause that does not express the time relation with the matrix time. In (89), katalipein is an aorist 22 . If the clause had express something lower than an event, it would have lack the TP(anterior) layer. In a nutshell, the uppermost boundary for the complement of verb of thinking is expected to range between TP(past) and AspPcelereative(I), but not lower. This enables parametrization among languages.

The Greek puzzle

We can now understand why in languages with a rich complementation system, declarative SAPs depart from verbs of thinking. Going back to Classical Greek and the first issue of the paper, we can therefore ask the question why one of their constructions is shared with verbs of thinking. In fact, the AcI is rarely employed, except with impersonal forms as 'it is said that…' that are probably more related to evidentials than to speech acts (90). 24 This means that with them we are already in the lower domain, the propositional domain. 25 (90) Nikia-s ho Nikêrat-ou lege-tai epistatê-n Nicias-NOM the-NOM Niceratos-GEN say-IND.PRS.PASS.3SG manager-ACC eis targurei-a pria-sthai talant-ou. 26 for the.silver.mines-ACC.N.PL buy-INF talent-GEN 'Nicias, son of Nicaratos, is said to have given a whole talent for a manager of his silvermine.' This does not account for languages as Classical Latin, where verbs of speaking are obligatorily followed by an AcI, without tense marks. Note however that languages of this type are not ruled out by our account, given that it makes predictions as to which is the uppermost boundary of a complementation type, but not as to the lowest. We can stipulate for Latin a grammaticalization of an evidential structure, this last feature being retained.

Finally, verbs like want are predicted not to be able to have a tensed complement, given that they sit very low in the hierarchy, in ModPobligation / ModPpermission&ability. This is borne out by every language I am aware of, even when a finite verb can occur, it is not tensed (which crucially does not mean that they are not finite). On this point Cinque's 2004 is highly convincing.

Conclusion

Based on [START_REF] Schweikert | The position of prepositional modifiers in the adverbial space[END_REF] hierarchical structure, the tests show that complex clauses behave like simple ones, at least with respect to the functional layering. Interestingly, there are some borderline cases like the use of credo + subjunctive without complementizer in Italian [START_REF] Giorgi | Credo (I believe): Epistemicity and the syntactic representation of the speaker[END_REF]. In order to account for the behavior of credo in this type of sentences, they argue for a movement that raises credo to a position above that expected, namely, the epistemic position, in order to check certain verbal features. This is typically a boderline case. If I am right, the matrix predicate has to be taken into account as the first layer of the embedded clause. This tells us that declarative SAPs do not embed a speech act, but a proposition, and, consequently, that propositional predicates embed state of affairs/event, rather than proposition.

The rough scheme of the study would be as in ( 91)/(92). In (91) the elements between the two bold-faced brackets are reinterpreted and merged into one and only continuous range of ordered adverbials. This is trigerred by the incompleteness of the embedded structure. (92) provides us with the outcome. In ( 93) and ( 94) we have what comes in generative framework.

(functional projections) [VP ]]]]]

This study does not allow us to decide between the syntactic [START_REF] Cinque | Adverbs and functional heads: A cross-linguistic perspective[END_REF]) and the semantic [START_REF] Ernst | The syntax of adjuncts[END_REF] accounts of adverb behavior. It does not help either in the determination of the left-periphery structure, as to which I will remain agnostic. It is only sure that the hierarchy, either semantic or syntactic, between adverbials is fixed and probably universal. We can also wonder whether we are able to find a predicate for each functional head.

Notes

1 Demosthenes, Ad Phormionem, 13. 2 Demosthenes, Ad Midiam, 121. 3 Isocrates, Aeropagiticus, 72. 4 E represents the Force level, X the propositional level, e the event/State of Affairs level… see 4.1.1 for further precision. 5 The double slash indicates a break in the structure. 6 The simple crossing indicates what has been added to the former proposal in (9). 7 These notions will be explained when we will turn to this hypothesis. 8 Cf. [START_REF] Rizzi | On the position "Int(errogative)[END_REF] « The other subclass of indirect questions selected by such verbs as "find out", "discover", etc., not allowing initial que, nor an initial topic, may perhaps be analyzed as not involving the Force layer at all. »

( 13 )

 13 Independent clause: [Force Top Foc // 5 Top Fin IP] or [E // 5 (X(e …)] (14) Cartography: Say [low CP level, IP] (15) FG: Say [(X(e …)]

( 16 )

 16 Cartography: Think [Force Top Foc Top Fin IP …] 6 (17) FG: Think [ (e …)] 1.5. Modified hypotheses Now we need to rephrase our hypotheses along the lines of the previous observation.

  ) through (32) fromMcCloskey (2006: 99-100) :

( 33 )

 33 Te pregunt-an (que) para qué quie-res el préstamo. 10 you ask-IND.PRS.3PL COMP for what want-IND.PRS.2SG the loan 'They ask you what you want the loan for.' (34) Investigar-on (*que) para qué quier-es el préstamo. investigate-IND.PRS.3PL (*COMP) for what want-IND.PRS.2SG the loan 'They investigate you what you want the loan for.' (35) El detective sab-e (*que) quién la mat-ó. The detective know-IND.PRS.3SG (*COMP) who her kill.IND.PST.3SG 'The detective knows who killed her.' (36) El detective no sab-e (*que) quién la mat-ó. The detective NEG know-IND.PRS.3SG s (*COMP) who her kill.IND.PST.3SG 'The detective does not know who killed her.'

  (41) Te preguntan (que ) el préstamo Topic para qué lo quieres. 13 you ask-IND.PRS.3PL COMP the loan for what it want-IND.PRS.2SG 'They ask you what you want the loan for.'

  ) MoodPspeech act > (2) MoodPevaluative > MoodPevidential > ModPepistemic > TP(Past) > TP(Future) > MoodPirrealis > ModPalethic > Temporal / Starting Point of ongoing event / Starting Point of closed event / Elapsed Time of ongoing event / Atelic Duration > AspPhabitual > AspPrepetitive(I) > AspPfrequentative(I) > ModPvolitional (3) AspPcelereative(I) > TP(Anterior) > AspPterminative > Aspcontinuative > AspPproximative > Aspdurative > AspPgeneric/progressive > AspPprospective > Locative > Comitative > Benefactive > Reason > Source > Telic Duration / Secondary Duration >Goal > Malefactive > Instrumental / Means / Path > Matter > Manner > (4) ModPobligation / ModPpermission&ability > AspPCompletive > VoiceP > AspPcelerative(II) > AspPrepetitive(II) > AspPfrequentative(II)

  [(...) adverbials[VP say [CP [(...) adverbials [VP ]]]]] (92) [(...) adverbials (MoodP speech act P [MoodP speech act ' [VP say]) (...) adverbials [VP ]]]]] (93) [IP (functional projections) [VP say [CP [IP (functional projections) [VP ]]]]] (94) [IP (functional projections) (MoodP speech act P [MoodP speech act ' [VP say])

  Order/say-IND.PST.3SG COMP to NEg bother-INF him. 'He ordered/said not to bother him.' Que is therefore expected after declarative SAPs. But it never occurs. See (38). IND.PST.1SG (*comp) COMP leave -SBJV.PRET.PRF.3SG Juan 'I said that Juan should leave.'

	(38) Dij-e	(*que)	que se fuer-a	Juan. 11
	say-

-o (que) a no molest-ar-le.

  Mom says that you should not let your sister go out.'But (40), where que and qué have the same pronounciation, should be excluded, as well. Yet it is not the case.

	39) Dic-e	mamá [que a tu hermana (que)
	Say-IND.PRS.3SG mom COMP to your sister COMP
	no la dej-es	salir]. 12
	not her let-SBJV.PRS.2SG go_out-INF
	'

(40) Me dij-o *(que) qué hab-ia pasado. To me say -IND.PST.3SG *(comp) what happen-IND.PLUPERFECT 'He asked me what happened.'

  56) Sincèrement, Anne a trompé Jérôme. Eric thinks that Anne has, allegedly, sold her phone.We must now deal with further objections. We assumed above that the same effects should appear at lower levels. (60) is strange to most French speakers. Since penser and probablement rank among the same class of epistemic items, it was expected that they would not cooccur. Likewise (61), where the adverb is in the matrix clause, is ruled out by our theory. But why is (60) for everyone more acceptable than (61)?

		Sincerely,	Anne deceived Jérôme.
	(57)	?? Eric a dit que sincèrement Anne avait trompé	Jérôme.
		Eric said that sincerely	Anne had deceived Jérôme.
	(58) Anne a, paraît-il, vendu son téléphone.
		Anne has allegedly sold her phone.
	(59)	?? Eric pense que Anne a, paraît-il, vendu son téléphone.
	(60)	? Eric pense que Anne a probablement vendu son téléphone.
		Eric thinks that Anne has probably	sold her phone.
	(61)
		Eric thinks probably	that Anne has sold her phone.
	(62) Eric a sincèrement dit que Anne avait trompé	Jérôme.
		Eric has sincerely	said that Anne had deceived Jérôme.

* Eric pense probablement

16

que Anne a vendu son téléphone.

  Eric pense que Anne a probablement acheté un téléphone.

	Eric thinks that Anne has probably	bought a phone
	pour son mari	dans le train.
	for her husband in the train.
	(67) Eric pense que Anne a acheté un téléphone dans le train
	Eric thinks that Anne has bought a phone	in the train
	probablement pour son mari.
	probably	for her husband.
	(68) Eric pense que Anne a acheté un téléphone pour son mari
	Eric thinks that Anne has bought a phone	for her husband
	probablement dans le train.
	probably	in the train.

  Eric a dit sincèrement que Anne avait trompé Jérôme. Eric has said sincerely that Anne had deceived Jérôme.

	(74) Eric a sincèrement dit que Anne avait trompé	Jérôme.
		Eric has sincerely said that Anne had deceived Jérôme.
	(75)	?? Eric a dit que sincèrement Anne avait trompé	Jérôme.
		Eric said that sincerely Anne had deceived Jérôme.
	(76)
				That yields (74) or
	(76).
	(72) Sincèrement, Anne a trompé Jérôme.
	(73)	Sincerely, * Eric pense probablement 17 que Anne a vendu son téléphone. Anne deceived Jérôme.
		Eric thinks probably	that Anne has sold her phone.

  Eric a dit que Anne avait probablement trompé Jérôme. Eric has said that Anne had, probably, deceived Jérôme.The first two are slightly marginal, maybe due to their proximity with the highest level. The last one is perfect. The hierarchy is respected with penser as well, since the acceptability increases in the same order: (85), (86), (87). Back to the Spanish dataIf we now go back to (38), repeated here as (88) for convenience's sake, we can provide a semantic explanation of the agrammaticality of the que-doubling. The fact that decir (say) takes as complement a proposition, is reflected within the syntax as the appearance of a single que. Employing another que would boil down to quoting a proposition. But what can be quoted is a speech act, something that has an illocutionary force.

	) (83) (86) (87) Therefore, the level unavailable to penser is the propositional level, and it follows from this ? Eric a dit que Anne avait, malheureusement, trompé Jérôme. Eric has said that Anne had, unfortunately, deceived Jérôme. ? Eric a dit que Anne avait, paraît-il, trompé Jérôme. Eric has said that Anne had, allegedly, deceived Jérôme. * Eric pense que Anne a, malheureusement, vendu son téléphone. Eric thinks that Anne has, unfortunately, sold her phone. ?? Eric pense que Anne a, paraît-il, vendu son téléphone. Eric thinks that Anne has, allegedly, sold her phone. ? Eric pense que Anne a probablement vendu son téléphone. Eric thinks that Anne has probably sold her phone. that penser should embed something lower such as a state of affairs or an event (see Section 5). 4.5.2. (88) Dij-e (*que) que se fuer-a Juan. 20 say-IND.PST.1SG (*comp) comp leave -SBJV.PRET.PRF.3SG Juan (84) (85) 'I said that Juan should leave.'

  The aorist would have expressed aspect and the clause would have had a different meaning, namely 'I consider that I am starting leaving…'. GEN.F.SG kingship-GEN.SG the-DAT older-DAT leave-INF.AORISTE 'I consider that I left to your older brother a greater power and the title of king.'

	(89) Nomiz-ô	archê-n		meizô	kai tounam-a
	think-IND.PRS.1SG power-ACC.F.SG greater-ACC.F.SG and the.name-ACC.PL
	t-ês	basilei-as	t-ô	presbuter-ô katalip-ein. 23
	the-


Carine Chavey

Lluis Fajas

teaching and research institutions in France or abroad, or from public or private research centers.

CXCL5 drives obesity to diabetes, and further.


Christophe Crespelle
email: christophe.crespelle@lip6.fr

Philippe Gambette
email: philippe.gambette@lirmm.fr

Unrestricted and Complete Breadth-First Search of Trapezoid Graphs in O(n) Time

Keywords: Breadth-First Search, trapezoid graphs, permutation graphs, interval graphs, shortest paths, graph algorithms

We present an O(n) Breadth-First Search algorithm for trapezoid graphs, which takes as input a trapezoid model and any priority order on the vertices. Our algorithm is the first able to produce any BFS-tree, and not only one specific to the model given as input, within this complexity. Moreover, it produces all the shortest paths from the root of the BFS-tree to the other vertices of the graph.

Introduction

Breadth-First Search (BFS for short) is probably the most famous graph algorithm, and also one of the most basic ones. Nevertheless, it turns out to be useful in many more sophisticated graph algorithms and in many contexts. One may think that there is nothing to do to lower the O(n + m) time complexity of the BFS algorithm, as, anyway, every edge of the graph should be traversed in order to perform the search correctly. This is not required for some well-structured graph classes that admit O(n) space representations, such as trapezoid graphs.

This class is a proper generalization of both permutation graphs and interval graphs, which are extensively studied; the main reason being that they naturally appear in many contexts such as scheduling, genomics, phylogeny and archeology [START_REF] Golumbic | Algorithmic Graph Theory and Perfect Graphs[END_REF]. Moreover, because of their strong but non-trivial structure, they also constitute a case worth to be studied before generalizing results to wider graph classes.

Here, we design the first algorithm able to produce any Breadth-First Search of a trapezoid graph, regardless of the model given as input, in O(n) time. This is achieved by making part of the input a priority order σ on the vertices, according to which the ties between neighbors of the vertex currently examined by the BFS will be broken. Moreover, our algorithm gives not only one but all possible shortest paths between any vertex of the graph and the root of the BFS-tree, which is a feature of high interest in practice for many problems.

Efficient implementations of BFS for these classes of graphs have already been studied: [START_REF] Rhee | Efficient algorithms for finding depth-first and breadthfirst search trees in permutation graphs[END_REF] showed that BFS can be implemented in O(n) time for permutation graphs, but their algorithm can only produce a single BFS-tree, which is not general at all and reflects the particular structure of their algorithm: it is always a caterpillar (a tree with a unique internal node at each level) rooted at the vertex whose upper endpoint is leftmost in the permutation diagram. [START_REF] Liang | Steiner set and connected domination in trapezoid graphs[END_REF] improved this result by giving an algorithm, having the same complexity, that is general to trapezoid graphs and can produce a tree T rooted at any vertex r of the graph. But again, the tree T produced is always the same and is strongly constrained: it is the union of four caterpillars having the same root r. [START_REF] Chao | An optimal EREW parallel algorithm for computing breadth-first search trees on permutation graphs[END_REF] showed that a parallel algorithm achieves a better complexity for the problem, but the tree produced is exactly the same as in [START_REF] Rhee | Efficient algorithms for finding depth-first and breadthfirst search trees in permutation graphs[END_REF]. Concerning Depth-First Search, the situation is similar: [START_REF] Rhee | Efficient algorithms for finding depth-first and breadthfirst search trees in permutation graphs[END_REF][START_REF] Chen | A linear time algorithm for finding depth-first spanning trees on trapezoid graphs[END_REF] give efficient implementations (O(n) time in [START_REF] Chen | A linear time algorithm for finding depth-first spanning trees on trapezoid graphs[END_REF]) but can only produce a single tree whose structure is very particular among all possible trees.

Preliminaries

Without loss of generality, we can make some restrictions and simplifications in the description of our algorithm. First, unlike the standard BFS algorithm, the tree first produced by our algorithm is unordered, that is, there is no order on the children of a vertex in the tree, while, in the standard BFS-tree, these children are ordered according to their discovery time in the search. In order to get the desired ordered tree, we can proceed as follows at the end of the algorithm. We parse order σ from the first to the last vertex, and for each vertex, we remove it from the list of children of its father and insert it again at the end of this list. This takes O(n) time and orders the lists of children with regard to σ, as desired. As a consequence, in the following, we only consider the construction of the unordered tree.

In addition, we focus on the case where the input graph is connected. If it is not, our algorithm performs the BFS of the connected component of the first vertex in σ, without any modification of its description. Then, the algorithm can go on starting from the first non-visited vertex of σ. Finding this vertex can be done in constant time by maintaining along the algorithm the list of non-visited vertices, ordered with regard to σ.

Definitions and Notations. All graphs considered here are finite, undirected, loopless and simple. V is the vertex set of graph G and E is its edge set, which we denote by G = (V, E). Throughout the paper, n stands for |V |. An edge between vertices x and y will be arbitrarily denoted xy or yx. The neighborhood of x is denoted N (x). T denotes the BFS-tree to be produced. The depth of node u in T is its distance from the root. The set of vertices at depth i in T will be denoted T i (T 0 contains only the root of T ). For a linear ordering σ on a set S, we denote min(σ) (resp. max(σ)) for the first (resp. last) element of σ. For s ∈ S, s -(resp. s + ) denotes for the predecessor (resp. successor) of s in σ. The interval of σ made of vertices between a and b, with a ≤ σ b, is denoted a, b . The list L containing elements x 1 , . . . , x k is denoted

L = [x 1 , . . . , x k ]. The concatenation of two lists L 1 , L 2 is denoted L 1 .L 2 .
A trapezoid model of a graph G is a set of trapezoids between two horizontal lines (two endpoints on the upper line and two endpoints on the lower line) together with a one to one mapping onto the set of vertices of G, such that there is an edge between vertices x and y in G iff their corresponding trapezoids intersect. A trapezoid graph is a graph admitting such a model. Note that a trapezoid model can be computed from the graph in time O(n 2 ) using the algorithm of [START_REF] Ma | An O(n 2 ) time algorithm for the 2-chain cover problem and related problems[END_REF]. The class remains the same if the trapezoids are required to be closed and to have distinct integer endpoints between 1 and 2n on both lines. All models considered here satisfy this restriction. More precisely, in the following, a trapezoid model will be considered as a couple (π 1 , π 2 ) of orders on some subsets of trapezoid endpoints of the model: π 1 is the left to right order of the endpoints on the upper line, and π 2 is the left to right order of the endpoints on the bottom line. Each vertex v is associated with the four endpoints of its corresponding trapezoid, which are denoted v l 1 , v r 1 , v l 2 and v r 2 for the top-left, top-right, bottom-left and bottom-right endpoint respectively. This provides an efficient encoding of the graph that takes O(n) space and allows to answer adjacency queries between any pair of vertices in O(1) time. In the sequel, we often identify vertices and their associated trapezoids.

BuildTree(π1, π2, σ) 1. x ← min(σ); ord(x) ← 1; color x in gray 2. initialize I and Γ with (x l 1 , x r 1 , x l 2 , x r 2 ) 3. For all y ∈ N (x) Do parent(y) ← x; color y in gray; update(Γ, y) 5. While I = Γ Do 6.

Γnew ← Γ; Ex ← ∅ 7. If α l 1 <π 1 a l 1 Then PutInTree(α l 1 , a l- 1 , π1, l, Q l 1 )
8.

If β r 1 >π 1 b r 1 Then PutInTree(β r 1 , b r+ 1 , π1, r, Q r 1 )
9.

If

γ l 2 <π 2 c l 2 Then PutInTree(γ l 2 , c l- 2 , π2, l, Q l 2 ) 10. If δ r 2 >π 2 d r 2 Then PutInTree(δ r 2 , d r+ 2 , π2, r, Q r 2 )
11.

AssignOrd(Q l 1 , Q r 1 , Q l 2 , Q r 2 ); color Ex in gray 12. I ← Γ; Γ ← Γnew Figure 1: Routine BuildTree. Lists Q l 1 , Q r 1 , Q l 2 , Q r 2 and
Ex are global variables, as well as

I = (a l 1 , b r 1 , c l 2 , d r 2 ), Γ = (α l 1 , β r 1 , γ l 2 , δ r
2 ) and Γnew which contain quadruplets of endpoints.

PutInTree(u side k , v t k , π k , side, Q) 1. p ← u; Q ← [p] 2. For y s k from u side k to v t k in π k Do 3.
If y white & s = side & p <prior parent(y) Then

Breadth-First Search of Trapezoid Graphs

The input of our algorithm is a trapezoid graph G (assumed to be connected w.l.o.g.) given by its model (π 1 , π 2 ) and a linear order σ on V . The first vertices of σ are those having highest priority, in particular, the first visited vertex is the minimum of σ. We first focus our attention on the algorithm building the unordered BFS-tree T . The structure computing and storing all shortest paths from the root of T to the other vertices of the graph is easy to design afterwards. This is done in Section 3.3.

Overview of the algorithm

Our algorithm computes the unordered BFS-tree T of G level by level: iteration number i of the main loop of Routine BuildTree (Line 5, cf. Fig. 1) builds level T i+1 . To that purpose, we parse the model of the graph pieces by pieces as explained below. We maintain along the algorithm two intervals in each of the two orders of the model: Γ 1 is the minimal interval of π 1 containing the upper endpoints of the vertices placed in the tree so far, namely 0≤j≤i T j , and I 1 is the interval containing the upper endpoints of the vertices of 0≤j≤i-1 T j ; intervals Γ 2 and I 2 are similarly defined in π 2 for lower endpoints.

Each level of the tree is built by parsing the endpoints in Γ 1 \I 1 and Γ 2 \I 2 , which are split in four intervals, thanks to the four calls to Routine PutInTree (Lines 7 to 10 of BuildTree). The new vertices encountered during this parse are exactly those of T i+1 , which are then assigned their parent in T . It is important to note that our algorithm does not discover the vertices in the same order as the standard BFS would do. Despite of this, we are able to determine, for each vertex, its correct parent in the BFS-tree, thanks to function ord. ord numbers a subset of vertices in each level of the tree computed so far, except in the last one T i . Its essential property is that, at the beginning of the i th iteration of the main loop, every vertex of level T i-1 having children in T is numbered and the order induced by ord on these vertices is exactly the order in which the standard BFS discovers them. Together with order σ, it allows to determine the parent of the vertices of level T i+1 and to assign their ord value to vertices of T i (at least to those having children in T ). Note that a vertex may be assigned a parent twice by our algorithm: in this case, the second one is the correct one.

Before the algorithm starts, for every vertex y, parent(y) is initialized with ⊥, and y is colored white. During the algorithm, vertices are colored gray once they have been assigned their correct parent in the tree. This is done at the end of the main loop of Routine BuildTree (Line 11). We denote by (a l 1 , b r 1 ) (resp. (α l 1 , β r 1 ), (c l 2 , d r 2 ), (γ l 2 , δ r 2 )) the left and right endpoint of I 1 (resp. Γ 1 , I 2 , Γ 2 ). Remark that this notation is coherent, since it is a straightforward property of our algorithm that the left (resp. right) endpoint of any of these four intervals is always the left (resp. right) endpoint of some trapezoid of the model. For y ∈ V and a quadruplet X = (l 1 , r 1 , l 2 , r 2 ) of endpoints such that l 1 , r 1 ∈ π 1 and l 2 , r 2 ∈ π 2 , procedure update(X, y) executes the instructions l j ← min πj (l j , y l j ) and r j ← max πj (r j , y r j ), for j ∈ {1, 2}. Function ord takes integer values which are assigned by Procedure AssignOrd. Order < prior is defined by u < prior v iff ord(parent(u)) < ord(parent(v)) or ord(parent(u)) = ord(parent(v)) and u < σ v . By convention, element ⊥ is the greatest for order < prior .

The arguments of AssignOrd are four lists (not necessarily disjoint), which are merged by the procedure into a single one Q glob , without repetition and sorted according to order < prior (defined above), the first element of the list being the least one for < prior . Once list Q glob is obtained, for each vertex x contained in it, the procedure assigns ord(x) with the rank of x in Q glob .

Correctness

Our proof of correctness is based on two invariants. The first one below shows that the set of new vertices discovered during an iteration of the main loop of Routine BuildTree is exactly the next level of the BFS-tree T . The second one implies that those vertices are assigned their correct parent in T by the algorithm.

(i) (ii) (iii) (iv)
Invariant 1. For any i ≥ 2, at the beginning of the i th iteration of the main loop, the following properties hold.

1. I 1 (resp. I 2 ) is the minimal interval of π 1 (resp. π 2 ) containing both upper endpoints (resp. lower endpoints) of the vertices of 0≤j≤i-1 T j ; and 2. Γ 1 (resp. Γ 2 ) is the minimal interval of π 1 (resp. π 2 ) containing both upper endpoints (resp. lower endpoints) of the vertices of 0≤j≤i T j ; and 3. set 0≤j≤i T j is equal to the set of vertices with at least one endpoint in I 1 ∪ I 2 , and is exactly the set of gray vertices.

Remark: For i = 1, the first two properties of Invariant 1 are satisfied, but even though 0≤j≤i T j is the set of gray vertices, Property 3 is not satisfied. Nevertheless, for any i ≥ 2 the three properties hold. In order to prove it, we will need the following lemma.

Lemma 1. Let i ≥ 1. At the beginning of the i th iteration of the main loop of Routine BuildTree, if the conditions of Invariant 1 are satisfied or if i = 1, then the set of white vertices with at least one endpoint in Γ 1 ∪ Γ 2 is exactly T i+1 .

Proof. Let y be a white vertex with at least one endpoint

y s k in Γ 1 ∪ Γ 2 .
If Invariant 1 is satisfied, then from Property 3, vertices having at least one endpoint in I 1 ∪ I 2 are gray. This is still true for i = 1 since those vertices belong to N (x). It follows that the endpoint y s k of y belonging to Γ 1 ∪ Γ 2 is in (Γ 1 \ I 1 ) ∪ (Γ 2 \ I 2 ). Let us examine the case where k = 1 and y s 1 is such that b r 1 < π1 y s 1 < π1 β r 1 (illustrated in Figure 3(ii) with y s k = e l 1 ), the other cases are similar. Since y is white, y ∈ T i and therefore is not adjacent to any vertex of T i-1 , which implies that y l 1 > π1 b r 1 and y l 2 > π2 d r 2 . Moreover, since b r 1 = β r 1 , Property 1 and 2 of the invariant ensures that β ∈ T i . If i = 1, from Property 3 of the invariant, β has at least one endpoint in I 1 ∪I 2 . It follows that

β l 1 < π1 b r 1 or β l 2 < π2 d r 2 .
In the former case, since β l 1 < π1 y l 1 < π1 β r 1 , y is adjacent to β. In the latter case, since y l 1 < π1 β r 1 and

β l 2 < π2 d r 2 < π2 y l 2 , y is again adjacent to β. If i = 1, β ∈ T 1 is adjacent to x, which implies that β l 1 < π1 x r 1 or β l 2 < π1 x r 2 .
As above, it follows that β is adjacent to y. Thus, in every case, y ∈ T i+1 .

Conversely, let y ∈ T i+1 . From Property 3 of the invariant, y is white, which is also clearly the case if i = 1, since y ∈ N (x). Suppose for contradiction that y has no endpoint in Γ 1 ∪ Γ 2 . Since y is not adjacent to x, the two endpoints of y are on the same side of Γ 1 (resp. Γ 2 ) in π 1 (resp. π 2 ). Moreover, the endpoints of y cannot lie on one side of Γ 1 in π 1 and on the other side of Γ 2 in π 2 . Since, from Property 2 of the invariant, vertices of T i have both upper endpoints in Γ 1 and both lower endpoints in Γ 2 , it follows that y is not adjacent to any vertex of T i . This is a contradiction with the fact that y ∈ T i+1 . Thus, y has at least one endpoint in Γ 1 ∪ Γ 2 .

2

Let us now prove that Invariant 1 holds for any i ≥ 2. Let i ≥ 1 such that either i = 1 or the invariant holds, we show that the invariant holds for i + 1. Since Property 2 holds at the beginning of the i th iteration of the loop and since I is set to the old value of Γ at the end of the loop, it follows that Property 1 holds at the end of the i th iteration. ¿From Lemma 1, the white vertices encountered during the i th iteration of the loop are exactly the vertices of T i+1 . Moreover, at the end of the loop, Γ is assigned the value of Γ new that has been computed by the calls to update(Γ new , y) at Line 4 of PutInTree when the endpoint of a new white vertex is encountered. Consequently, at the end of the i th iteration, Γ 1 and Γ 2 are the least intervals containing both endpoints of vertices of T i+1 , respectively in π 1 and π 2 . Thus, Property 2 holds. Lemma 1 ensures that, at the beginning of the i th iteration, the set of vertices with at least one endpoint in Γ 1 ∪Γ 2 is 0≤j≤i+1 T j . Since, at the end of the loop, I is set to the old value of Γ and vertices of T i+1 are colored in gray, then Property 3 holds at the end of the i th iteration. And so does the invariant at the beginning of the i + 1 th iteration, which proves that it holds for any i ≥ 2.

Invariant 2 claims that function ord gives the order in which the standard BFS algorithm discovers vertices of the graph. In order to prove it, we need the following lemma, which characterizes the neighborhood in T i of the vertices of T i+1 during the i th execution of the main loop.

Lemma 2. Let i ≥ 1, let y be a vertex of T i+1 and z be a vertex of T i . y and z are adjacent iff there exists some call to PutInTree(u side k , v t k , π k , side, Q) occurred during the i th iteration of the main loop such that the non-side endpoint of y and the side endpoint of z both lie between u side k and v t k in π k , and z's endpoint is visited before y's.

Before proving Lemma 2, it is worth to emphasize on the fact that during a call to PutInTree(u side k , v t k , π k , side, Q), we examine only the side endpoints of gray vertices (Line 5) and the non-side endpoints of white vertices (Line 3). All nodes encountered, white or gray, can be correctly handled regardless of their other endpoint. This is possible because the non-examined endpoint appears only in calls where the examined endpoint does as well, as stated by the following remark.

Remark: During any execution of PutInTree(u side k , v t k , π k , side, Q), if the non-side (resp. side) endpoint of a gray (resp. white) vertex is encountered, then its side (resp. non-side) endpoint is encountered too during the same execution of PutInTree.

Indeed, consider, without loss of generality, the case of the first call to PutInTree (Line 7 of BuildTree) between α l 1 and a l- 1 . If the right endpoint z r 1 of a gray vertex z is encountered, since all the endpoints of gray vertices in π 1 lie within Γ 1 (see Invariant 1), then necessarily the left endpoint z l 1 of z is such that α l 1 ≤ π1 z l 1 < π1 z r 1 and therefore has been encountered before during the current execution of PutInTree. Similarly, let y be a white vertex whose left endpoint y l 1 is encountered. We have α l 1 < π1 y l 1 < π1 a l 1 . Since y is white, y ∈ T i+1 and y is not adjacent to x. Consequently, if i = 1, since a l 1 = x l 1 , we have y r 1 < π1 a l 1 . If i ≥ 2, since y has no endpoint in I 1 (see Invariant 1) and is not adjacent to x, we have again y r 1 < π1 a l 1 . Thus, in every case, the right endpoint y r 1 of y is encountered later in the current execution of PutInTree.

Proof of Lemma 2: For any i ≥ 1, vertices having an endpoint in I 1 ∪ I 2 are gray at the beginning of the i th iteration of the loop. Since y ∈ T i+1 is white, y has no endpoints in I 1 ∪ I 2 . Moreover, since y ∈ T i+1 and i + 1 ≥ 2, y is not adjacent to x. It follows that either b r 1 < π1 y l 1 and d r 2 < π2 y l 2 , or y r 1 < π1 a l 1 and y r 2 < π2 c l 2 . Let us consider the first case, the second one is symmetric.

If y and z are adjacent, then clearly y l 1 < π1 z r 1 or y l 2 < π2 z r 2 . Without loss of generality, assume that y l 1 < π1 z r 1 . Since z ∈ T i , from Property 2 of Invariant 1, z r 1 ∈ Γ 1 , and so y l 1 ∈ Γ 1 . Then, the endpoints of y and z are encountered in a same execution of PutInTree, and z is visited first within this execution.

Conversely, if y and z are not adjacent, the trapezoid of z lies either entirely to the right of the trapezoid of y, or entirely to its left. The former case is impossible as z ∈ T i is adjacent to some vertex of T i-1 , whose trapezoid, which is included in I 1 ∪ I 2 from Property 1 of Invariant 1, lies entirely to the left of y. In the latter case, where the trapezoid of z lies entirely to the left of the trapezoid of y, no endpoint of z is visited before an endpoint of y in any execution of Routine PutInTree, which ends the proof of the lemma. Invariant 2. For any i ≥ 1, at the beginning of the i th iteration of the main loop, the subset O i-1 of vertices of T i-1 for which ord is defined contains all the vertices of T i-1 that have children in T . And the order induced by ord on vertices of O i-1 is exactly the order of visit of those vertices by the standard BFS algorithm.

Proof. Since ord(x) is initialized to 1 at Line 1 of Routine BuildTree, the invariant clearly holds for i = 1. Suppose it holds for some i ≥ 1. Then, since ord is defined for every parent of the vertices of T i , order < prior is defined for all vertices of T i and is precisely the BFS order of visit of those vertices. And since, during the i th iteration of the loop, AssignOrd assigns the values of ord to a subset, denoted O i , of vertices of T i by increasing < prior , it follows that the order induced by ord on O i is the order of visit by the standard BFS algorithm. Now, let z ∈ T i \O i , we will show that z has no children in T . In other words, we want to prove that z is not the parent of any of its neighbors y ∈ T i+1 . From Lemma 2, since y and z are adjacent, they are encountered in a same execution of PutInTree occurred during the i th iteration of the main loop. Assume without loss of generality that it was in the first call to PutInTree (Line 7 of BuildTree), between α l 1 and a l- 1 , the other cases are similar. By definition, since z ∈ O i , it is not assigned a value for ord in the i th iteration of the main loop. Then, necessarily, z is not placed in Q at Line 6 of PutInTree, which implies that the test of Line 5 is negative. Since z ∈ T i , z is already gray when this test is performed. It follows that the test is negative because there exists some gray vertex u ∈ T i such that α l 1 ≤ π1 u l 1 < π1 z l 1 and u < prior z. Lemma 2 states that the side endpoint of z is visited before the non-side endpoint of y in the considered execution of PutInTree. That is, in the present case, z l 1 < π1 y r 1 . This implies that u l 1 < π1 y r 1 , and Lemma 2 concludes that y is also adjacent to u. Finally, since u < prior z, z is not the parent of y. 2

We can now prove the correctness of our algorithm. Clearly, the first two levels of the tree (T 0 and T 1 ) are properly built by the initialization phase of Routine Build-Tree (Line 1 to 4). Lemma 1 shows that, for all i ≥ 1, the vertices discovered during the i th iteration of the main loop of BuildTree are exactly those of T i+1 . In order to complete the proof of correctness, we have to show that these vertices are assigned their correct parent in T . Parent assignments occur at Line 4 of Routine PutInTree(u side k , v t k , π k , side, Q). Every vertex of T i+1 (white vertices) is assigned a parent. Indeed, when the non-side endpoint of a white vertex y is encountered, the test of Line 3 is true iff p < prior parent(y); and in particular, this is true if y has no parent (i.e. parent(y) = ⊥), since, by definition, ⊥ is the greatest element for < prior .

The parent assigned to vertex y is p, which is initialized with u at Line 1 and is maintained to be the least gray node for order < prior among the gray nodes whose side endpoint has been visited so far during the current execu-tion of PutInTree (Lines 5 and 6). From its definition, and from Invariant 2, order < prior is exactly the order in which the standard BFS algorithm discovers the vertices of T i . Then, from Lemma 2, p is the first vertex visited by the standard BFS algorithm among the vertices of T i ∩ J adjacent to x, where J is the set of vertices with an endpoint lying between u side k and v t k in π k . The non-side endpoint of a white vertex y may be encountered in two different executions of Routine PutInTree, once in each of the two orders π 1 and π 2 . The test p < prior parent(y) of Line 3 of PutInTree guarantees that it is assigned a new parent p iff p has been visited by the standard BFS algorithm before the previously assigned parent of y in T . Since from Lemma 2, every neighbor z ∈ T i of y is encountered in some call to PutInTree where y is encountered too, it follows that y is assigned as parent the first vertex visited by the standard BFS algorithm among vertices of T i ∩ N (y). Thus, the tree T produced by our algorithm is the correct BFS-tree.

Computing all shortest paths

In the standard algorithm, it is possible to obtain, within O(n + m) time complexity, a data-structure encoding all the shortest paths from the root x of T to the other vertices of the graph. This is done by storing, for each vertex y, the subset S y of its neighbors that belong to a shortest path from y to x. This set S y is nothing but the set of vertices of level T i-1 , with T i being the level of y, that are adjacent to y. In the standard BFS algorithm, set S y is stored in a list, and the total space needed to do so for all vertices of the graph is O(n + m).

In our case, due to the structure of the intersection model, sets S y can be stored more efficiently, within a total O(n) space. Moreover, this data-structure can be computed without penalizing the complexity of our algorithm.

Indeed, from Lemma 2, set S y is exactly the set of vertices of T i-1 whose side endpoint is encountered before the non-side endpoint of y in each of the executions of PutInTree where y is encountered, during the i -1 th iteration of the main loop. Thus, we can store S y in the following way. For each level T i , we build four lists L i c , with c ∈ 1, 4 , corresponding to the four calls to PutInTree occurred during the i -1 th iteration. We build L i c by pushing on a stack (different for each call) each vertex of T i-1 whose side endpoint is encountered during execution number c of PutInTree. When we find the non-side endpoint of some vertex y of T i , y is assigned a pointer to the cell of list L i c (under construction) which is the current top of the stack. Doing so, we are able to know which are the vertices of T i-1 whose side endpoint has been encountered before the non-side endpoint of y in the present execution of PutInTree. In this way, at the end of the computation, we can get set S y in O(|S y |) time by merging the at most two partial lists given by the pointers assigned to y towards lists L i c , c ∈ 1, 4 . It is worth to note that set S y can be handled by a constant space description consisting of the mentioned (at most) two pointers. The total size of the four lists assigned to level T i is dominated by the number of vertices in T i-1 . Thus the size of the additional space needed to store the whole data structure is O(n).

In practice, it may be desirable to follow the shortest paths in the other way: from the root of T to the other vertices of G. To this purpose one must store, for each vertex at level i, its set of neighbors at level i+ 1. This can be done very similarly to what precedes. During the i th iteration of the loop, for each execution of PutInTree, build the list of white vertices encountered by pushing them on a stack. When a gray vertex z is encountered, assign to it a pointer to the top of the stack: the neighbors of z at level i+1 are the white vertices that are above this pointer in the stack (Lemma 2).

Complexity

First of all, note that the computation of the lists storing all shortest paths from nodes of the graphs to the root x of T only requires constant additive extra-time in the treatment of an endpoint. This does not change the overall complexity of the algorithm and, for sake of simplicity, we do not take it into account anymore in the complexity analysis.

The complexity of Routine BuildTree is O(n).

∈ {Q l 1 , Q r 1 , Q l 2 , Q r 2 }
being one of its arguments is already sorted according to order < prior . This is a property of PutInTree, which produces Q , guaranteed by the test y < prior p at Line 5 and the affectations of Line 6. It follows that AssignOrd can be implemented to merge the four lists in a single one, sorted according to < prior , in

O(|Q l 1 | + |Q r 1 | + |Q l 2 | + |Q r 2 |) = O(|B|)
time, using classic technique for union of sorted lists. Finally, the running time of an iteration of the main loop is O(|B|), and since all the B's considered until the end of the loop are pairwise disjoint, it follows that the main loop, as well as Routine BuildTree, runs in O(n) time.

Conclusion and Perspectives

We showed that it is possible to achieve a complete and unrestricted BFS of a trapezoid graph in O(n) time. It opens the way to improvement and simplification of several problems on this class of graphs, which make use of a BFS step in their solutions. Let us cite as example All Pairs Shortest Paths [START_REF] Mondal | An optimal algorithm for solving all-pairs shortest paths on trapezoid graphs[END_REF] and its variations (Next-to-Shortest [START_REF] Barman | An efficient algorithm to find next-to-shortest path on trapezoid graphs[END_REF], Almost Shortest [START_REF] Dragan | Estimating all pairs shortest paths in restricted graph families: A unified approach[END_REF]), biconnected components [START_REF] Liang | Finding biconnected components in O(n) time for a class of graphs[END_REF] and betweeness [START_REF] Brandes | A faster algorithm for betweenness centrality[END_REF].

Another perspective is to generalize these results to other graph classes such as circular-arc graphs and circle graphs for example, which are the circular generalizations of respectively interval graphs and permutation graphs. We believe that only few work is left to be done for solving the problem in O(n) time for circular-arc graphs, using the fact that deleting a vertex and its neighborhood from a circular-arc graph results in an interval graph. On the other hand, the case of circle graphs seems to be challenging, and solving it would certainly lead to new insight on the structure of this class of graphs.

4 . 5 .

 45 parent(y) ← p; Ex ← Ex.[y]; update(Γnew, y) If y gray & s = side & y <prior p Then 6. p ← y; Q ← [p].Q

Figure 2 :

 2 Figure 2: Routine PutInTree. side and t belongs to {l, r}, u side k and v t k are two endpoints, and Q is a list. Γnew and Ex are global variables initialized in Routine BuildTree. Note that according to our previously introduced notation u is the vertex corresponding to endpoint u side k and y is the vertex corresponding to endpoint y s k .

Figure 3 :

 3 Figure 3: A trapezoid graph (i), its trapezoid model (ii) labeled as in the beginning of the second iteration of the main loop of Algorithm 1, and two BFS trees: one respecting priority order (xβδdbeaα) (iii) and the other respecting priority order (xβδbdeaα) (iv).

  Let B denote (Γ 1 \ I 1 ) ∪ (Γ 2 \ I 2 ). At Line 3, we can get N (x) in O(n) time, by scanning π 1 and π 2 , and the running time of the initialization loop (Lines3 and 4) is O(|N (x)|) = O(n). In Routine PutInTree(u side k , v t k , π k , side, Q),all instructions take O(1) time, and the routine runs in O(| u side k , v t k |) time. This gives an O(|B|) time bound for the four calls of Lines 7 to 10 of BuildTree. Coloring list Ex also takes O(|B|) time. The complexity of procedure AssignOrd is a crucial point. It is important to note that any list Q