Automata in Geometric Groups, Combinatorics, and Logic

这个项目研究自动结构，特别是当它们与几何群论、组合学和逻辑相互作用时。有限状态自动机是在资源使用上具有固定有限界限的图灵机。延续研究数学中可有效执行部分的传统，自动结构领域探索可由自动机表示的数学对象。关于自动结构的问题可以分为两个主题：发展结构特征和研究这种特征的算法结果。Minnes博士在这两个领域都做过研究，包括证明这些特征存在的正面和负面结果。通过这项NSF资助，她将致力于在不太了解的结构类别的背景下回答这些指导性问题。例如，与某些流形相关的基本群与自动机有着密切的联系，符号动力学和组合学中出现的一些序列可以看作是由自动机产生的。自动结构社区开发的工具可能会导致对这些对象的更好的结构理解。同时，Minnes博士寻求发展自动模型理论领域。在理解模型理论的标准结果如何在可计算或多项式时间对象的框架下发生变化方面已经做了很多工作。初步的工作显示了自动结构世界中有趣的类比，并表明有望取得丰硕成果。随着现代世界对计算机化和网络化系统的日益依赖，计算可行性的理论基础已经获得了更直接的相关性。从20世纪50年代开始，图灵机——一种对内存使用和计算时间没有限制的理想化计算机模型——让人们对什么问题可以用任何算法解决、什么问题不能用任何算法解决产生了惊人的基础性见解。这个NSF项目关注的是计算机的另一种模型，有限自动机，它更接近于在线计算和资源边界。Minnes博士将研究将有限自动机与数学逻辑的传统主题以及与其他数学和计算机科学领域的新互动联系起来的问题。

This project studies automatic structures, in particular as they interact with geometric group theory, combinatorics, and logic. Finite-state automata are Turing machines with fixed finite bounds on resource use. Continuing a tradition of studying that part of mathematics which can be performed effectively, the field of automatic structures explores mathematical objects which can be represented by automata. Questions about automatic structures may be grouped into two themes: developing structural characterizations and studying algorithmic consequences of such characterizations. Dr. Minnes has worked in both of these areas, including proving both positive and negative results about the existence of such characterizations. Through this NSF grant, she will work towards answering these guiding questions in the context of less understood classes of structures. For example, the fundamental groups associated with certain manifolds have intimate connections with automata and some sequences arising in symbolic dynamics and combinatorics may be seen as generated by automata. The tools developed by the automatic structures community may lead to a better structural understanding of these objects. In parallel, Dr. Minnes seeks to develop the area of automatic model theory. Much work has been done in understanding how the standard results of model theory change when restricted to the framework of computable or polynomial-time objects. Preliminary work shows interesting analogies in the automatic structures world and suggests the promise of fruitful results. With the increasing reliance of the modern world on computerized and networked systems, the theoretical underpinnings of computational feasibility have gained more immediate relevance. Starting in the 1950s, the Turing machine, an idealized model of a computer with no bounds on memory use or computation time, led to astonishing and foundational insight into what problems can or cannot be solved by any algorithm. This NSF project focusses on a different model for the computer, the finite automaton, which more closely captures online computation and resource bounds. Dr. Minnes will study questions which relate finite automata both to traditional topics of mathematical logic and to new interactions with other fields of mathematics and computer science.