Automata in semigroup theory, group theory and analysis

半群论、群论和分析中的自动机

• 批准号: 262403-2007
• 负责人: Steinberg, Benjamin
• 金额: $ 1.24万
• 依托单位: Carleton University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2007
• 资助国家: 加拿大
• 起止时间: 2007-01-01 至 2008-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=362117
• 关键词: Automata; semigroup; theory; group; analysis

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.

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