Automata in semigroup theory, group theory and analysis

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