The semiring of partial transformations: an algebraic and algorithmic approach to modularity

This project will aim to design algorithms to efficiently solve equations in the semiring of partial transformations. This is a theoretical project in an area that combines graph theory, algebra, and algorithms.

Many large systems, both abstract and in real life, are modular, i.e. they are built by combining smaller modules that do small tasks. Some examples include transition systems, Cellular automata, systolic arrays, Petri nets, and Boolean networks. Our main goal is to understand the functionality of a large system by decomposing its smaller components. 

The semiring of transformations was first proposed in 2018 by researchers in Cellular Automata as a simple mathematical model for deterministic systems [1]. The objects of the semiring are finite transformations (functions from a finite set to itself) up to topological equivalence. Those objects are equipped with two operations: the sum corresponds to two systems having disjoint dynamics, while the product corresponds to the parallel composition of the two dynamics. Recently, this has been naturally generalised to partial transformations. Partial transformations are equivalent to functional digraphs, i.e. directed graphs where each vertex has at most one successor. In graph terms, the sum represents the disjoint union of digraphs, while the product is the direct product of digraphs.

The proposed model aims to be very broad by remaining simple: the modelled system has a finite number of possible states, for which we do not know the semantics, and is represented by a deterministic evolution. The two operations represent different ways of combining those systems. While (full) transformations assume that every state has a defined successor, some states may lead to undefined characteristics, or crashing the whole system entirely; such states without successors are encapsulated in a partial transformation instead. 

Decomposing a large system C then amounts to solving polynomial equations, e.g. if X^2 + YZ + Z^3 = C, how can we recover the components X, Y, Z from C? Previous work has focused on the division (solve AX = C), factorisation (solve XY = C), and root (solve X^k = C) problems (see [2, 3] and references therein). Interestingly, for those problems, the “algebraic” approach (that determines the uniqueness of a solution) and the “algorithmic” approach (that constructs the solution(s)) go hand in hand, as both unveil some interesting structural properties of the semiring.

As such, the project aims at using the algebraic and algorithmic approaches efficiently to design general algorithms to solve equations in the semiring of partial transformations. 

ENVIRONMENT

The supervisor, Dr Maximilien Gadouleau, is an Associate Professor of Computer Science. His research interests are centred around Boolean networks, a growing area of Discrete Mathematics and Theoretical Computer Science. More importantly, his work is recognised for its breadth, including cryptography, coding theory, Cellular automata, combinatorics, graphs and digraphs, or Linear Programming. This approach has led him to significantly expand the scope of research in Boolean networks, bringing in connections with the fields listed above. In turn, this has made him one of the internationally leading figures in the area. 

Dr Gadouleau is a member of the Algorithms and Complexity in Durham research group, one of the leading groups in Theoretical Computer Science in the UK. Durham University is world-class, constantly ranked as one of the best universities in the UK.

REFERENCES

[1] Alberto Dennunzio, Valentina Dorigatti, Enrico Formenti, Luca Manzoni, and Antonio E. Porreca. Polynomial equations over finite, discrete-time dynamical systems, 2018.

[2] Sara Riva. Factorisation of discrete dynamical systems. PhD thesis, 2022.

[3] Émile Naquin and Maximilien Gadouleau. Factorisation in the semiring of finite dynamical systems, 2023.