The Pentus theorem for Lambek calculus with simple nonlogical axioms
Studia Logica 81 (1):43 - 59 (2005)
| Abstract | The Lambek calculus introduced in Lambek [6] is a strengthening of the type reduction calculus of Ajdukiewicz [1]. We study Associative Lambek Calculus L in Gentzen style axiomatization enriched with a finite set Γ of nonlogical axioms, denoted by L(Γ).It is known that finite axiomatic extensions of Associative Lambek Calculus generate all recursively enumerable languages (see Buszkowski [2]). Then we confine nonlogical axioms to sequents of the form p → q, where p and q are atomic types. For calculus L(Γ) we prove interpolation lemma (modifying the Roorda proof for L [10]) and the binary reduction lemma (using the Pentus method [9] with modification from [3]). In consequence we obtain the weak equivalence of the Context-Free Grammars and grammars based on L(Γ). | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,672 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesHeinrich Wansing (2002). A Rule-Extension of the Non-Associative Lambek Calculus. Studia Logica 71 (3):443-451.
Wojciech Zielonka (2002). On Reduction Systems Equivalent to the Lambek Calculus with the Empty String. Studia Logica 71 (1):31-46.
Wojciech Zielonka (1989). A Simple and General Method of Solving the Finite Axiomatizability Problems for Lambek's Syntactic Calculi. Studia Logica 48 (1):35 - 39.
Wojciech Buszkowski (1996). The Finite Model Property for BCI and Related Systems. Studia Logica 57 (2-3):303 - 323.
Philippe De Groote & François Lamarche (2002). Classical Non-Associative Lambek Calculus. Studia Logica 71 (3):355 - 388.
Philippe de Groote & François Lamarche (2002). Classical Non-Associative Lambek Calculus. Studia Logica 71 (3):355-388.
Makoto Kanazawa (1992). The Lambek Calculus Enriched with Additional Connectives. Journal of Logic, Language and Information 1 (2).
Wojciech Buszkowski (1996). Extending Lambek Grammars to Basic Categorial Grammars. Journal of Logic, Language and Information 5 (3-4):279-295.
Maria Bulińska (2009). On the Complexity of Nonassociative Lambek Calculus with Unit. Studia Logica 93 (1).
Mati Pentus (1997). Product-Free Lambek Calculus and Context-Free Grammars. Journal of Symbolic Logic 62 (2):648-660.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads2 ( #232,316 of 549,037 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
