Lambda Calculus, Type Theory, and Natural Language II

摘要

The articles in this special issue have been contributed by individuals involved in the second Workshop on Lambda Calculus, Type Theory, and Natural Language (LCTTNL) held at King's College London on 12 September 2005. The papers published here were written, peer reviewed and revised specifically for this issue of Logic and Computation. Both of the LCTTNL workshops provided an opportunity to exchange ideas between those working in different areas of lambda calculus, type theory and related topics, with a particular regard for their application to problems in natural language. Jan van Eijck's paper 'Sequentially Indexed Grammars' is concerned with defining a variant of indexed grammars which result from changing the stack handling mechanism. He presents a polynomial parsing algorithm that is an extension of the Earley parser for context free grammars. The claimed advantages of sequentially indexed grammars are that they have a simple rule format, and that they support a straightforward parsing algorithm, and that there is a natural correspondence between indices and traces. Roger Hindley's 'M. H. Newman's Typability Algorithm for Lambda-Calculus' provides a review and historical commentary on Newman's much neglected typability algorithm of 1943 for determining whether a lambda-calculus term is typable.