The IGPL/FoLLI Prize for the best Idea of the Year

Last year, the first IGPL/FoLLI Prize was announced for the best contribution on the interface of Logic, Language and Information, made by some innovative young researcher in our field. The aim is to acknowledge novel contributions of high quality which are likely to increase the interdisciplinary `connectivity' of our field. The first Prize Committee consisted of Johan van Benthem (past FoLLI chairman), Dov Gabbay (co-ordinator FoLLI Clearing House), and Hans Jürgen Ohlbach (editor Journal of the IGPL).

The Committee received 9 proposals, coming from Germany, Moldova, Russia, the UK and the USA. We would like to thank all those who submitted proposals and provided documentation on behalf of their nominees. The topics covered much of FoLLI's sphere of action: formal semantics and databases, logical theory of lambda calculus, mathematical linguistics, new methods for information retrieval, provability logics, physical methods in complexity theory, spatial reasoning, finite model theory, and display techniques in proof theory.

The Committee was quite impressed by several submissions. Even with the above criteria, it has been hard to `choose between goods'. In the end, we would like to award the FoLLI prize of US\$ 1000 for this year to

MATI PENTUS
Department of Mathematical Logic, Moscow University

for his ground-breaking work on the mathematical theory of categorial grammars. The key publication on which this judgment is based is his paper

"Language Completeness of the Lambek Calculus"
Proceedings of the 9th Annual IEEE Symposium
on Logic in Computer science,
July 4-7, 1994, Paris.

This work continues his ongoing research of recent years into the foundations of categorial grammars, which has introduced new powerful proof-theoretic methods (based, amongst others, on interpolation theorems for small language fragments) into the study of recognizing power as pursued in mathematical linguistics. The first fruit of this research was the solution of the long-standing `Chomsky Conjecture', open since the early sixties, stating that the languages recognizable by flexible categorial Lambek grammars are precisely the context-free ones. This laid to rest an old and vexed issue. The new result introduces high-powered combinatorial methods into categorial semantics, in order to prove that the well-known Lambek Calculus of categorial sequents is complete for its intended model, consisting of formal languages closed under the operations of concatenation product and its two direct slash inverses. The Committee was impressed by this demonstration how problems that originated in descriptive linguistics give rise to significant mathematical questions and novel theorems. It seems only fitting that this result was found in Moscow, a city with a long tradition in just this kind of interdisciplinary interest. In addition, we would like to mention three runners-up (one of them as a team):

Scott Kirkpatrick (Yorktown Heights) & Bart Selman (Murray Hill),
(statistical physics applied to complexity theory)
Brandon Bennett, Leeds
(new logics for spacial reasoning);
Heinrich Wansing, Leipzig
(modal extensions of display logic).

Both the FoLLI prize winner and the runners-up will be invited to contribute a paper on their themes to the Journal of the IGPL.

Nominations for next year's IGPL/FoLLI prize can be sent to the current FoLLI Chairman

            Wilfried Hodges
            University of London,
            School of Mathematical Sciences,
            Queen Mary and Westfield College,
            Mile End Road, GB - EI 4NS London,
            United Kingdom
	    email: W.A.Hodges@qmw.ac.uk

before May 1, 1996. These should be based on publications in 1995. We hope that we will see a fair reflection of the interests in our community, both theoretical and descriptive.