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的这笔拨款，她将致力于在较少了解的结构类别的背景下回答这些指导性问题。例如，与某些流形相关的基本群与自动机有着密切的联系，而符号动力学和组合学中出现的一些序列可能被视为由自动机生成。自动结构社区开发的工具可能会导致对这些对象更好的结构理解。与此同时，明尼斯博士试图发展自动模型理论领域。当模型理论的标准结果被限制在可计算或多项式时间对象的框架内时，人们已经做了很多工作来理解模型理论的标准结果是如何变化的。初步工作显示了自动结构世界中有趣的类比，并暗示了取得丰硕成果的前景。随着现代世界对计算机化和网络化系统的日益依赖，计算可行性的理论基础获得了更直接的相关性。从20世纪50年代开始，图灵机--一种没有内存使用或计算时间限制的理想化计算机模型--导致了人们对任何算法都能解决或不能解决什么问题的惊人而基础性的洞察。NSF的这个项目专注于计算机的另一种模型--有限自动机，它更接近于在线计算和资源限制。Minnes博士将研究与有限自动机有关的问题，这些问题既与数理逻辑的传统主题有关，也与数学和计算机科学的其他领域的新交互有关。