Academic Journals Database
Disseminating quality controlled scientific knowledge

An Algebra of Hierarchical Graphs and its Application to Structural Encoding

Author(s): R. Bruni | F. Gadducci | A. Lluch Lafuente

Journal: Scientific Annals of Computer Science
ISSN 1843-8121

Volume: 20;
Start page: 53;
Date: 2010;
VIEW PDF   PDF DOWNLOAD PDF   Download PDF Original page

We define an algebraic theory of hierarchical graphs, whose axioms characterise graph isomorphism: two terms are equated exactly when they represent the same graph. Our algebra can be understood as a high-level language for describing graphs with a node-sharing, embedding structure, and it is then well suited for defining graphical representations of software models where nesting and linking are key aspects. In particular, we propose the use of our graph formalism as a convenient way to describe configurations in process calculi equipped with inherently hierarchical features such as sessions, locations, transactions, membranes or ambients. The graph syntax can be seen as an intermediate representation language, that facilitates the encodings of algebraic specifications, since it provides primitives for nesting, name restriction and parallel composition. In addition, proving soundness and correctness of an encoding (i.e. proving that structurally equivalent processes are mapped to isomorphic graphs) becomes easier as it can be done by induction over the graph syntax.
RPA Switzerland

RPA Switzerland

Robotic process automation


Tango Jona
Tangokurs Rapperswil-Jona