Posets With Interfaces as a Model for Concurrency

Authors

Uli Fahrenberg, Christian Johansen, Georg Struth, Krzysztof Ziemianski

Journal

Information and Computation

Type

article

Projects

AA"AA" is not in the list (Vaucanson, Spot, URBI, Olena, APMC, Tiger, Climb, Speaker ID, Transformers, Bison, ...) of allowed values for the "Related project" property.

Date

2022-06-30

Abstract

We introduce posets with interfaces (iposets) and generalise their standard serial composition to a new gluing composition. In the partial order semantics of concurrency, interfaces and gluing allow modelling events that extend in time and across components. Alternativelytaking a decompositional view, interfaces allow cutting through events, while serial composition may only cut through edges of a poset. We show that iposets under gluing composition form a category, which generalises the monoid of posets under serial composition up to isomorphism. They form a '"`UNIQ--postMath-00000001-QINU`"'-category when a subsumption order and a lax tensor in the form of a non-commutative parallel composition are added, which generalises the interchange monoids used for modelling series-parallel posets. We also study the gluing-parallel hierarchy of iposets, which generalises the standard series-parallel one. The class of gluing-parallel iposets contains that of series-parallel posets and the class of interval orders, which are well studied in concurrency theory, too. We also show that it is strictly contained in the class of all iposets by identifying several forbidden substructures.

Documents

• Paper

Bibtex (lrde.bib)

@Article{	  fahrenberg.22.iandc,
  author	= {Uli Fahrenberg and Christian Johansen and Georg Struth and
		  Krzysztof Ziemianski},
  title		= {Posets With Interfaces as a Model for Concurrency},
  journal	= {Information and Computation},
  volume	= {285},
  number	= {B},
  pages		= {104914},
  year		= {2022},
  url		= {https://doi.org/10.1016/j.ic.2022.104914},
  doi		= {10.1016/j.ic.2022.104914},
  timestamp	= {Tue, 28 Jun 2022 21:08:18 +0200},
  biburl	= {https://dblp.org/rec/journals/iandc/FahrenbergJSZ22.bib},
  bibsource	= {dblp computer science bibliography, https://dblp.org},
  abstract	= {We introduce posets with interfaces (iposets) and
		  generalise their standard serial composition to a new
		  gluing composition. In the partial order semantics of
		  concurrency, interfaces and gluing allow modelling events
		  that extend in time and across components. Alternatively,
		  taking a decompositional view, interfaces allow cutting
		  through events, while serial composition may only cut
		  through edges of a poset. We show that iposets under gluing
		  composition form a category, which generalises the monoid
		  of posets under serial composition up to isomorphism. They
		  form a $2$-category when a subsumption order and a lax
		  tensor in the form of a non-commutative parallel
		  composition are added, which generalises the interchange
		  monoids used for modelling series-parallel posets. We also
		  study the gluing-parallel hierarchy of iposets, which
		  generalises the standard series-parallel one. The class of
		  gluing-parallel iposets contains that of series-parallel
		  posets and the class of interval orders, which are well
		  studied in concurrency theory, too. We also show that it is
		  strictly contained in the class of all iposets by
		  identifying several forbidden substructures.}
}