Refinement Composition Using Doubly Labeled Transition Graphs
Abstract
Process Algebra forms a cornerstone in the formal methods area of Computer Science. Among the more widely used approaches is Milner's Communication and Concurrency Systems (CCS). Recently CCS has been extended by Schmidt and Bibighaus through the introduction of Doubly Labeled Transition Systems. This framework has enhanced the model s ability to capture security and availability properties. In this thesis we reformulate, simplify, and extend Bibighaus work using a graph theoretic framework. The intent is that this abstract mathematical view will make the results more accessible and stimulate additional research. Existing definitions and theorems are redefined and proved using Labeled and Doubly Labeled Transition Graphs (LTG and DLTG). CCS simulation concepts are recast as graph morphisms and the notion of abstraction and refinement are explained through the use of graphs. Bibighaus work is extended by showing how to carry out non-atomic DLTG refinement, and by developing a form of graph composition involving graph refinements that share a common abstract graph. This type of composition is proven to always be possible with DLTG refinements, and we demonstrate that the composite graph is both a refinement of the abstract graph, and an abstract graph for the refinements from which it was made.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 2007
- Accession Number
- ADA474356
Entities
People
- Thor Martinsen
Organizations
- Naval Postgraduate School