1. Verifying higher-order concurrency with data automata
- Author
-
Ranko Lazić, Alex Dixon, Andrzej S. Murawski, Igor Walukiewicz, Laboratoire Bordelais de Recherche en Informatique (LaBRI), and Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)
- Subjects
QA75 ,Theoretical computer science ,Recursion ,Game semantics ,Computer science ,Semantics (computer science) ,Concurrency ,010102 general mathematics ,[INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO] ,0102 computer and information sciences ,01 natural sciences ,Decidability ,Automaton ,TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES ,Fragment (logic) ,010201 computation theory & mathematics ,Concurrent computing ,Computer Science::Programming Languages ,0101 mathematics ,Computer Science::Formal Languages and Automata Theory - Abstract
International audience; 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 treestructured 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.
- Published
- 2021
- Full Text
- View/download PDF