Delayed-Choice Semantics for Pomset Families and Message Sequence Graphs

Clemens DubslaffClemens Dubslaff, Christel BaierChristel Baier

DOI Link

Clemens Dubslaff, Christel Baier
Delayed-Choice Semantics for Pomset Families and Message Sequence Graphs
ModelEd, TestEd, TrustEd - Essays Dedicated to Ed Brinksma on the Occasion of His 60th Birthday, volume 10500 of Lecture Notes in Computer Science, 64--84, 2017. Springer

Details
Bibtex

KurzfassungAbstract
Message sequence charts (MSCs) are diagrams widely used to describe communication scenarios. Their higher-order formalism is provided by graphs over MSCs, called message sequence graphs (MSGs), which naturally induce a non-interleaving linear-time semantics in terms of a pomset family. Besides this pomset semantics, an operational semantics for MSGs was standardized by the ITU-T as an interleaving branching-time semantics using a process-algebraic approach. A key ingredient in the latter semantics is delayed choice, formalizing that choices between communication scenarios are only made when they are inevitable. In this paper, an approach towards branching-time semantics for pomset families that follows the concept of delayed choice is proposed. First, transition-system semantics are provided where global states comprise cuts of pomsets represented either by suffixes or prefixes of family members. Second, an event-structure semantics is presented those benefit is to maintain the causal dependencies of events provided by the pomset family. These semantics are also investigated in the context of pomset families generated by MSGs.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-68270-9_4.

@inproceedings{DB2017,
  author    = {Clemens Dubslaff and Christel Baier},
  title     = {Delayed-Choice Semantics for Pomset Families and Message Sequence
               Graphs},
  booktitle = {ModelEd, {TestEd,} {TrustEd} - Essays Dedicated to Ed Brinksma on
               the Occasion of His 60th Birthday},
  series    = {Lecture Notes in Computer Science},
  volume    = {10500},
  publisher = {Springer},
  year      = {2017},
  pages     = {64--84},
  doi       = {10.1007/978-3-319-68270-9_4}
}