Algebra of Parametrised Graphs

  1. Lookup NU author(s)
  2. Dr Andrey Mokhov
  3. Dr Victor Khomenko
  4. Arseniy Alekseyev
  5. Professor Alex Yakovlev
Author(s)Yakovlev A; Khomenko V; Mokhov A; Alekseyev A
Editor(s)Brandt, J., Heljanko, K.
Publication type Conference Proceedings (inc. Abstract)
Conference Name12th International Conference on Application of Concurrency to System Design (ACSD)
Conference LocationHamburg, Germany
Year of Conference2012
Date27-29 June 2012
Volume
Pages22-31
ISBN9780769547091
Full text is available for this publication:
One of the difficulties in designing modern hardware systems is the necessity to comprehend and to deal with a very large number of system configurations, operational modes, and behavioural scenarios. It is often infeasible to consider and specify each individual mode explicitly, and one needs methodologies and tools to exploit similarities between the individual modes and work with groups of modes rather than individual ones. The modes and groups of modes have to be managed in a compositional way: the specification of the system should be composed from specifications of its blocks. This includes both structural and behavioural composition. Furthermore, one should be able to transform and optimise the specifications in a fully formal and natural way. In this paper we propose a new formalism, called Parameterised Graphs. It extends the existing Conditional Partial Order Graphs (CPOGs) formalism in several ways. First, it deals with general graphs rather than just partial orders. Moreover, it is fully compositional. To achieve this we introduce an algebra of Parameterised Graphs by specifying the equivalence relation by a set of axioms, which is proved to be sound, minimal and complete. This allows one to manipulate the specifications as algebraic expressions using the rules of this algebra. We demonstrate the usefulness of the developed formalism on two case studies coming from the area of microelectronics design.
PublisherIEEE Computer Society
URLhttp://dx.doi.org/10.1109/ACSD.2012.15
DOI10.1109/ACSD.2012.15
ActionsLink to this publication
Library holdingsSearch Newcastle University Library for this item