Automata in semigroup theory, group theory and analysis

有限状态自动机是理论计算机科学中的一个基本计算模型。 它们既被用作识别常规语言的机器，又被用作将输入字符串转换为输出字符串的机器。它们在计算语言的编译器中也起着关键作用。 此外，自动机形成了更复杂的计算模型的基本构建块。 自动机理论在纯数学中也有许多应用。 应用可以发现在这样的不同领域的数学：群论，半群理论，符号动力学和全纯dynamics.I建议探讨自动机理论的几个方面。 第一个方面是克罗恩-罗兹理论，该理论涉及将自动机分解为最简单的部分。 Krohn-Rhodes复杂性测量在这样的分解中所需的组部分的数量，我正在寻找一种方法来计算这一点。其元素由自动机组成的组最近在自相似组理论及其与分形的关系中发挥了作用。 这项建议也建议在这方面做一些工作。 这样的群体也可能导致一种方法来产生新的扩展图，这在电信网络中有应用。关于形式语言的数学问题在自动机理论中起着重要作用，特别是在计算机科学应用中。 一个典型的问题是这样的：给定一类形式语言，并给定形式语言上的一个运算符，应用这个运算符产生的类仍然有可判定的成员吗？ 还有一些问题与语言的逻辑描述和正则语言的层次结构有关。

Finite state automata are a fundamental model of computation in theoretical computer science.  They are used both as machines to recognize regular languages, and as machines to transform input strings into output strings. They also play a key role in compilers of computing languages.  In addition, automata form a basic building block for more complicated models of computation.  Automata theory has also found many applications in pure mathematics.  Applications can be found in such diverse areas of mathematics as: group theory, semigroup theory, symbolic dynamics and holomorphic dynamics.I propose to explore several aspects of the theory of automata.  The first aspect is Krohn-Rhodes theory, which concerns decomposing automata into their simplest possible parts.  Krohn-Rhodes complexity measures the number of group parts needed in such a decomposition and I am looking for a way to compute this.Groups whose elements consist of automata have recently played a role in the theory of self-similar groups and their relationship with fractals.  This proposal also suggests doing some work in this direction.  Such groups may also lead to a way to generate new expander graphs, which have applications in telecommunication networks.Algorithmic problems concerning formal languages plays a major role in automata theory, especially in computer science applications.   A typical question is of the sort:  given a class of formal languages and given an operator on formal languages, does the class resulting from applying this operator still have decidable membership?  There are also questions related to logical description of languages and hierarchies of regular languages.