Automata, Languages, Decidability in 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.