Semigroups and automata

Overview

Research in Semigroups and Automata at the University of Hertfordshire Algorithms Research Group focuses on computational methods for Krohn-Rhodes Theory and Automata Networks. Automata correspond to discrete-time dynamical systems (depending on multiple inputs and producing multiple outputs) with finite phase spaces. They may be synchronous or asynchronous, localized or distributed.

All such systems can be decomposed and synthesized hierarchically from irreducible (prime and unit components) using the methods of Algebraic Automata Theory. To each such discrete dynamical system is associated a canonical algebraic structure called a semigroup. An axiomatic and rigorous Complexity Theory arises by considering shortest possible such decompositions. The prime components are finite simple groups which have been well-studied in finite group theory.

At the University of Hertfordshire we have developed the world's first computational implementations of the Krohn-Rhodes decompositions and synthesis for finite automata, finite transformation semigroups, and for finite permutation groups (Frobenius-Lagrange coordinates), by developing computationally feasible mathematical proofs and corresponding constructive computer implementations.

Applications

This work has applications in Artificial Intelligence, Systems Biology, Game Theory, and Finite Phase-Space Dynamical Systems Theory, and Interaction Computing.

Artificial Intelligence. Hierarchical coordinate systems on finitary dynamical systems correspond to models for understanding and manipulating phenomena. These are analogous to the decimal expansion for real numbers. They provide a mathematical means to zoom-in and zoom-out in detail in coordinate form, and transformations of the systems have a cascade, feed-forward form. In permutation puzzles, such as Rubik's cube, they provide automatically derived strategies for solving.

Algebraic Biology. Petri-nets, Multi-Valued Automata (including Boolean Networks) and Reaction Graphs are useful means of modelling phenomena in Systems Biology, biochemical networks, and genetic regulatory control. Applying our computer algebraic methods to such models leads to global hierarchical methods for understanding and manipulating them in a coordinated form and is useful in detecting natural subsystems (characterized as 'pools of local reversibility').

Category-, automata-, and information-theoretic methods are also applied in relation to work on Interaction Computing; asynchronous emulation of arbitrary synchronous computation; automatic customized user-interface synthesis and analysis based on affordance graphs; novel techniques for data visualization and manipulation, and interactive systems analysis (with applications to HCI, HRI, and human-human interaction psychology), as well as perception-action loops, the evolution of complexity in artificial life and in biology.