Automata, Computability and Complexity Theory Group

This is the home page of the Automata, Computability and Complexity Theory Group, part of the Algorithms Section in the Department of Computer Science at the University of Liverpool.

The question “What can be (efficiently) automated?” is one of the most inspiring philosophical and practical questions. Our group works on fundamental questions about what can be computed in principal (computability theory) and what amount of computational resources such as time and space are required to perform those computations (computational complexity theory). The study of abstract machines and automata plays essential role in theoretical analysis of computations and therefore is important integral part of this stream of research.

We have a wide range of expertise including such areas as analysis of algorithms, computational complexity, models of computations, mathematical logic, automata theory, automata and games, formal languages, probabilistic computation, computational geometry and topology, computational algebra, decision problems and reachability problems in infinite state systems. Also we are open to interdisciplinary research and new collaborations on algorithmic and complexity aspects for various computational problems.

The group is led by Dr Igor Potapov

About the Automata, Computability and Complexity Theory Group