Cyclic Pregroups and Natural Language: a Computational Algebraic Analysis Claudia Casadio and Mehrnoosh Sadrzadeh 1 Faculty of Psychology, Chieti University, IT casadio@unich.it 2 Computing Laboratory, Oxford University, UK mehrs@comlab.ox.ac.uk Abstract. The calculus of pregroups is introduced by Lambek [1999] as an algebraic computational system for the grammatical analysis of natural languages. Pregroups are non commutative structures, but the syntax of natural languages shows a diffuse presence of cyclic patterns exhibited in different kinds of word order changes. The need of cyclic operations or transformations was envisaged both by Z. Harris and N. Chomsky, in the framework of generative transformational grammar. In this paper we propose an extension of the calculus of pregroups by intro- ducing appropriate cyclic rules that will allow the grammar to formally analyze and compute word order and movement phenomena in differ- ent languages such as Persian, French, Italian, Dutch and Hungarian. This cross-linguistic analysis, although necessarily limited and not at all exhaustive, will allow the reader to grasp the essentials of a pregroup grammar, with particular reference to its straightforward way of com- puting linguistic information. 1 Introduction In this paper we apply logical cyclic rules to the analysis of word order changes in natural languages. The need of some kind of cyclic operations or transformations was envisaged both by Harris [1966, 1968] and Chomsky [1981, 1986] for the treatment of the linguistic contexts referred to with the term movement. In the paper we present a formal approach to natural language based on two cyclic rules that hold in the systems of Noncommutative and Cyclic Multiplicative Linear Logic (NMLL,CyMLL), developed by Abrusci [1991, 2002] from Yetter [1990]. A critical move of this paper is to embed such cyclic rules into the calculus of Pregroups recently introduced by Lambek [1999, 2001, 2008]. The calculus has been succesfully applied to a variety of natural languages from English and German, to French and Italian, and others [see Casadio and Lambek 2008]. We show that the formal grammar obtained by so extending the pregroup calculus allows one to compute string of words belonging to various kinds of natural languages, deriving grammatical sentences involving different types of word order changes or movements, with particular reference to the way in which unstressed clitic pronouns attach to their verbal heads. Cross-linguistic evidence is provided comparing languages belonging to the Indo-European family, like Persian, on the one side, French and Italian, on the other, as representatives of the Romance group. Moreover the analysis is extended to include Dutch, as a representative of the West Germanic group, and Hungarian, as a represen- tative of the Uralic family, non related to the Indo-European languages. Such cross-linguistic prespective extends the results of preceding work [Casadio and Sadrzadeh 2011, Sadrzadeh 2010], and the analysis proposed for Dutch is new. We conclude with a short discussion of the logical and methodological con- nections of the present analysis to cyclic linear logic [Yetter 1990, Abrusci 1991, 2002]. 2 Cyclic rules for the Calculus of Pregroups 2.1 Pregroup grammar Pregroups are introduced by Lambek in [1999] as an alternative to the Syntactic Calculus, a well known model of categorial grammar largely applied in the fields of theoretical and computational linguistics; see e.g. Moortgat [1997], Morrill [2010]. The calculus of pregroups is a particular kind of substructural logic that is compact and non-commutative [Buszkowsi 2001, 2007]. Pregroups in fact are non conservative extensions of Noncommutative Multiplicative Linear Logic (NMLL) in which left and right iterated negations, equivalently left and right iterated adjoints, do not cancel [Abrusci 2001, Casadio 2001, Casadio and Lambek 2002, Lambek 2001, 2008]. A pregroup {G, . , 1, ` , r , →} is a partially ordered monoid in which each element a has a left adjoint a` , and a right adjoint ar such that a` a → 1 → a a` a ar → 1 → ar a where the dot “.”, that is usually omitted, stands for multiplication with unit 1, and the arrow denotes the partial order1 . In linguistic applications syntactic types (or categories) are assigned to the words in the dictionary of a language, the symbol 1 is assigned to the empty string of types, and the operation of multiplication is interpreted as linguistic concatenation. Adjoints are unique and the following results are proved (see Lambek [2008] for details) 1` = 1 = 1r , (a · b) = b · a ` , (a · b)r = b r · a r , ` ` a→b a→b b` → a` br → ar ` ` r r `` `` b →a , b →a , a →b , ar r → br r . 1 A partial order ‘≤’ (here denoted by the arrow ‘→’) is a binary relation which is reflexive: x ≤ x, transitive: x ≤ y and y ≤ z implies x ≤ z, and anti-symmetric: x ≤ y and y ≤ x implies x = y. We may read x ≤ y as saying that everything of type x is also of type y. The arrow is introduced to show the inference between types, like in type logical grammmars. Linguistic applications make particular use of the equation ar ` = a = a`r , allowing the cancellation of double opposite adjoints, and of the rules a`` a` → 1 → a` a`` , ar ar r → 1 → ar r ar contracting and expanding left and right adjoints respectively; just contractions are needed to check and determine if a given string of words is a sentence: a` a → 1 and a ar → 1 . A pregroup is freely generated by a partially ordered set of basic types. From each basic type a we form simple types by taking single or repeated adjoints: . . . a`` , a` , a, ar , arr . . . . Compound types or just types are strings of simple types. Like in categorial grammars we have two essential steps: (i) assign one or more (basic or compound) types to each word in the dictionary; (ii) check the grammaticality and sentencehood of a string of words by a calculation on the corresponding types, where the only rules involved are contractions and ordering postulates such as α → β (α, β basic types). Taking as basic types: n (noun), π (nominative argument), o (accusative argument), w (dative argument), λ (locative argument), i (infinitive verb), s (sentence), we obtain simple types such as n` , nr , π ` , π r , o` , or , . . . , and com- pound types such as (π r s o` ), the type of a transitive verb with subject in the nominative case and object in the accusative case. For example, the types of the constituents of the sentence “I saw him.” are as follows, where the subscript 1 in π1 means first person singular, and the subscript 2 in s2 indicates the past tense2 I saw him. π1 (π1r s2 o` ) o We say that a sentence is grammatical iff the computation (or calculation) of the types assigned to its words reduces to the type s, a procedure depicted by the under-link diagrams3 . 2.2 Cyclic rules in theoretical linguistics In the Sixties Zellig Harris developed a cyclic cancellation automaton [1966, 1968] as the simplest device to recognize sentence structure by computing strings of words through cancellations of a given symbol with its left (or right) inverse. 2 We analyze a sentence of the form SUBJ VP by assigning types (πk sj ), for j = 1, . . . ,7 denoting the seven basic tenses, and k denoting the six verbal persons (singular k = 1, 2, 3, plural k = 4, 5, 6). 3 These diagrams are reminescent of the planar poof nets of non-commutative linear logic, connecting the formulas, decorated by a left or right adjoint with their positive counterparts, by means of under-links that satisfy the requirements of parallelism and planarity (Abrusci 2002, Lambek 1999, 2008, Buszkowski 2007). The formalism proposed by Harris is sufficient for many languages, requiring just string concatenation for sentence derivation, but the same limitations of context free grammars are met [Francez and Kaminski 2007, Buszkowski and Moroz 2008]. Different kinds of cyclic transformations were explored by Chom- sky [e.g. 1981] to compute constituents movement in long distance dependencies. As argued by Lambek [2008], the analysis of modern European languages re- quires that word symbols (logical types) take double superscripts, like in Harris [1968], or the double adjoints defined in pregroup grammar, wherever Chom- sky’s approach postulates a trace. The calculus of pregroups meets in this sense the requirements of Chomsky’s transformational grammar expressing traces by means of double adjoints. 2.3 Introducing cyclic rules into pregroups We extend the pregroup calculus with two cyclic rules that will allow us to anal- yse a variety of movement phenomena in natural languages. It is important to point out that the addition of cyclic rules is not equivalent to the reintroduc- tion of the structural rule of Commutativity into the pregroup calculus (a logic without structural rules like the Syntactic Calculus). These rules are derivable into NMLL (or also CyMLL) cf. Abrusci [2002] ` Γ, ∆ ` Γ, ∆ (rr) (``) ` ∆+2 , Γ ` ∆, Γ −2 In the notation of pregroups (positive formulae as right adjoints and negative formulae as lef t adjoints), the formulation of the two cyclic rules becomes (1) qp ≤ prr q (2) qp ≤ pq `` The monoid multiplication of the pregroup is non-commutative, but if we add to the pregroup calculus the cyclic rules defined above as metarules, then we obtain a limited form of commutativity, for p, q ∈ P . Metarules are postulates introduced into the dictionary of the grammar to simplify lexical assignments and make syntactic calculations quicker: the types assigned to the words of a given language are assumed to be stored permanently in the speaker’s ‘mental’ dictionary; to prevent overloading this mental dictio- nary, the grammar includes metarules asserting that, if the dictionary assigns a certain type to a word, then this word may also have certain other types. The effect of the two cyclic metarules is that the cyclic type of each verb form is derivable from its original type. 3 Word Order and Cyclicity in Natural Languages In the following section we present a cross-linguistic analysis comparing lan- guages belonging to the Indo-European family, like Persian, on the one side, French and Italian, on the other side, as representatives of the Romance group. The analysis is also extended to include Dutch, as a representative of the West Germanic group, and Hungarian, as a representative of the Uralic family, which is not related to the Indo-European family. 3.1 Cross-linguistic motivations In Persian the subject and object of a sentence occur in pre-verbal position (Per- sian is a SOV language), but they may attach themselves as clitic pronouns to the end of the verb and form a one-word sentence. By doing so, the word order changes from SOV to VSO. A similar phenomenon happens in Romance lan- guages like Italian and French, but the movement goes in the opposite direction: verbal complements occurring in post-verbal position, can take a clitic form and move to a pre-verbal position. These movements have been accounted for in the pregroup grammar for French [Bargelli and Lambek 2001] and Italian [Casadio and Lambek 2001] by assigning clitic words types with double adjoints. In this paper we present a different approach offering a unified account of clitic movement by adding two cyclic rules (or metarules) to the lexicon of the pregroup grammar. The import of these rules is that the clitic type of the verb is derivable from its original type. Clitic Rule (1): If pr q is the original type of the verb, then so is qp` . Clitic Rule (2): If qp` is the original type of the verb, then so is pr q. The over-lined types p` , pr are introducend as a notational convenience to dis- tinguish the clitic pronouns from the non-clitic stressed pronouns or arguments. For any clitic pronoun p, we postulate the partial order p ≤ p to express the fact that a clitic pronoun is also a kind of pronoun. We assume that for all p, q ∈ P , we have pq = p q. 3.2 Clitic movement in Persian In Persian the subject and object of a sentence occur in pre-verbal position (Persian is a SOV language), but they may attach themselves as clitic pronouns to the end of the verb and form a one-word sentence (word order changes from SOV to VSO). The clitic clusters (pre-verbal vs. post-verbal) for the sentence I saw him, “man u-ra didam” in Persian, exhibit the following general pattern: I him saw saw I him man u-ra didam. did am ash. π o (or π r s) s o` π ` π o The over-lined types π, o, stand for the clitic versions of the subject and object pronouns. Including clitic rule (1) in the lexicon of the pregroup grammar of Persian, we obtain the clitic form of the verb from its original type. The original Persian verb has the type: or π r s = (πo)r s , which is of the form pr q; after applying the clitic rule we obtain: s(πo)` = s(π o)` = so` π ` , i.e. the type of the verb with postverbal clitics. The clitic rule can be seen as a re-write rule and the derivation can be depicted as a one-liner as follows or π r s = (πo)r s ; s(πo)` = so` π ` To form these one-word sentences, one does not necessarily have pronouns for subject and object in the original sentence. They can as well be formed from sentences with nominal subjects and objects, for example the sentence I saw Nadia, in Persian “man Nadia-ra didam”, becomes “did-am-ash” and is typed exactly as above. Hassan Nadia saw saw he her Hassan Nadia-ra did. di d ash. π o (or π r s) → s (s o` π ` ) π o →s One can form a yes-no question from any of the sentences above, by adding the question form “aya” to the beginning of the sentence. Since in Persian the word order of the question form is the same as that of the original sentence, the clitic movement remains the same and obeys the same rule [Sadrzadeh 2008] Did Hassan Nadia see? Did see he her? aya Hassan Nadia-ra did? aya di d ash? qs` π o (or π r s) → q qs` (so` π ` ) π o → q 3.3 Clitic movement in French In French, the clitic clusters move in the opposite direction with respect to Persian. We need therefore the clitic rule (2). Using this rule we can derive the type of the clitic form of the verb from its original type. Consider a simple example, the sentence “Jean voit Marie.” (Jean sees Marie) and its clitic form “Jean la voit”. We type these as follows Jean voit Marie. Jean la voit. π (π r s o` ) o → s π o (or π r s) → s To derive the clitic type of the verb from its original type, we start with the original type of “voit” : (π r s o` ) take q = (π r s) and p` = o` , apply clitic rule (2) and obtain the type: (or π r s) . The following is an example with the locative object λ and its clitic pronoun λ . Jean va à Paris. Jean y va. r π (π r sλ` ) λ →s π λ (λ π r s) → s r Again the clitic rule (2) easily derives (λ π r s) from (π r sλ` ). Now consider the more complicated example “Jean donne une pomme à Marie” (Jean gives an apple to Marie); we type it as follows Jean donne une pomme à Marie. π (π r s w` o` ) o w While learning French at school, it’s difficulty to remember the order of the clitic pronouns in these sentences; clitic rule (2) offers a hint: according to it a verb of the type (π r s w` o` ) can also be of type wr or π r s, taking q = (π r s) and p = (ow)` . This type will result in the following grammatical sentence Jean la lui donne. π o w wr or π r s But it will not make the following incorrect order grammatical Jean lui la donne. π w o wr or π r s . 3.4 Clitic movement in Italian Sentences with one occurrence of a pre-verbal clitic can be obtained exactly like in French, as shown in the following examples corresponding to the French sentences given above: “Gianni vede Maria” and its clitic form “Gianni la vede” Gianni vede Maria. Gianni la vede. π (π r s o` ) o → s π o (or π r s) → s To derive the clitic type of the verb we start with the original type (π r so` ), take q = π r s and p` = o` , apply clitic rule (2) and obtain the type (or π r s). The same process is obtained with a locative argument λ and the corresponding clitic r pronoun λ, where the clitic rule derives (λ π r s) from (π r sλ` ). Gianni va a Roma. Gianni ci va. r π (π r s λ` ) λ →s π λ (λ π r s) → s When we consider the more complicated cases of a verb with two arguments like in “Gianni da un libro a Maria” (Gianni gives a book to Maria), or “Gianni mette un libro sul tavolo” (Gianni puts a book on the table), we find that clitics pronouns occur in the opposite order with respect to French: e.g. the verb “dare” (to give) has the clitic form “Gianni glie lo da” (Gianni to-her it gives). In Casadio and Lambek [2001] this problem was handled by introducing a second type for verbs with two complements (π r s o` w` ) and (π r s o` λ` ); assuming these verb types and applying clitic rule (2) we obtain the correct clitic verb forms to handle the cases of pre-verbal cliticization: (π r s o` w` ) = (π r s(wo)` ) ; ((wo)r π r s) = (or wr π r s) the same with λ in place of o. Gianni glie lo da. Gianni ce lo mette. r π w o (or wr π r s) → s π λ o (or λ π r s) → s The following diagram shows the general pattern of preverbal cliticization in Italian with a verb taking two arguments: I (nom) you (dat) it (acc) say io te lo dico π w o (or wr π r s) 4 Insights into Hungarian and Dutch word order In the previous section we have dealt with a special kind of movement: the clitic movement, limited to certain words moving from before to after the verb (or the other way around) and becoming clitics. In this section we show that similar cyclic rules can be used to reason about movement of words in general. This movement is more free: firstly all words, or relevant words strings, can move; secondly the movement is not restricted to the context surrounding the verb. 4.1 Word order in Dutch subordinate clauses In Dutch (like in German), the position of the finite verb in main clauses differs from that in subordinate clauses. The unmarked order of the former is SVO, while the latter exhibit an SOV pattern. Also concerning word order Dutch is similar to German in that the finite verb always occurs in second position in declarative main clauses (V2), while the verb appears in final position in subordinate clauses: a sentence like “hij kocht het boek” (he bought the book ) in subordinate clauses becomes “. . . hij het boek kocht” (he the book bought); with more arguments, “Jan geeft het boek aan Marie” (Jan gives the book to Marie) becomes “. . . Jan het boek aan Marie geeft” (Jan the book to Marie gives). In order to reason about these kinds of movement, we generalize our clitic rule (2), corresponding to the r ight cyclic axiom, to all words by removing the bar from the types and the word ‘original’ from the definition, obtaining the following rule allowing verb argoments to move up the string from right to left Move Rule (1): If qp` is the type of the verb, so is pr q. The rule allows us to correctly type the examples mentioned above hij kocht het boek omdat hij het boek kocht he bought the book because he the book bought π (π r s o` ) o →s ss` π o (or π r s) → s omdat Jan het boek aan Marie geeft because Jan the book to Marie gives π o w (wr or π r s) Consider now an example with a modal verb “Ann wil Marie kussen” (Ann wants to kiss Marie) and the corresponding embedded clause “dat Ann Marie wil Kussen” (that Ann wants to kiss Marie) Ann wil Marie kussen dat Ann Marie (wil kussen) Ann wants Marie kiss that Ann Marie (wants kiss) π (π r s i` ) o (or i) → s ss` π o (or π r s) → s By contraction we obtain the type of the string “wil kussen”: (π r s i` ) (i o` ) → (π r s o` ); then by applying move rule (1) we obtain the type (or π r s) expect- ing the object to occur before the verb string. The clause-final verb clusters in Dutch and German have been estensively studied in different linguistic theo- ries, see Steedman [1985], Haegeman and van Riemsdijk [1986], Moortgat [1997], Lambek [2000]: a common observation is that while German prefers nested de- pendencies, between verbs and their arguments, Dutch prefers crossed depen- dencies. Consider the following sentences where “geld”: NP2 and “Marie”: NP3 are arguments of “geven”: V2 , “Piet”: NP1 is an argument of the perception verb “zag”: V1 . In the second example, an embedded clause, the dependencies between the two verbs and their arguments are crossed. Jan zag Piet geld Marie geven Jan saw Piet money Marie give π (π r s i` o`1 ) o1 o2 w (wr or2 i) → s . . . Jan Piet Marie geld (zag geven) . . . Jan Piet Marie money (saw give) π o1 w o2 (or2 wr or1 π r s) → s In the first example, “Jan zag Piet geld Marie geven” (Jan saw Piet give money to Marie), the type (i w` o`2 ) of “geven” is converted by move rule (1) into (wr or2 i) where o1 = “Piet”, o2 = “geld”, w = “Marie”; for q = i and p` = (w` o`2 ) = (o2 w)` , we have (o2 w)` ; (o2 w)r = (wr or2 ). In the second example, first we apply move rule (1) to the type (π r s i` o`1 ) of “zag” and obtain (or1 π r s i` ), for p = o1 ; then we get the type of the verb string “zag geven” by contraction: (or1 π r s i` ) (i o`2 w` ) → (or1 π r s o`2 w` ); finally, applying again the cyclic rule, we obtain (or2 wr or1 π r s), for p` = (w o2 )` . A similar analysis applies to the sentence “Jan Piet Marie zag laten zwemmen” (Jan saw Piet make Marie swim). . . . Jan Piet Marie (zag laten zwemmen) . . . Jan Piet Marie (saw make swim) π o1 o2 (or2 or1 π r s) → s 4.2 Word order changes in Hungarian Examples of still more radical word order changes are offered by languages such as Hungarian4 , where the movement is caused by a change of focus in the sen- tence. Words move within the sentence to reflect or focus on a certain meaning. For instance the following Hungarian sentence, which has no focus in it, simply means “János took two books to Péternek yesterday”. 4 agglutinative János tegnap elvitt két könyvet Péternek. János yesterday took two books to Péternek. This can become as follows János tegnap két könyvet vitt el Péternek. János yesterday two books took to Péternek. π λ o (or λr π r sw` ) w which means “Only two books were taken by János to Péternek yesterday”. This is an example of a single move: két könyvet has moved from after the verb to before it. More sophisticated movements are also possible, for instance in the following sentence Péternek vitt el tegnap János két könyvet. To Péternek took yesterday János two books. w (wr so` π ` λ` ) λ π o which means “It was to Péternek and to no one else that the two books were taken”. This is an example of a multi move: not only Péternek has moved to the beginning of the sentence, but also first tegnap and then János have moved from before the verb to after it, and in so doing have changed their order with regard to each other. For more details on single and multi moves and a formalization of a notion of focus, we refer the reader to Sadrzadeh [2010]; here instead we review some examples. In order to reason about these kinds of movement, we generalize our previous cyclic rules in the following way Move Rule (2): If pr q is in the type of the verb, so is qp` . Move Rule (3): If qp` is in the type of the verb, so is pr q. Taking π to stand for the type of the subject, o for the first object, w for the second object, and λ for the adverb, we assign the following types to the constituents of our example sentence, which had no focus in it yet János tegnap elvitt két könyvet Péternek. π λ (λr π r s w` o` ) o w The focus can be on the subject or either of the objects. In each case, they will appear right before the verb after the movement. For the case of the subject, i.e. János the temporal adverb yesterday moves to after the verb, as follows János vitt el tegnap két könyvet Péternek. János took yesterday two books to Péternek. π (π r sw` o` λ` ) λ o w We use our new cyclic rules to derive the new type of the verb as follows: apply move rule (2) to the type of the verb (λr π r sw` o` ), by taking q to be (π r s w` o` ) and p to be λ. If the focus is on the first object, i.e. two books, then it moves before the verb and the sentence above and its typing change as follows János tegnap két könyvet vitt el Péternek. János yesterday two books took to Péternek. π λ o (or λr π r sw` ) w To derive the new verb type, we apply move rule (3) to the original type of the verb (λr π r sw` o` ), by taking q to be (λr π r sw` ), and p to be o. The focus can also be on the second object Péternek and the verb; for details see Sadrzadeh [2010]. As an example of multi move, consider our above sentence, typed as follows Péternek vitt el tegnap János két könyvet. To Péternek took yesterday János two books. w (wr s o` π ` λ` ) λ π o Here Péternek has moved to the beginning of the sentence, but also first tegnap and then János have moved from before the verb to after it, and in so doing have changed their order with regard to each other. The calculation for deriving the new type of the verb reflects the above complications and needs repetitive applications of the rules. It is as follows Start from the original type of the verb (λr π r sw` o` ) and, first Péternek moves to the front; to obtain this we apply rule (3) to the subtype (λr π r sw` ), take p to be w, and obtain (wr λr π r so` ). Then tegnap moves after the verb, for this we apply rule (2) to the subtype (λr π r so` ), take p to be λ, and obtain (wr π r so` λ` ). Finally János moves to after tegnap, for this we apply rule (2) to the subtype (π r so` ), take p to be π, and obtain (wr so` π ` λ` ). Free as they might seem, we need some restrictions to avoid certain over genera- tions, mainly caused by the presence of the word in. Formulation of these exceed the purpose of this paper and can be found in Sadrzadeh [2010]. In a nutshell, they will prevent formation of types such as (π r λ` sw` o` ) and (λr π r sor w` ). 5 Clitic Rules and Cyclic Pregroups Following Lambek [1999, 2001, 2008], we have formulated the clitic rules as metarules. At some risk of overgeneration, one is tempted to formulate these rules as axioms and add them to the pregroup calculus, or add their rule version to the sequent calculus of compact bilinear logic [Buszkowski 2001, 2002]. Note that the addition of our cyclic axioms (or cyclic rules) is not equivalent to the reintroduction of the structural rule of Commutativity into the pregroup calculus (a logic without structural rules like the Syntactic Calculus)5 . These axioms belong to the cyclic calculus studied by Abrusci [1991, 2002] and introduced in the following way ` Γ, ∆ ` Γ, ∆ (rr) (ll) ` ∆+2 , Γ ` ∆, Γ −2 Via the standard translation from the Syntactic Calculus to pregroups [Lam- bek 1999, Buszkowski 2001] (positive formulae as right adjoints and negative formulae as left adjoints), the axiomatic version of these rules becomes (1) qp ≤ pq ll (2) qp ≤ prr q We can refer to (1) and (2) as cyclic axioms, in particular to the first one as the left cyclic axiom and to the second one as the right cyclic axiom. We can then re-formulate our clitic metarules as clitic axioms Persian pr q ≤ qpl French-Italian qpl ≤ pr q where the latter is derivable from the former, and prove the following results: Proposition 1. The clitic axioms are derivable from the cyclic axioms. Proof. The axiom for French and Italian is derivable form the right cyclic axiom as follows, take p to be pl and observe that (pl )rr = pr , then one obtains qpl ≤ pr q. Since p ≤ p, and since adjoints are contravariant, we have pr ≤ pr , thus pr q ≤ pr q, and by transitivity of order we obtain qpl ≤ pr q. The axiom for Persian is derivable from the left cyclic axiom as follows: take q to be pr and p to be q. Now since (pr )ll = pl , we obtain pr q ≤ qpl , and since p ≤ p, by contravariance, pl ≤ pl , thus qpl ≤ qpl , and by transitivity of order pr q ≤ qpl . It is interesting that the rules for clitic movement correspond to logical rules of cyclicity. Accordingly, one may call French and Italian right cyclic languages and Persian a left cyclic language. The consequences of enriching a pregroup with these cyclic axioms (or rules) are however not so desirable. Proposition 2. A pregroup P with either of the cyclic axioms is a partially ordered group. Proof. Consider the left cyclic axiom; if one takes q = 1, we obtain pr ≤ pl for all p ∈ P , from which one obtains pll ≤ p. Here take p = wr for some w ∈ P and obtain wl ≤ wr . Now since we have pr ≤ pl for all p, we obtain wr = wl . A similar argument can be made for the right cyclic axiom. 5 An approach in this line is proposed by Francez and Kaminski [2007], where a free pregroup grammar is extended by a finite set of additional (commutative) inequa- tions between types, leading to a class of mildly context-sensitive languages, allowing the analysis of crossed dependencies and extractions. Although, as proven by Abrusci and Lambek, cyclic bilinear logic is a con- servative extension of bilinear logic (or non-commutative linear logic), this is not the case for cyclic compact bilinear logic and compact bilinear logic (the logical calculus of pregroups) [Lambek 2008, Barr 2004]. The relations among these system are however of real interest to be studied both from the logical and, particularly, from the linguistic point of view. We conclude observing that the present analysis is consistent with previous work on French [Bargelli and Lambek 2001] and Italian [Casadio and Lambek 2001], where iterated adjoints are used to type clitic pronouns. We can prove in fact that iterated adjoints show up in our work too, since as observed by Lambek, the pr used in the metarule for French and Italian is nothing but (pl )rr , and the pl used for Persian is nothing but (pr )ll . 6 Conclusions We have applied the calculus of pregroups to a selected set of sentences involving word order changes in different languages: Persian, French, Italian, Dutch and Hungarian. The cross-linguistic results we have obtained provide evidence in favour of the theoretical and computational advantages offered by the pregroup calculus extended with appropriate cyclic rules. These rules in turn represent a stimulating challenge for the development of logical grammars. We have in fact shown that those calculations, or computations, that in pregroups are dealt with logical types involving double adjoints (corresponding to Chomskian traces), can be performed, in the different languages, by means of appropriate cyclic operations. References 1. Abrusci, V. M.: Phase Semantics and Sequent Calculus for Pure Noncommutative Classical Linear Propositional Logic. J. Symbolic Logic 56(4), 1403–1451 (1991) 2. Abrusci, M.: Classical Conservative Extensions of Lambek Calculus. Studia Logica 71, 277–314 (2002). 3. Abrusci, V.M., Casadio C. eds: New Perspectives in Logic and Formal Linguistics. Proceedings of the 5th Roma Workshop. Rome, Bulzoni (2002) 4. Ajdukiewicz, K.: Die syntaktische Konnexitaat, Studia Philosophica, 1, 1-27 (1935). Eng. trans., Syntactic connexion. In Polish Logic, ed. S. McCall. Oxford, Clarendon Press (1967) 5. Bargelli, D., Lambek J.: An Algebraic Approach to French Sentence Structure. In Logical Aspects of Computational Linguistics, edited by P. de Groote, G. Morrill, and C. Retoré, 62–78. Berlin, Springer-Verlag (2001) 6. Barr, M.: *-Autonomous Categories Revisited, Journal of Pure and Applied Algebra, 111, 1–20 (1996) 7. Barr, M.: On Subgroups of The Lambek Pregroup. Theory and Application of Cat- egories 12(8), 262–269 (2004) 8. Buszkowski, W.: Lambek Grammars Based on Pregroups. In Logical Aspects of Computational Linguistics edited by P. de Groote, G. Morrill, and C. Retoré, 95– 109. Berlin, Springer-Verlag (2001) 9. Buszkowski, W.: Type Logics and Pregroups. Studia Logica 87(2–3), 145-169 (2007) 10. Buszkowski, W., Moroz, K.: Pregroup Grammars and Context-free Grammars. In Casadio and Lambek eds., 1–21 (2008) 11. Casadio, C.: Non-Commutative Linear Logic in Linguistics. Grammars 4(3), 167– 185 (2001) 12. Casadio, C.: Applying Pregroups to Italian Statements and Questions. Studia Log- ica 87, 253–268 (2007) 13. Casadio, C., Lambek, J.: An Algebraic Analysis of Clitic Pronouns in Italian. In Logical Aspects of Computational Linguistics edited by P. de Groote, G. Morrill, and C. Retoré, 110–124. Berlin, Springer-Verlag (2001) 14. Casadio, C., Lambek, J.: A Tale of Four Grammars. Studia Logica 71(2), 315–329 (2002) 15. Casadio, C., Lambek, J. (eds.): Recent Computational Algebraic Approaches to Morphology and Syntax. Milan, Polimetrica (2008) 16. Casadio, C., Sadrzadeh, M.: Clitic Movement in Pregroup Grammar: a Cross- linguistic Approach. Proceeding 8th International Tbilisi Symposium on Language, Logic and Computation, Springer (2011) 17. Chomsky, N.: Lectures on Government and Binding. Dordrecht, Foris (1981) 18. Chomsky, N.: Barriers. Cambridge, The MIT Press (1986) 19. Francez, N., Kaminski, M: Commutation-Augmented Pregroup Grammars and Mildly Context-Sensitive Languages. Studia Logica 87(2/3), 295-321 (2007) 20. Grishin, V. N. : On a generalization of the Ajdukiewicz-Lambek system. In Studies in Nonclassical Logics and Formal Systems, Moscow, Nauka 315-343 (1983). Eng. trans. by D. Cubric, edited by author. In Abrusci and Casadio (eds.) 9-27 (2001) 21. Haegeman, L., van Riemsdijk, H.: Verb Projection Raising, Scope, and the Typol- ogy of Rules Affecting Verbs. Linguistic Inquiry, 17 (3), 417–466 (1986) 22. Harris, Z. S.: Methods in Structural Linguistics. Chicago (1951) 23. Harris, Z. S.: A Cycling Cancellation-Automaton for Sentence Well-Formedness. International Computation Centre Bulletin 5, 69–94 (1966) 24. Harris, Z. S.: Mathematical Structures of Language, Interscience Tracts in Pure and Applied Mathematics, John Wiley & Sons., New York (1968) 25. Kiślak - Malinowska, A.: Pregroups as a tool for typing relative pronouns in Pol- ish, Proceedings of Categorial Grammars. An Efficient Tool for Natural Language Processing, Montpellier, 114-128 (2004) 26. Kiślak - Malinowska, A.: Polish Language in Terms of Pregroups. In: Casadio, C., Lambek, J. (eds.) Recent Computational Algebraic Approaches to Morphology and Syntax. Polimetrica, Milan, 145–172 (2008) 27. Klavans, J. L.: Some Problems in a Theory of Clitics. Bloomington, Indiana Lin- guistics Club (1982) 28. Kusalik, T.: Product Pregroups as an Alternative to Inflectors. In Recent Compu- tational Algebraic Approaches to Morphology and Syntax, edited by C. Casadio and J. Lambek, 173–190. Milan, Polimetrica (2008) 29. Lambek, J.: The Mathematics of Sentence Structure. American Mathematics Monthly 65, 154–169 (1958) 30. Lambek, J. : Deductive Systems and Categories I. Syntactic Calculus and Residu- ated Categories. Mathematical Systems Theory, 2(4), 287–318 (1968) 31. Lambek, J.: From Categorial Grammar to Bilinear Logic. In Doŝen, K., P. Schroeder-Heister, eds. Substructural Logics. Oxford, Oxford University Press, 207– 237 (1993) 32. Lambek, J.: Type Grammar Revisited. In Logical Aspects of Computational Lin- guistics, edited by A. Lecomte et al., 1–27. Springer LNAI 1582 (1999) 33. Lambek, J.: Type Grammar Meets German Word Order. Theoretical Linguistics 26, 19–30 (2000) 34. Lambek, J.: Type Grammars as Pregroups. Grammars 4(1), 21–39 (2001) 35. Lambek, J.: A computational Algebraic Approach to English Grammar. Syntax 7(2), 128–147 (2004) 36. Lambek, J.: From Word to Sentence: a Pregroup Analysis of the Object Pronoun Who(m). Journal of Logic, Language and Information 16, 303–323 (2007) 37. Lambek, J.: From Word to Sentence. A Computational Algebraic Approach to Grammar. Polimetrica, Monza (MI) (2008) 38. Monachesi, P.: A Grammar of Italian Clitics. ITK Dissertation Series, Tilburg (1995) 39. Morrill, G.: Categorial Grammar. Logical Syntax, Semantics, and Processing. Ox- ford University Press, Oxford (2010) 40. Moortgat, M.: Categorical Type Logics. In Handbook of Logic and Language, edited by J. van Benthem and A. ter Meulen, 93–177. Amsterdam: Elsevier (1997) 41. Moortgat, M.: Symmetric Categorial Grammar. J. Philos. Logic 38, 681–710 (2009) 42. Preller, A., Lambek, J.: Free Compact 2-categories. Mathematical Structures for Computer Sciences 17, 309–340 (2007) 43. Preller, A., Prince, V.: Pregroup Grammars with Linear Parsing of the French Verb Phrase. In Recent Computational Algebraic Approaches to Morphology and Syntax edited by C. Casadio and J. Lambek, 53-84. Milan, Polimetrica (2008) 44. Preller, A., Sadrzadeh, M.: Semantic Vector Space and Functional Models for Pre- group Grammars. Journal of Logic, Language and Information (2011) 45. Sadrzadeh, M.: Pregroup Analysis of Persian Sentences. In Casadio and Lambek eds., 121–143 (2008) 46. Sadrzadeh, M.: An Adventure into Hungarian Word Order with Cyclic Pregroups. In AMS-CRM proceedings of Makkai Fest. (2010) 47. Steedman, M.: Dependency and Cordination in the Grammar of Dutch and English. Language, 61 (3), 523–568 (1985) 48. Stabler, E. P.: Tupled Pregroup Grammars. In Recent Computational Algebraic Approaches to Morphology and Syntax edited by C. Casadio and J. Lambek, 23–52. Milan, Polimetrica (2008) 49. Yetter, D. N.: Quantales and (non-Commutative) Linear Logic. Journal of Symbolic Logic, 55 (1990) 50. Wanner, D.: The Development of Romance Clitic Pronouns. From Latin to Old Romance. Amsterdam, Mouton de Gruyter (1987) 51. Zwicky, A. M., Pullum, G. K.: Cliticization vs. Inflection: English n’t. Language 59(3), 502-513 (1983)