The equational theory of pomsets
type: Item
instance of: scholarly article
title: The equational theory of pomsets
zbMATH Open document ID: 0669.68015
DOI: 10.1016/0304-3975(88)90124-7
author: Jay L. Gischer
published in: Theoretical Computer Science
publication date: 1988-01-01T00:00:00Z
review text: A labeled partial order is a partially ordered set together with a labeling of each element (by a symbol from some alphabet). A partially- ordered multiset, or pomset, is an isomorphism class of some labeled partial order. Pomsets have been used as a model of concurrency and as an aid in understanding the semantics of parallel programs The author investigates the axiomatic properties of pomsets, sets of pomsets and ideals of pomsets. He shows, for example, that the equational theory of pomsets under the operations of concatenation, parallel composition and union is finitely axiomatizable. Similar results are obtained for ideals of pomsets.
Mathematics Subject Classification ID: 68Q60
Mathematics Subject Classification ID: 06A06
zbMATH DE Number: 4096763
zbMATH Keywords: partial order equational theory
zbMATH Keywords: pomset
zbMATH Keywords: semantics of parallel programs
MaRDI profile type: Publication
full work available at URL: 0304-3975(88)90124-7
OpenAlex ID: W1981404622
cites work: Q4187288
cites work: Relations of flow languages to Petri net languages
cites work: Net theory and applications. Proceedings of the Advanced Course on General Net Theory of Processes and Systems, Hamburg, October 8-19, 1979. Ed. by Wilfried Brauer
cites work: A Theory of Communicating Sequential Processes
cites work: Q5639639
cites work: Shuffle languages, Petri nets, and context-sensitive grammars
cites work: Q3922196
cites work: Q4136519
cites work: Q3777424
cites work: Q4055972
cites work: The power of synchronizing operations on strings
cites work: Extending regular expressions with iterated shuffle
cites work: Q4138147
cites work: Q4140399
cites work: Time, clocks, and the ordering of events in a distributed system
cites work: The mutual exclusion problem
cites work: A calculus of communicating systems
cites work: A complete inference system for a class of regular behaviours
cites work: Q3680249
cites work: Modeling concurrency with partial orders
cites work: Q5596826
cites work: Two Complete Axiom Systems for the Algebra of Regular Events
cites work: Software Descriptions with Flow Expressions
cites work: Q3883468
cites work: The Recognition of Series Parallel Digraphs
cites work: Q3683531
cites work: Complements and transitive closures
description: scientific article; zbMATH DE number 4096763