9500983 Nies Nies' research concerns areas of algebra and logic that involve coding with first-order properties in structures and in classes of structures. He is interested in proving undecidability of fragments of elementary theories consisting of sentences with few quantifier alternations, in particular, for theories of classes of finite groups, the theory of finite distributive lattices, and for the theory of the lattice E of enumerable sets. Interest in such fragments arises from their containing the first-order sentences that usually occur in mathematical practice. Moreover, he will work toward determining the complexity of theories of degree structures from structural complexity theory and toward using coding methods to investigate model-theoretic properties of the structure D of enumerable Turing degrees. Both E and D are central structures in computability theory. Also using coding methods, he intends to prove nonelementary equivalence of various degree structures and intends to introduce a measure of the informational content of isomorphism types of structures belonging to various classes of structures from model theory. In a further project, he plans to separate complexity classes that are generalizations of deterministic and nondeterministic linear time. The general idea of coding is to represent objects of one kind by objects of another kind, with a fixed decoding key used to retrieve the information from an object of the second kind. In this project, the objects are certain structures from algebra, computability theory, and model theory. The decoding key consists of a collection of formulas in first-order logic, a formal language which can be viewed as a formalization of a major part of natural language within mathematics. A coding of a structure A in a structure B guarantees that B is at least as complex as A. Nies will investigate the abstract ordering on classes of all possibly infinite structures by comparing their co mplexity and will apply similar methods to classes of finite structures, a field which has been the focus of interest in recent years for its connections with computer science. In a second part of this project, coding methods will be applied to computability theory, that part of mathematical logic which deals with computability in the ideal sense. Undecidable sets can vary with respect to their computational complexity. The goals here, beyond determining the complexity of the associated first-order theory, are to find out the symmetries of the structures and to find a simple characterization of these structures. These questions are important for deepening the understanding of computation. ***
