Verifying higher-order concurrency with data automata

Speaker(s)

Andrzej Murawski

Affiliation

University of Oxford

Date

June 23, 2021, 2:15 p.m.

Information about the event

online

Seminar

Seminar Automata Theory

---

Using a combination of automata-theoretic and game-semantic techniques, we propose a method for analysing higher-order concurrent programs. Our language of choice is Finitary Idealised Concurrent Algol (FICA) due to its relatively simple fully abstract game model. Our first contribution is an automata model over a tree-structured infinite data alphabet, called split automata, whose distinctive feature is the separation of control and memory. We show that every FICA term can be translated into such an automaton. Thanks to the structure of split automata, we are able to observe subtle aspects of the underlying game semantics. This enables us to identify a fragment of FICA with iteration and limited synchronisation (but without recursion), for which, in contrast to the whole FICA, a variety of verification problems turn out to be decidable. This is joint work with Alex Dixon (Warwick), Ranko Lazic (Warwick) and Igor Walukiewicz (Bordeaux), to appear at LiCS’21. I will also discuss earlier related work from FoSSaCS’21.

---