Lambek Calculus:
Recognizing Power and Complexity

Makoto Kanazawa

Department of Cognitive and Information Sciences
Faculty of Letters
Chiba University
1--33 Yayoi-cho
263--8522 Japan


I survey known results and results that easily follow from known results about the recognizing power and complexity of various fragments of the Lambek calculus.

Bibtex Entry

I was a second-year graduate student in Linguistics at Stanford when Johan van Benthem was appointed by the Philosophy Department for the spring quarter of 1991. I understood that John Perry initially asked him to replace Jon Barwise, who had left the Stanford Philosophy Department for Indiana some time earlier, but Johan was not interested in leaving Amsterdam at all, hence the agreement on the part-time appointment. At that time, I was rather disappointed by the program offered by the Stanford Linguistics Department, where formal methods were not appreciated as much as I had hoped, so I was very much looking forward to taking Johan's course, secretly thanking Jon Barwise for making it possible. It was an exciting period for me; Johan's book Language in Action had just appeared, and his course had much to do with formal linguistics. My advisor Stanley Peters suggested I talk with Johan about possible topics for my first Qualifying Paper, which I had decided to write in the area of mathematical linguistics. Johan gave me a list of about 10 open problems; the recognizing power of the Lambek calculus with additional connectives was one. Working on it led to my first publication. (My contribution to this collection summarizes it and other related results.) As Maarten de Rijke once put it, `my life was never the same' after I met Johan.

This photo was taken in 1994 by my parents in the back of the Coffee House on Stanford campus after the four of us had chatted for about an hour. I think it was the Thursday before the Commencement. (The date on the photo reads `June 10, 1994' (Japan Standard Time), the Commencement was on Sunday the 12th.) Stanley had to be out of town during that weekend and couldn't see my parents, so Johan agreed to spend some time with us. We lost two rolls of films my parents used during their visit when we had one of our bags stolen, but this photo survived the incident. It captures one of the happiest moments in my life.