ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

1. Logic

1991 MS Classification: 03D15, 68Q05, 03D20, 03F20 Schwichtenberg, Helmut, Niggl, Karl-Heinz (Universität München), Bellantoni, Stephen J. (University of Toronto) Ramification, Modality and Linearity in Higher Type Recursion It is shown how to restrict Gödel’s system T of recursion in all higher types, so that the type level 1 section consists of exactly the polynomial-time computable functions. The characterization is obtained by a novel combination of ramified recursion and linearity of usage, which are made to coincide through modal operations.