Research Areas
Permuting machines
We are developing a theory of machines whose sole or main purpose is to move objects from one place to another. An example of such a permuting machine is the road layout of a city; the roads are a means of conducting a queue of traffic from one end of the city to another even if the vehicles might (by taking different routes) change their order in the queue. Another example is a stack in a computer program; data items move onto the stack and leave it, often in a different order. The key property of any permuting machine is its potential to reorder the objects which pass through it. We study such machines partly through the classical theory of automata, and investigate how they may be combined to produce new machines.
The long term applications of such a theory could include the design of efficient road topologies, and an understanding of how to build data types with a specified function.
Permutation patterns
The central theory that underpins our work on permuting machines is the theory of patterns in permutations. Therefore we are studying the foundations of this subject and that involves combinatorial and enumeration investigations.
Usually, the set of permutations generated by a permuting machine are characterised by a set of minimal impossible permutations. Machines where this minimal set is finite are rare in theory but abundant in practice. Deciding whether it is finite or infinite is often the first step to understanding the machine. Further understanding comes from knowing how many permutations there are of each length generated by the machine.