SEMINAR: Groups and Combinatorics Seminar 16:00 Fri 02/03/2018: Tim Boykett in Weatherburn LT

Speaker: Tim Boykett (Johannes Kepler University, Linz, Austria)

Title: Algebraic Models of Computation: Nearrings of Group Automata

Time and place: 16:00 Friday 2/3/2018 in Weatherburn LT

Abstract: Input-Output Automata are a simple but powerful model of processes. Inputs arrive and, depending upon the current state, the automaton outputs a symbol and moves to a new state. In the case that the input and output alphabets are identical, we can compose them by connecting the input of one automaton to the output of another. By equipping the alphabet with a group operation, we can compose automata in parallel, feeding each the same input and summing their output using the group operation. We obtain a collection of synchronous state automata, equivalently a set of mappings on infinite sequences.

The algebraic tool that best allows us to model, manipulate and analyse collections of such automata are nearrings, the nonlinear analogue of rings. A (right) nearring (N,+,*) is a (not necessarily abelian) group (N,+), a semigroup (N,*) with one distributive law (a+b)*c= a*c+b*c. Standard examples are the set of all mappings of a group to itself under pointwise addition and functional composition, the closed subalgebras of this, or the class of nearfields as used in describing certain projective planes including the Hall Plane. In this talk we will outline this construction in more detail, demonstrate the complexity of the nearring of automata and introduce radicals as simplifying tools. In particular we will show that the amnesiac mapping and the set of delay automata help bound the Jacobson 2-radical, defining it in certain cases. In these cases we can write down the 2-semisimple automata nearrings explicitly. Input-Output Automata are a simple but powerful model of mechanical, electronic and other processes. In the case that the input and output alphabets are identical, we can compose them by connecting the input of one automaton to the output of another. By equipping the alphabet with a group operation, we can compose automata in parallel, feeding each the same input and summing their output using the group operation.

This work is supported by the grant P29931 and SFB Project F5004 of the Austrian Science Foundation, FWF.