On the specification of higher dimensional automata

Richard Buckland, Michael Johnson, Dominic Verity

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

Higher dimensional automata (HDA) have been widely studied as models of concurrent processes. Most current work focuses on developing the directed algebraic topological notions required to analyse HDA to determine their computer scientific properties (deadlock, safety, unreachable states, etc). Instead, this paper is concerned with the software engineering of HDA and details the specification of HDA by process algebra operations. The specifications work for cubical HDA, but are designed to also work for the explicit choice higher dimensional automata (ECHDA) originally proposed by Buckland. We introduce ω-multigraphs, a graphical notion which is easier to use than pasting schemes but more general than cubical complexes, we describe basic process algebra operations on ECHDA as constructions on ω-multigraphs, we discuss the trichotomy of concurrent, conferring, and conflicting choices, and note that the "deadlock choice" can arise from intersecting conflicting choices, and we remark that common software engineering refinements correspond to choice refinement.

Original languageEnglish
Pages (from-to)3-13
Number of pages11
JournalElectronic Notes in Theoretical Computer Science
Volume68
Issue number1
DOIs
Publication statusPublished - Nov 2002

Fingerprint

Dive into the research topics of 'On the specification of higher dimensional automata'. Together they form a unique fingerprint.

Cite this