Cyclic Pregroups and Natural Language: a Computational Algebraic Analysis

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 di use presence of cyclic patterns exhibited in di erent 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 introducing appropriate cyclic rules that will allow the grammar to formally analyze and compute word order and movement phenomena in di erent 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 computing linguistic information.

-

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 di erent 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 representative 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 connections of the present analysis to cyclic linear logic [Yetter 1990, Abrusci 1991, 2002]. 2 2.1

Cyclic rules for the Calculus of Pregroups

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 elds 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 fG, . , 1, `, r, !g 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 ! ara 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 b` ! a` , br ! ar , a`` ! b`` , arr ! brr . 1 A partial order ` ' (here denoted by the arrow `!') is a binary relation which is re exive: 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 arr ! 1 ! arr 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 (in nitive verb), s (sentence), we obtain simple types such as n`, nr, `, r, o`, or, : : : , and compound types such as ( rs 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 rst person singular, and the subscript 2 in s2 indicates the past tense2

I saw him.

1 ( 1rs2 o`) o We say that a sentence is grammatical i 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 su cient 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]. Di erent kinds of cyclic transformations were explored by Chomsky [e.g. 1981] to compute constituents movement in long distance dependencies. As argued by Lambek [2008], the analysis of modern European languages requires that word symbols (logical types) take double superscripts, like in Harris [1968], or the double adjoints de ned in pregroup grammar, wherever Chomsky'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 analyse 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 reintroduction 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] ` 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

The monoid multiplication of the pregroup is non-commutative, but if we add to the pregroup calculus the cyclic rules de ned above as metarules, then we obtain a limited form of commutativity, for p; q 2 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 dictionary, 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 e ect 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 languages 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 (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. By doing so, the word order changes from SOV to VSO. A similar phenomenon happens in Romance languages 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 di erent approach o ering a uni ed 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 prq 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 prq. The over-lined types p`, pr are introducend as a notational convenience to distinguish 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 2 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 man u-ra didam.

o (or rs) saw I him did am ash. 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 rs = ( o)rs , which is of the form prq; 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 rs = ( o)rs ; 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

Hassan Nadia-ra o saw did. (or rs) ! s saw di (s o` `) he d her ash. 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

aya Hassan Nadia-ra qs` o see? did? (or rs) ! q Did see aya di qs` (so` `) he d her? ash? 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 ( rs o`)

Marie.

o ! s

Jean la voit.

o (or rs) ! s To derive the clitic type of the verb from its original type, we start with the original type of \voit" : ( rs o`) take q = ( rs) and p` = o` , apply clitic rule ( 2 ) and obtain the type: (or rs) . The following is an example with the locative object and its clitic pronoun .

Jean Again the clitic rule ( 2 ) easily derives ( r rs) from ( rs `). Now consider the more complicated example \Jean donne une pomme a Marie" (Jean gives an apple to Marie); we type it as follows

donne ( rs w`o`) une pomme a Marie.

o w While learning French at school, it's di culty to remember the order of the clitic pronouns in these sentences; clitic rule ( 2 ) o ers a hint: according to it a verb of the type ( rs w`o`) can also be of type wror rs, taking q = ( rs) and p = (ow)`. This type will result in the following grammatical sentence But it will not make the following incorrect order grammatical

Jean la lui donne.

o w wror rs

Jean lui la donne.

w o wror rs . 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

( rs o`)

Maria.

o ! s

Gianni la vede.

o (or rs) ! s To derive the clitic type of the verb we start with the original type ( rso`), take q = rs and p` = o`, apply clitic rule ( 2 ) and obtain the type (or rs). The same process is obtained with a locative argument and the corresponding clitic pronoun , where the clitic rule derives ( r rs) from ( rs `).

Gianni va

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 nd 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 ( rs o`w`) and ( rs 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:

( rs o`w`) = ( rs(wo)`) ; ((wo)r r s) = (or wr r s) the same with

in place of o.

Gianni glie lo da.

w o (orwr rs) ! s

Gianni ce lo mette.

o (or r rs) ! 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) io te lo w o say dico (orwr rs) 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: rstly 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 nite verb in main clauses di ers 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 nite verb always occurs in second position in declarative main clauses (V2), while the verb appears in nal 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 de nition, 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 prq.

The rule allows us to correctly type the examples mentioned above hij kocht het boek he bought the book ( rs o`) o ! s omdat hij het boek kocht because he the book bought ss` o (or rs) ! s omdat Jan het boek aan Marie because Jan the book to Marie o w By contraction we obtain the type of the string \wil kussen": ( rs i`) (i o`) ! ( rs o`); then by applying move rule ( 1 ) we obtain the type (or rs) expecting the object to occur before the verb string. The clause- nal verb clusters in Dutch and German have been estensively studied in di erent linguistic theories, see Steedman [1985], Haegeman and van Riemsdijk [1986], Moortgat [1997], Lambek [2000]: a common observation is that while German prefers nested dependencies, between verbs and their arguments, Dutch prefers crossed dependencies. 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

( rs i` o`1) o1 o2 w (wror2 i) ! s : : : Jan Piet Marie : : : Jan Piet Marie o1 w geld (zag geven) money (saw give) o2 (or2 wr or1 rs) ! s In the rst example, \Jan zag Piet geld Marie geven" (Jan saw Piet give money to Marie), the type (i w`o` ) of \geven" is converted by move rule ( 1 ) into (wror2 i) 2 where o1 = \Piet", o2 = \geld", w = \Marie"; for q = i and p` = (w`o` ) = (o2w)`, 2 we have (o2w)` ; (o2w)r = (wror2). In the second example, rst we apply move rule ( 1 ) to the type ( rs i` o` ) of \zag" and obtain (or1 rs i`), for p = o1; then 1 we get the type of the verb string \zag geven" by contraction: (or1 rs i`) (i o`2w`) ! (or1 rs o`2w`); nally, applying again the cyclic rule, we obtain (or2 wr or1 rs), 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 o ered by languages such as Hungarian4 , where the movement is caused by a change of focus in the sentence. Words move within the sentence to re ect or focus on a certain meaning. For instance the following Hungarian sentence, which has no focus in it, simply means \Janos took two books to Peternek yesterday". 4 agglutinative

Janos tegnap elvitt ket konyvet Peternek. Janos yesterday took two books to Peternek.

This can become as follows

which means \Only two books were taken by Janos to Peternek yesterday". This is an example of a single move: ket konyvet has moved from after the verb to before it. More sophisticated movements are also possible, for instance in the following sentence which means \It was to Peternek and to no one else that the two books were taken". This is an example of a multi move: not only Peternek has moved to the beginning of the sentence, but also rst tegnap and then Janos 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 prq is in the type of the verb, so is qp`.

Move Rule ( 3 ): If qp` is in the type of the verb, so is prq.

Taking to stand for the type of the subject, o for the rst 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

Janos tegnap elvitt

( r rs w`o`) ket konyvet Peternek.

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. Janos the temporal adverb yesterday moves to after the verb, as follows Janos vitt el tegnap ket konyvet Peternek.

Janos took yesterday two books to Peternek.

( rsw`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 rsw`o`), by taking q to be ( rs w`o`) and p to be . If the focus is on the rst object, i.e. two books, then it moves before the verb and the sentence above and its typing change as follows To derive the new verb type, we apply move rule ( 3 ) to the original type of the verb ( r rsw`o`), by taking q to be ( r rsw`), and p to be o. The focus can also be on the second object Peternek and the verb; for details see Sadrzadeh [2010]. As an example of multi move, consider our above sentence, typed as follows Here Peternek has moved to the beginning of the sentence, but also rst tegnap and then Janos 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 re ects the above complications and needs repetitive applications of the rules. It is as follows

Start from the original type of the verb ( r rsw`o`) and, rst Peternek moves to the front; to obtain this we apply rule ( 3 ) to the subtype ( r rsw`), take p to be w, and obtain (wr r rso`). Then tegnap moves after the verb, for this we apply rule ( 2 ) to the subtype ( r rso`), take p to be , and obtain (wr rso` `). Finally Janos moves to after tegnap, for this we apply rule ( 2 ) to the subtype ( rso`), take p to be , and obtain (wrso` ` `).

Free as they might seem, we need some restrictions to avoid certain over generations, 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 rsorw`). 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 ` Via the standard translation from the Syntactic Calculus to pregroups [Lambek 1999, Buszkowski 2001] (positive formulae as right adjoints and negative formulae as left adjoints), the axiomatic version of these rules becomes We can refer to ( 1 ) and ( 2 ) as cyclic axioms, in particular to the rst 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

prq qpl

French-Italian qpl prq 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 prq. Since p p, and since adjoints are contravariant, we have pr pr, thus prq prq, and by transitivity of order we obtain qpl prq. 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 prq qpl, and since p p, by contravariance, pl pl, thus qpl qpl, and by transitivity of order prq 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 2 P , from which one obtains pll p. Here take p = wr for some w 2 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 nite set of additional (commutative) inequations 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 conservative 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 di erent languages: Persian, French, Italian, Dutch and Hungarian. The cross-linguistic results we have obtained provide evidence in favour of the theoretical and computational advantages o ered 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 di erent 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. Retore , 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 Categories 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. Retore , 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 Logica 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. Retore , 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 Crosslinguistic 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 Typology of Rules A ecting 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. Kislak - Malinowska , A.: Pregroups as a tool for typing relative pronouns in Polish , Proceedings of Categorial Grammars . An E cient Tool for Natural Language Processing , Montpellier, 114 - 128 ( 2004 )

26. Kislak - 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 Linguistics Club ( 1982 )

28. Kusalik , T. : Product Pregroups as an Alternative to In ectors . In Recent Computational 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 Residuated Categories. Mathematical Systems Theory , 2 ( 4 ), 287 { 318 ( 1968 )

31. Lambek , J.: From Categorial Grammar to Bilinear Logic . In Do^sen, 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 Linguistics , 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 . Oxford 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 Pregroup 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 . In ection: English n't. Language 59 ( 3 ), 502 - 513 ( 1983 )