Automata in Geometric Groups, Combinatorics, and 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.