Automata in semigroup theory, group theory and analysis

有限状态自动机是理论计算机科学中计算的基本模型。因此，它们既被用作识别规则语言的机器，也被用作将输入字符串转换为输出字符串的机器。自动机在计算语言的编译中也起着关键的作用。此外，自动机形成了更复杂的计算模型的基本构件。自动机理论在纯数学中也有许多应用。自动机理论的应用可以在诸如群论、半群理论、符号动力学和全纯动力学等不同的数学领域找到。我建议探索自动机理论的几个方面。第一个方面是克罗恩-罗兹理论，它涉及到将自动机分解成它们最简单的部分。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.