Automata, Languages, Decidability in Algebra
Lead Research Organisation:
University of St Andrews
Department Name: Mathematics and Statistics
Abstract
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.
Organisations
People |
ORCID iD |
Nik Ruskuc (Principal Investigator) | |
Martyn Quick (Co-Investigator) |
Publications
Abu-Ghazalh N
(2014)
A classification of disjoint unions of two or three copies of the free monogenic semigroup
in Semigroup Forum
Albert M
(2014)
Inflations of geometric grid classes of permutations
in Israel Journal of Mathematics
Belk J
(2016)
Some undecidability results for asynchronous transducers and the Brin-Thompson group $2V$
in Transactions of the American Mathematical Society
Belk James
(2014)
Some undecidability results for asynchronous transducers and the Brin-Thompson group 2V
in arXiv e-prints
Bleak C
(2017)
The infinite simple group $V$ of Richard J. Thompson: presentations by permutations
in Groups, Geometry, and Dynamics
Bleak Collin
(2015)
Determining solubility for finitely generated groups of PL homeomorphisms
in arXiv e-prints
Bourne T
(2016)
On the star-height of subword counting languages and their relationship to Rees zero-matrix semigroups
in Theoretical Computer Science
Brough T
(2014)
Automaton semigroup constructions
in Semigroup Forum
CAIN A
(2012)
UNARY FA-PRESENTABLE SEMIGROUPS
in International Journal of Algebra and Computation
Cain A
(2014)
Subalgebras of FA-presentable algebras
in Algebra universalis
Description | This project resulted in a wide-ranging investigation into the ways in which automata can be used in the description of algebraic structures. A number of diverse teams developed, including the CoI Quick, two postdocs employed on the grant Bleak and Brough, and the originally named RA Cain. Areas in which progress has been made include: Thompson-like groups and semigroups (Bleak and Quick), automatic word problems (Brough, Ruskuc), FA presentable semigroups and other structures (Cain, Ruskuc, and various PhD students of Ruskuc), idempotent generated semigroups (Ruskuc and collaborators). In each area major progress has been achieved, leading to intensive further investigation following the conclusion of the project. |
Exploitation Route | In each area major progress has been achieved, leading to intensive further investigation following the conclusion of the project. |
Sectors | Digital/Communication/Information Technologies (including Software) |