A Graph Syntax for Processes and Services

Roberto Bruni, Fabio Gadducci, Alberto Lluch Lafuente

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


We propose a class of hierarchical graphs equipped with a simple algebraic syntax as a convenient way to describe configurations in languages with inherently hierarchical features such as sessions, fault- handling scopes or transactions. The graph syntax can be seen as an intermediate representation language, that facilitates the encoding of structured specifications and, in particular, of process calculi, since it provides primitives for nesting, name restriction and parallel composition. The syntax is based on an algebraic presentation that faithfully characterises families of hierarchical graphs, meaning that each term of the language uniquely identifies an equivalence class of graphs (modulo graph isomorphism). Proving soundness and completeness of an encoding (i.e. proving that structurally equivalent processes are mapped to isomorphic graphs) is then facilitated and can be done by structural induction. Summing up, the graph syntax facilitates the definition of faithful encodings, yet allowing a precise visual representation. We illustrate our work with an application to a workflow language and a service-oriented calculus.
Original languageEnglish
Title of host publicationWeb Services and Formal Methods : 6th International Workshop, WS-FM 2009, Bologna, Italy, September 4-5, 2009, Revised Selected Papers
PublisherSpringer Berlin Heidelberg
Publication date2010
ISBN (Print)978-3-642-14457-8
ISBN (Electronic)978-3-642-14458-5
Publication statusPublished - 2010
Externally publishedYes
Event9th International Workshop on Web Services and Formal Methods - Bologna, Italy
Duration: 4 Sept 20095 Sept 2009
Conference number: 9


Conference9th International Workshop on Web Services and Formal Methods
SeriesLecture Notes in Computer Science


Dive into the research topics of 'A Graph Syntax for Processes and Services'. Together they form a unique fingerprint.

Cite this