权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Automata, Languages, Decidability in Algebra

自动机、语言、代数可判定性

基本信息

批准号：
EP/H011978/1
负责人：
Nik Ruskuc
金额：
$ 44.42万
依托单位：
University of St Andrews
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2010
资助国家：
英国
起止时间：
2010 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FH011978%2F1
关键词：
Automata Languages Decidability Algebra

项目摘要

The overarching aim of this project is to unite the presently fragmented field of `automatic descriptions of algebraic structures'. Several different authors have developed various concepts to describe infinite groups, monoids and other algebraic structures using automata. Each of these areas started at a different time and has developed at a different rate. We aim to draw together these different descriptions, place them in a common framework, study the connections and the contrasts between them, and thus develop and exploit new insights into decision problems.An algebraic structure is a set with operations defined by it. As such, they are a corner-stone of mathematics. Automata are the most basic mathematical model of computation. There are three main motives behind introducing automata into algebra: 1. the need to define infinite (algebraic) structures by finite means (automata); 2. the need to identify classes of algebraic structures amenable to computation and computability; 3. the desirability for utilising results and techniques from Theoretical Computer Science in Algebra.Groups and semigroups -- algebraic structures we will mostly be concerned with -- hold a distinguished place in the history of interaction between algebra and theoretical computer science, and U.K. has long been at the forefront of research activity in this area. In this project we propose to analyse different existing approaches to using automata in algebra in the light of the above motives. We expect that by such analysis we will obtain deeper insights into the nature, uses and limitations of each approach, and hopefully discover some new ways in which the theory of automata and languages can be employed in Algebra. In pursuing this overall goal, we expect to also achieve the following subsidiary ones: (1) setting the common foundations for different approaches, utilising the language of semigroup actions; (2) inaugurating new uses of automata in algebra, such as automaton monoids, or regular word problems for semigroups; (3) establishing new undecidability results for the standard descriptions, such as automatic structures for groups and semigroups; (4) discovery, and, if feasible, implementation, of new algorithms for dealing with different automatic descriptions.The project will involve 4 permanent researchers: two proposers, a named research assistant (Dr Alan Cain) and a Ph.D. student. It will also involve a string of research visits and collaborations with the leading exponents of different strands of research in automata and decidability in Algebra. We also plan to organise an early workshop which would bring these representatives together for forward looking discussions.

这个项目的首要目标是统一目前支离破碎的领域“自动描述的代数结构”。几个不同的作者已经开发了各种概念来描述无限群，monoid和其他代数结构使用自动机。这些领域中的每一个都在不同的时间开始，并以不同的速度发展。我们的目标是把这些不同的描述集合在一起，把它们放在一个共同的框架中，研究它们之间的联系和对比，从而发展和开发对决策问题的新见解。代数结构是一个由它定义的运算的集合。因此，它们是数学的基石。自动机是最基本的计算数学模型。在代数学中引入自动机有三个主要的动机：1。需要定义无限（代数）结构的有限手段（自动机）; 2。需要确定类别的代数结构服从计算和可计算性; 3.在代数中利用理论计算机科学的结果和技术的可取性。群和半群--我们将主要关注的代数结构--在代数和理论计算机科学之间的相互作用的历史上占有突出的地位。长期以来一直处于该领域研究活动的前沿。在这个项目中，我们建议分析不同的现有方法，使用自动机在代数的上述动机。我们希望通过这样的分析，我们将获得更深入的了解每种方法的性质，用途和局限性，并希望发现一些新的方法，自动机和语言的理论可以在代数。在追求这一总体目标的过程中，我们还期望实现以下附属目标：（1）利用半群作用的语言，为不同的方法建立共同的基础;（2）开创自动机在代数中的新用途，如自动机幺半群，或半群的正则字问题;（3）为群和半群的自动结构等标准描述建立新的不可判定性结果;（4）发现并在可行的情况下实现处理不同自动描述的新算法。该项目将涉及4名永久研究人员：两名提议者，一名指定的研究助理（Alan Cain博士）和一名博士。学生.它还将涉及一系列的研究访问和合作，与自动机和代数中可判定性研究的不同领域的领先指数。我们还计划尽早举办一个研讨会，让这些代表聚集在一起进行前瞻性的讨论。