Schedulers and finishers: On generating the behaviours of an event structure

Annabelle McIver, Tahiry Rabehaja*, Georg Struth

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

1 Citation (Scopus)

Abstract

It is well known that every trace of a transition system can be generated using a scheduler. However,this basic completeness result does not hold in event structure models. The reason for this failure is that,according to its standard definition,a scheduler chooses which action to schedule and,at the same time,finishes the one scheduled last. Thus,scheduled events will never be able to overlap. We propose to separate scheduling from finishing and introduce the dual notion of finishers which,together with schedulers,are enough to regain completeness back. We then investigate all possible interactions between schedulers and finishers,concluding that simple alternating interactions are enough to express complex ones. Finally,we show how finishers can be used to filter behaviours to the extent to which they capture intrinsic system characteristics.

Original languageEnglish
Title of host publicationTheoretical Aspects of Computing - ICTAC 2016, 13th International Colloquium, Proceedings
EditorsAugusto Sampaio, Farn Wang
Place of PublicationCham, Switzerland
PublisherSpringer, Springer Nature
Pages121-138
Number of pages18
Volume9965 LNCS
ISBN (Print)9783319467498
DOIs
Publication statusPublished - 2016
Event13th International Colloquium on Theoretical Aspects of Computing, ICTAC 2016 - Taipei, Taiwan
Duration: 24 Oct 201631 Oct 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9965 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other13th International Colloquium on Theoretical Aspects of Computing, ICTAC 2016
Country/TerritoryTaiwan
CityTaipei
Period24/10/1631/10/16

Fingerprint

Dive into the research topics of 'Schedulers and finishers: On generating the behaviours of an event structure'. Together they form a unique fingerprint.

Cite this