Mathematical Sciences: Coding Methods in Algebra, Computability Theory and Model Theory

9500983 Nies Nies的研究涉及代数和逻辑领域，这些领域涉及在结构和结构类中使用一阶性质进行编码。他感兴趣的是证明由少量量词交替的句子组成的基本理论的片段的不可判断性，特别是对于有限群类理论、有限分配格理论和可列集格E的理论。对这些片段的兴趣源于它们包含了数学实践中通常出现的一阶句子。此外，他还将致力于从结构复杂性理论出发确定度结构理论的复杂性，并使用编码方法来研究可列图灵度结构D的模型论性质。E和D都是可计算性理论的中心结构。他还用编码的方法证明了各种度结构的非初等等价性，并从模型论的角度介绍了各类结构同构类型的信息量的一种度量。在另一个项目中，他计划分离作为确定性和非确定性线性时间的泛化的复杂性类别。编码的一般思想是用另一种对象表示一种对象，使用固定的解码密钥从第二种对象检索信息。在这个项目中，对象是代数、可计算性理论和模型理论中的某些结构。译码密钥由一阶逻辑中的公式集合组成，一阶逻辑是一种形式语言，可以被视为数学中自然语言的主要部分的形式化。结构A在结构B中的编码保证了B至少和A一样复杂。Nies将通过比较所有可能无限的结构的复杂性来研究它们的类的抽象顺序，并将类似的方法应用于有限结构的类，这是一个近年来因其与计算机科学的联系而一直是感兴趣的领域。在这个项目的第二部分，编码方法将应用于可计算性理论，这是数理逻辑中处理理想意义上的可计算性的部分。不可判定集可以根据它们的计算复杂性而变化。除了确定相关的一阶理论的复杂性之外，这里的目标是找出结构的对称性，并找到这些结构的简单表征。这些问题对于加深对计算的理解具有重要意义。***

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. ***