Home

Papers

Pomsets

• The pomset model of parallel processes: Unifying the temporal and the spatial - V. Pratt (1984)

  • Introduction to the pomsets , basic definitions, examples.

• Pomsets with Boxes: Protection, Separation, and Locality in Concurrent Kleene Algebra - Paul Brunet, David Pym (FSCD 2020).

  • Interesting concept of boxes over pomsets which are used to enforce certain forms of non-interference and prohibit some interleavings. Can be useful to model various atomicity primitives.
  • Pomset logic as a specification language for properties of programs and its relationship to CKA.

Event Structures

• Event Structures - Markus Hoffmann.

  • A very gentle introduction to prime and stable event structures.

• Event Structures - Glynn Winskel (1986).

  • Definition of event structures (through consistency predicate and enabling relation).
  • Definition of stable event structures, motivation, examples.
  • Family of configurations, prime algebraic domains, connection to Scott domains.
  • Denotational semantics of CCS.

• Event Structure Semantics For CCS and Related Languages - Glynn Winskel (1983).

  • General definition of event structures as a family of configurations.
  • cpo (chain-complete partial order) on event structures.
  • Denotational semantics of CCS.

• Bundle Event Structures and CCSP - Rob van Glabbeek and Frits Vaandrager (CONCUR 2003).

  • Definition of bundle event structures.
  • Denotational semantics of CCSP (CCS + CSP).

• Flow models of distributed computations: event structures and nets - Gérard Boudol, Ilaria Castellani (1991).

  • Flow event structures, connection to prime, bundle, and stable event structures, connection to Petri Nets.

• Reversibility and Models for Concurrency - Iain Phillips, Irek Ulidowski (ENTCS 2007)

  • Prime event structures as a non-interleaving model for reversible computations.
  • Definition of prime event structures with general conflict.

• A Complete Theory of Deterministic Event Structures - Arend Rensink (CONCUR 1995)

  • Subclass of deterministic prime event structures.
  • Sound and complete equational theory for deterministic event structures (the signature of the theory is similar to CKA).
  • Definition of prime event structure with consistency predicate (dual to general conflict).

• Minimisation of Event Structures - Paolo Baldan, Alessandra Raffaetà (2019)

  • Theory of minimization of event structures, that is construction of a minimal event structure equivalent to the original (by hereditary history preserving bisimilarity).
  • Formal definitions of various classes of event structures: poset, prime, asymmetric, bundle, flow.
  • Formal definition of (hereditary) history preserving bisimulation.

• Language Inclusion for Finite Prime Event Structures - Andreas Fellner, Thorsten Tarrach, Georg Weissenbacher (VMCAI 2020).

  • Study of a word membership and language inclusion problems for finite prime event structures.
  • Application to mutation-based test case generation.

Concurrent Kleene Algebra

• Brzozowski Goes Concurrent: A Kleene Theorem for Pomset Languages - T. Kappé, P. Brunet, B. Luttik, A. Silva, F. Zanasi (CONCUR 2017).
  • Operational and denotational model (based on series-parallel pomset languages) for the bi-Kleene Algebra.
  • Kleene Theorem for weak bi-Kleene Algebra (i.e. CKA without parallel star and exchange law).

Weak Memory / Relaxed Concurrency

• Weak Memory Bibliography list

Tools

• The SAV-Science LaTeX Package