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

Abstract

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
Pages46-60
ISBN (Print)978-3-642-14457-8
ISBN (Electronic)978-3-642-14458-5
DOIs
Publication statusPublished - 2010
Externally publishedYes
Event9th International Workshop on Web Services and Formal Methods - Bologna, Italy
Duration: 4 Sep 20095 Sep 2009
Conference number: 9

Conference

Conference9th International Workshop on Web Services and Formal Methods
Number9
CountryItaly
CityBologna
Period04/09/200905/09/2009
SeriesLecture Notes in Computer Science
Volume4912
ISSN0302-9743

Cite this

Bruni, R., Gadducci, F., & Lluch Lafuente, A. (2010). A Graph Syntax for Processes and Services. In Web Services and Formal Methods: 6th International Workshop, WS-FM 2009, Bologna, Italy, September 4-5, 2009, Revised Selected Papers (pp. 46-60). Springer Berlin Heidelberg. Lecture Notes in Computer Science, Vol.. 4912 https://doi.org/10.1007/978-3-642-14458-5_3