A Lambek Automaton

We define an automata-theoretic counterpart of (type-logical) grammars based on the (associative) Lambek-calculus L, a prominent formalism in computational linguistics. While the usual push-down automaton (PDA) has the same weak generative power as the L-based grammars (Pentus, 1995), there is no di...

Full description

Saved in:
Bibliographic Details
Published in:Logic journal of the IGPL 2006-10, Vol.14 (5), p.659-708
Main Authors: Veksler, Tatyana, Francez, Nissim
Format: Article
Language:English
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We define an automata-theoretic counterpart of (type-logical) grammars based on the (associative) Lambek-calculus L, a prominent formalism in computational linguistics. While the usual push-down automaton (PDA) has the same weak generative power as the L-based grammars (Pentus, 1995), there is no direct relationship between the computations of a PDA for some language L and the derivations of an L-based grammar for L. In the Lambek-automaton, on the other hand, there is a tight relation (1-1) between automaton computations and grammar derivations. The automaton exhibits a novel mode of operation, using hypothetical steps, directly inspired by the hypothetical reasoning embodied by L.
ISSN:1367-0751
1368-9894
DOI:10.1093/jigpal/jzl005