Automata in Geometric Groups, Combinatorics, and Logic

几何群、组合学和逻辑中的自动机

• 批准号: 1060351
• 负责人: Mia Minnes
• 金额: $ 8.24万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-07-01 至 2014-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1060351&HistoricalAwards=false
• 关键词: Automata; Geometric; Groups; Combinatorics; Logic

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.

该项目研究自动结构，特别是它们与几何群体理论，组合和逻辑相互作用时。有限状态的自动机是用于资源使用的固定有限范围的图灵机。 继续研究可以有效执行的数学部分的传统，自动结构领域探讨了可以由自动机表示的数学对象。 有关自动结构的问题可能会分为两个主题：开发结构特征和研究此类特征的算法后果。明尼斯博士在这两个领域都工作了，包括证明存在这种特征的正面和负面结果。通过这项NSF赠款，她将在不太了解的结构类别的背景下回答这些指导性问题。 例如，与某些歧管相关的基本组与自动机具有密切的连接，并且在符号动力学和组合物中产生的某些序列可以看作是由自动机视为生成的。 自动结构社区开发的工具可能会导致对这些对象的更好的结构理解。 同时，Minnes博士试图发展自动模型理论领域。 在理解模型理论的标准结果时，在限于可计算或多项式时间对象的框架时如何改变。 初步工作在自动结构世界中显示出有趣的类比，并提出了富有成果的希望。随着现代世界对计算机化和网络系统的依赖越来越多，计算可行性的理论基础已经获得了更直接的相关性。 从1950年代开始，Turing Machine是一个理想化的计算机模型，在内存使用或计算时间内无界限，导致了对任何算法可以或无法解决哪些问题的惊人和基础洞察力。 该NSF项目将重点放在计算机的不同模型上，即有限自动机，该模型更紧密地捕获在线计算和资源界限。 Minnes博士将研究将有限自动机与数学逻辑的传统主题以及与其他数学和计算机科学领域的新互动相关的问题。