Ruth Hoffmann

I am an Research Fellow at the University of St Andrews. My research interests lie in computational combinatorics and group theory, formal verification, permutation classes and graph theory.

I have been awared an Impact Accelaration Account to disseminate and progress the work which I've done with Susmit Sarkar on the verification of Cache Coherence Protocols against Memory Consistency Models. This work was part of the C3 EPSRC grant and in collaboration with the University of Edinburgh.

While working at the University of Glasgow, I had the opportunity to apply my knowledge of automata and group theory to model verification and applications thereof in the formalisation of autonomous behaviour of UAVs.

During my PhD, I have investigated permutation pattern classes in a language theoretic context.

In addition to my verification work, I have been collaborating with Ciaran McCreesh and various other researchers on algorithms for graph problems.


Sequential and Parallel Solution-Biased Search for Subgraph Algorithms, Blair Archibald, Fraser Dunlop, Ruth Hoffmann, Ciaran McCreesh, Patrick Prosser, James Trimble, CPAIOR, 2019.

Memory Consistency Models using Constraints, Ruth Hoffmann, Özgür Akgün, Susmit Sarkar, ModRef, 2018.

Observations from Parallelising Three Maximum Common (Connected) Subgraph Algorithms, Ruth Hoffmann, Ciaran McCreesh, Samba Ndojh Ndiaye, Patrick Prosser, Craig Reilly, Christine Solnon, James Trimble, CPAIOR, 2018.

Strategy Synthesis for Autonomous Agents Using PRISM, Alice Miller, Ruben Giaquinta, Ruth Hoffmann, Murray Ireland, Gethin Norman, NMF, 2018.

Verification of a lazy cache coherence protocol against a weak memory model, Christopher J. Banks, Marco Elver, Ruth Hoffmann, Susmit Sarkar, Paul Jackson, Vijay Nagarajan, FMCAD, 2017.

Between Subgraph Isomorphism and Maximum Common Subgraph, Ruth Hoffmann, Ciaran McCreesh, Craig Reilly, AAAI, 2017.

A Continuous-Time Model of an Autonomous Aerial Vehicle to Inform and Validate Formal Verification Methods, Murray L. Ireland, Ruth Hoffmann, Alice Miller, Gethin Norman, Sandor M. Veres, CoRR arXiv, 2016.

Towards the Automated Verification of Weibull Distributions for System Failure Rates, Yu Lu, Alice A. Miller, Ruth Hoffmann, Christopher W. Johnson, FMICS-AVoCS, 2016.

Autonomous Agent Behaviour Modelled in PRISM - A Case Study, Ruth Hoffmann, Murray Ireland, Alice Miller, Gethin Norman, Sandor M. Veres, SPIN, 2016.

On dots in boxes, or permutation pattern classes and regular languages, Ruth Hoffmann, PhD Thesis, University of St Andrews, 2015.

Regular languages of plus- and minus-(in)decomposable permutations, Ruth Hoffmann, Steve Linton, PU.M.A., 2013.


EPSRC Impact Acceleration Account (IAA) awarded £15'000 to C3+.
SICSA Data Science Workshop Fund awarded £1'000 to host a workshop series for the Institute of Data Intensive Research.


October 2019 Seminar, Heriot-Watt University, Edinburgh, Invited Speaker
May 2019 GWiCS Seminar, University of Glasgow, Glasgow, Invited Speaker
November 2018 SICSA DEMOFest, Our Dynamic Earth, Edinburgh, Poster Presentation
November 2017 FP Seminar, University of St Andrews, St Andrews, Invited Speaker
March 2017 FP Seminar, University of St Andrews, St Andrews, Invited Speaker
February 2017 Seminar, Strathclyde University, Glasgow, Invited Speaker
December 2016 FATA Seminar, University of Glasgow, Glasgow, Invited Speaker
December 2016 Seminar, Open University, Milton Keyes, Invited Speaker
November 2016 SICSA DEMOFest, Strathclyde University, Glasgow, Poster Presentation
September 2016 FMICS-AVOCS, CNR, Pisa, Speaker
May 2016 D3S Seminar, Charles University, Prague, Invited Speaker
May 2016 FATA Seminar, University of Glasgow, Glasgow, Invited Speaker
April 2016 SPIN, Eindhoven University of Technology, Eindhoven, Speaker
March 2016 BCTCS, Queen's University Belfast, Belfast, Speaker
October 2015 FATA Seminar, University of Glasgow, Glasgow, Invited Speaker
October 2015 School of Computing Research Colloquium, University of Leeds, Leeds, Invited Speaker
June 2015 Permutation Patterns 2015, LMS London, London, Speaker
April 2015 North British Semigroups and Applications Network, University of St Andrews, St Andrews, Invited Speaker
April 2015 CIRCA Lunch Seminar, University of St Andrews, St Andrews, Invited Speaker
July 2014 Permutation Patterns 2014, East Tennessee University, Johnson City, Speaker
June 2014 SICSA PhD Conference, University of St Andrews, St Andrews, Poster Presentation
August 2013 FSMNLP, University of St Andrews, St Andrews, Invited Tutorial Speaker
July 2013 Permutation Patterns 2013, Universite Paris Diderot, Paris, Speaker
June 2012 Permutation Patterns 2012, Strathclyde University, Glasgow, Speaker


I have written a GAP package called PatternClass. It allows to explore the permutation pattern classes build by token passing networks as well as sets of permutations encoded by the rank encoding. Amongst other things, PatternClass can compute the basis of a permutation pattern class et vice versa, rank encode and decode permutations, create automata from token passing networks and checking if the deterministic automaton is a possible representative of a token passing network.



School of Computer Science
North Haugh
St Andrews
Fife KY16 9SX


+44 (0)1334 46 3072


rh347 <at> st-andrews <dot> ac <dot> uk