Algebraic Synchronization Trees and Processes

The study of recursive program schemes is one of the classic topics in programming language semantics. One of the main goals of this line of research is to define the semantics of systems of recursive equations such as F(n) = if iszero(n) then 1 else n * F(n-1). In this talk, I will consider recursion schemes from a process-algebraic perspective and view them as a way of defining synchronization trees. In particular, I will investigate the relative expressive power of regular and algebraic recursion schemes over two signatures, which are based on those for Basic CCS and Basic Process Algebra, as a means for defining synchronization trees up to isomorphism as well as modulo bisimilarity and language equivalence. Amongst other results, I will present a generalization of a celebrated result by Bergstra and Klop to the effect that the process describing the behaviour of a bag over a two element data set is not definable in BPA with recursive definitions. I will also compare the expressiveness of algebraic recursion schemes to that of the low levels in the classic Caucal hierarchy of infinite graphs. The talk is based on joint work with Arnaud Carayol (LIGM, Universite' Paris-Est, CNRS, France), Zoltan Esik (Institute of Informatics, University of Szeged, Hungary) and Anna Ingolfsdottir ((ICE-TCS, School of Computer Science, Reykjavik University, Iceland). This work will be presented at ICALP 2012. The extended abstract is available at http://www.ru.is/faculty/luca/PAPERS/algsynchICALPfinal.pdf