Skip Navigation


Logic Journal of IGPL Advance Access originally published online on September 30, 2006
Logic Journal of IGPL 2006 14(5):659-708; doi:10.1093/jigpal/jzl005
This Article
Right arrow Full Text
Right arrow Full Text (PDF)
Right arrow All Versions of this Article:
14/5/659    most recent
jzl005v1
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Veksler, T.
Right arrow Articles by Francez, N.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2006. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

A Lambek Automaton

Tatyana Veksler

Computer Science department, Technion, Haifa. E-mail: tatyana{at}il.ibm.com

Nissim Francez

Computer Science department, Technion, Haifa. E-mail: francez{at}cs.technion.ac.il


  Abstract

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.

Key Words: Lambek-Automaton • Lambek-calculus • formal languages • type-logical grammar


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.