Home | Papers | Teaching | CV | Leisure |

|Esperanto| |English|

- Equivalent Types in Lambek Calculus and Linear Logic
- Lambek grammars are context free
- The conjoinability relation in Lambek calculus and linear logic
- Models for the Lambek calculus
- Product-free Lambek calculus and context-free grammars
- Free monoid completeness of the Lambek calculus allowing empty premises
- Lambek Calculus and Formal Grammars
- Lambek calculus is NP-complete

See also papers in Russian (with English abstracts).

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

## Papers in English(preliminary versions) |

## Equivalent Types in Lambek Calculus and Linear Logic
## Abstract In 1958 J. Lambek introduced a calculus L of syntactic
types and defined an equivalence relation on types: "x~y
means that there exists a sequence x=x |
| |||

## Lambek grammars are context free
## AbstractIn this paper the Chomsky Conjecture is proved: all languages recognized by the Lambek calculus are context free. |
| |||

## The conjoinability relation in Lambek calculus and linear logic
## Abstract In 1958 J. Lambek introduced a calculus L of syntactic
types and defined an equivalence relation on types: "x~y
means that there exists a sequence x=x This paper gives an effective characterization of this equivalence for the Lambek calculi L and LP, and for the multiplicative fragments of Girard's and Yetter's linear logics. Moreover, for the non-directed Lambek calculus LP and the multiplicative fragment of Girard's linear logic, we present linear time algorithms deciding whether two types are equal, and finding a join for them if they are. |
| |||

## Models for the Lambek calculus
## AbstractWe prove that the Lambek calculus is complete w.r.t. L-models, i.e., free semigroup models. We also prove the completeness w.r.t. relativized relational models over the natural linear order of integers. |
| |||

## Product-free Lambek calculus and context-free grammars
## AbstractIn this paper we prove the Chomsky Conjecture (all languages recognized by the Lambek calculus are context-free) for both the full Lambek calculus and its product-free fragment. For the latter case we present a construction of context-free grammars involving only product-free types. |
| |||

## Free monoid completeness of the Lambek calculus allowing empty premises
## AbstractWe prove that the Lambek syntactic calculus allowing empty premises is complete with respect to the class of all free monoid models (i. e., the class of all string models, allowing the empty string). |
| |||

## Lambek Calculus and Formal Grammars
## AbstractWe prove context-freeness of languages generated by categorial grammars based on any of the following calculi: the Lambek calculus, the Lambek calculus allowing empty premises, the Lambek calculus with the unit, the multiplicative fragment of cyclic linear logic. We prove that all elementary fragments of the Lambek calculus have the Craig interpolation property. We prove that the conjoinability relation (on syntactic types) is decidable and that it is complete with respect to the free group interpretation. This is the English translation of the Ph.D. thesis of Mati Pentus. |
| |||

## Lambek calculus is NP-complete
## AbstractWe prove that for both the Lambek calculus L and the Lambek calculus allowing empty premises L* the derivability problem is NP-complete. It follows that also for the multiplicative fragments of cyclic linear logic and noncommutative linear logic the derivability problem is NP-complete. |
| |||

Home | Papers | Teaching | CV | Leisure |

Location:
http://lpcs.math.msu.su/~pentus/abstr.htmLast modified 14.11.2006. Mati Pentus Tel/fax: + 7 - 495 - 939 30 31 |