Skip to search boxSkip to navigationSkip to main content

Lambek calculus proofs and tree automata

*Corresponding author for this work
Scholarship:
Chapter in Book/Report/Conference proceeding
Conference contribution
Research

Abstract

We investigate natural deduction proofs of the Lambek calculus from the point of view of tree automata. The main result is that the set of proofs of the Lambek calculus cannot be accepted by a finite tree automaton. The proof is extended to cover the proofs used by grammars based on the Lambek calculus, which typically use only a subset of the set of all proofs. While Lambek grammars can assign regular tree languages as structural descriptions, there exist Lambek grammars that assign non-regular structural descriptions, both when considering normal and non-normal proof trees. Combining the results of Pentus (1993) and Thatcher (1967), we can conclude that Lambek grammars, although generating only context-free languages, can extend the strong generative capacity of context-free grammars. Furthermore, we show that structural descriptions that disregard the use of introduction rules cannot be used for a compositional semantics following the Curry-Howard isomorphism.

Scholarship

Output type

Scholarship:
Chapter in Book/Report/Conference proceeding
Conference contribution
Research

Original language

English

Pages from-to (Number of pages)

Pages 251-265 (15 pages)

Publication milestones

  • Published - 2001

Publication status

Published - 2001

Publisher

Springer Verlag

Publication series

  • Publication series name: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    ISSN (Print): 0302-9743
    ISSN (Electronic): 1611-3349
    Volume: 2014
354042251X, 9783540422518

Publication IDs

  • Scopus: 84942933442

Host publication title

Logical Aspects of Computational Linguistics - 3rd International Conference, LACL 1998, Selected Papers

Host publication editors

  • Michael Moortgat