computer science


Computer Science Theory

Welcome | People | Research | Publications | Seminars | Talks | Courses | Events | Useful Links

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 toanother even if the vehicles might (by taking different routes) changetheir order in the queue. Another example is a stack in a computerprogram; data items move onto the stack and leave it, often in a differentorder. 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 sucha 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 inpermutations. 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.