Causal automata
type: Item
instance of: scholarly article
title: Causal automata
zbMATH Open document ID: 0765.68103
DOI: 10.1016/0304-3975(92)90052-H
author: Jeremy Gunawardena
published in: Theoretical Computer Science
publication date: 1992-09-27T00:00:00Z
review text: This paper begins the study of causality from a logical point of view. Causality has conventionally been studied --- at least in semantics --- through the use of partially ordered sets (posets). This paper points out that a poset, without additional structure, is only capable of expressing AND causality. From the logical perspective it is natural to extend this by incorporating the ``dual'' connective OR. The paper introduces the formalism of causal automata as a convenient model in which to do this. A causal automaton is a pair \((E,\rho)\) where \(E\) is a finite set of events and \(\rho: E\to BE\) is a function from \(E\) to the free Boolean algebra generated by \(E\). The paper concentrates on motivating this model by studying Milner's notion of confluence in CCS. Confluence in CCS is a strong, labelled form of the classical notion of confluence in transition systems. (It is discussed at length in Chapter 11 of \textit{R. Milner's} book [Communication and concurrency, Prentice Hall, New York (1989; Zbl 0683.68008)].) The main result in the paper is the following causal characterisation of confluence: \[ Confluence\;\equiv\;Determinism\;+\;\{AND,OR\} Causality. \] It follows that confluence is a two dimensional phenomenon, the dimensions being measured by the extent of AND and OR causality respectively. In earlier work the author has shown that (finite) confluent processes which use only AND causality can always be built up by compositional techniques in CCS. The problem of constructing all confluent processes in a compositional manner is still open. In a subsequent work the author has given a careful treatment of the principles underlying logics of causality and has discussed the logics which must be used when the number of events is infinite [Geometric logic, causality and event structures, Proc. 2nd int. Conf. concurrency theory, Amsterdam, Aug. 26-29 1991, Lect. Notes Comput. Sci. 527, 266-280 (1991)].
Mathematics Subject Classification ID: 68Q55
Mathematics Subject Classification ID: 68Q10
zbMATH DE Number: 64236
zbMATH Keywords: causality
zbMATH Keywords: confluence
zbMATH Keywords: concurrency
zbMATH Keywords: processes
zbMATH Keywords: event structures
MaRDI profile type: Publication
cites work: Q3030238
cites work: Q4733427
cites work: Event structures and domains
cites work: Q3975937
cites work: Q3703299
cites work: Q3777424
cites work: Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
cites work: Q3965241
cites work: Q4055201
cites work: Q5514078
cites work: A calculus of communicating systems
cites work: Q3992568
cites work: On theories with a combinatorial definition of 'equivalence'
cites work: Petri nets, event structures and domains. I
cites work: Special issue on ``Combining compositionality and concurrency''. II
cites work: Q3030239
full work available at URL: 0304-3975(92)90052-h
OpenAlex ID: W2912895170
description: scientific article; zbMATH DE number 64236