Research activity in 1994
Though this area of research overlaps with many others pursued in the
Department, from theoretical computer science to the applied fields of AI and
automated reasoning, mathematical logic is also cultivated for its own sake and
interest. Researchers in this area are mainly interested in questions of
foundations, both of computer science and of mathematics, and of complexity
theory.
One subfield of mathematical logic actively investigated is that of recursion
theory, especially the theory of recursively enumerable degrees; in this field
there is a standing collaboration of P. Odifreddi with researchers of Cornell
University and of the University of Chicago. P. Odifreddi and G. Lolli have
participated in a joint project (CNR-NSF) on inductive inference in the years
1993-94.
P. Odifreddi has written with A. Nerode a book on Lambda Calculus, to be
published by MIT in 1995; he has edited a book of essays on Kreisel's life and
work, to be published by Stanford CSLI. He has recently published papers on
Inductive Inference, Church's Thesis and the Logical Foundations of Geometry.
He is currently working on the second volume of his Classical Recursion
Theory.
G. Lolli has published a book on the history, foundations and axiomatics of set
theory; he has lately worked on the principle of induction and has been the
editor of the italian translation of Turing's works.
L. Egidi has been studying the computational complexity of the first order
theory of p-adic numbers, and is still working on the subject. She recently
started to investigate the possible applications of results of algebraic
geometry to complexity theory; in particular as tools for establishing lower
bounds of sub-polynomial complexity classes. In April '94 she took part as
invited speaker to the Workshop on Proof Theory, Complexity and
Metamathematics, organized in Vienna by the Kurt Goedel Society and the
Technische Universitaet Wien, giving a talk on Efficient Quantifier Elimination
in p-adic Fields.
N. Olivetti has completed his doctoral dissertation on goal directed rule
systems for a large class of modal and relevance logics, finding in all cases a
complete rule system.