Lambek calculus proofs and tree automata
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
Original language
EnglishPages from-to (Number of pages)
Pages 251-265 (15 pages)Publication milestones
- Published - 2001
Publication status
Publisher
Springer VerlagPublication 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
ISBN (Print)
354042251X, 9783540422518Publication IDs
- Scopus: 84942933442
Host publication title
Logical Aspects of Computational Linguistics - 3rd International Conference, LACL 1998, Selected PapersHost publication editors
- Michael Moortgat
