Details of Grant 

EPSRC Reference:	EP/H011978/1
Title:	Automata, Languages, Decidability in Algebra
Principal Investigator:	Ruskuc, Professor N
Other Investigators:	Quick, Dr MR
Researcher Co-Investigators:
Project Partners:
Department:	Mathematics and Statistics
Organisation:	University of St Andrews
Scheme:	Standard Research
Starts:	01 June 2010	Ends:	31 May 2014	Value (£):	348,646
EPSRC Research Topic Classifications:	Algebra & Geometry Logic & Combinatorics
EPSRC Industrial Sector Classifications:	No relevance to Underpinning Sectors
Related Grants:
Panel History:	Panel Date Panel Name Outcome 03 Sep 2009 Mathematics Prioritisation Panel Sept 3rd 2009 Announced
Summary on Grant Application Form
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.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk Summary Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:
Further Information:
Organisation Website:	http://www.st-and.ac.uk