Higher Dimensional Transition Systems

Gian Luca Cattani and Vladimiro Sassone

In Proceedings of the Eleventh Annual IEEE Symposium on Logic in Computer Science, pages 55-62. IEEE Computer Society Press, 1996.

Available as DVI (27k) or postscript (127k).

Abstract

We introduce the notion of higher dimensional transition systems as a model of concurrency providing an elementary, set-theoretic formalisation of the idea of higher dimensional transition. We show an embedding of the category of higher dimensional transition systems into that of higher dimensional automata which cuts down to an equivalence when we restrict to non-degenerate automata. Moreover, we prove that the natural notion of bisimulation for such structures is a generalisation of the strong history preserving bisimulation, and provide an abstract categorical account of it via open maps. Finally, we define a notion of unfolding for higher dimensional transition systems and characterise the structures so obtained as a generalisation of event structures.

@InProceedings{cattani/sassone:hdts,
author=       {Gian Luca Cattani and Vladimiro Sassone},
title=        {Higher Dimensional Transition Systems},
booktitle =   {Proceedings of the Eleventh Annual IEEE Symposium on Logic 
               in Computer Science},  
pages=        {55--62},
year =        1996,
organization= {IEEE Computer Society Press},
url =         {ftp://ftp.cl.cam.ac.uk/users/glc25/hdts.ps.gz}
}