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

Annabelle McIver; Tahiry Rabehaja; Georg Struth

doi:10.1007/978-3-319-46750-4_8

Schedulers and finishers

On generating the behaviours of an event structure

Annabelle McIver, Tahiry Rabehaja^*, Georg Struth

^*Corresponding author for this work

Department of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution

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 language	English
Title of host publication	Theoretical Aspects of Computing - ICTAC 2016, 13th International Colloquium, Proceedings
Editors	Augusto Sampaio, Farn Wang
Place of Publication	Cham, Switzerland
Publisher	Springer, Springer Nature
Pages	121-138
Number of pages	18
Volume	9965 LNCS
ISBN (Print)	9783319467498
DOIs	https://doi.org/10.1007/978-3-319-46750-4_8
Publication status	Published - 2016
Event	13th International Colloquium on Theoretical Aspects of Computing, ICTAC 2016 - Taipei, Taiwan, Province of China Duration: 24 Oct 2016 → 31 Oct 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9965 LNCS
ISSN (Print)	03029743
ISSN (Electronic)	16113349

Other

Other	13th International Colloquium on Theoretical Aspects of Computing, ICTAC 2016
Country	Taiwan, Province of China
City	Taipei
Period	24/10/16 → 31/10/16

Access to Document

10.1007/978-3-319-46750-4_8

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

1 Finished

Designing software for secrecy: Security-enabled program algebra
McIver, A., Morgan, C., Newton, J. & Butler, M.
1/07/10 → 31/12/13
Project: Research

Cite this

McIver, A., Rabehaja, T., & Struth, G. (2016). Schedulers and finishers: On generating the behaviours of an event structure. In A. Sampaio, & F. Wang (Eds.), Theoretical Aspects of Computing - ICTAC 2016, 13th International Colloquium, Proceedings (Vol. 9965 LNCS, pp. 121-138). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9965 LNCS). Cham, Switzerland: Springer, Springer Nature. https://doi.org/10.1007/978-3-319-46750-4_8

McIver, Annabelle ; Rabehaja, Tahiry ; Struth, Georg. / Schedulers and finishers : On generating the behaviours of an event structure. Theoretical Aspects of Computing - ICTAC 2016, 13th International Colloquium, Proceedings. editor / Augusto Sampaio ; Farn Wang. Vol. 9965 LNCS Cham, Switzerland : Springer, Springer Nature, 2016. pp. 121-138 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d68d7646fd9d449eb6b42bbf1484ffc1,

title = "Schedulers and finishers: On generating the behaviours of an event structure",

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.",

author = "Annabelle McIver and Tahiry Rabehaja and Georg Struth",

year = "2016",

doi = "10.1007/978-3-319-46750-4_8",

language = "English",

isbn = "9783319467498",

volume = "9965 LNCS",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Springer Nature",

pages = "121--138",

editor = "Augusto Sampaio and Farn Wang",

booktitle = "Theoretical Aspects of Computing - ICTAC 2016, 13th International Colloquium, Proceedings",

address = "United States",

}

McIver, A, Rabehaja, T & Struth, G 2016, Schedulers and finishers: On generating the behaviours of an event structure. in A Sampaio & F Wang (eds), Theoretical Aspects of Computing - ICTAC 2016, 13th International Colloquium, Proceedings. vol. 9965 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9965 LNCS, Springer, Springer Nature, Cham, Switzerland, pp. 121-138, 13th International Colloquium on Theoretical Aspects of Computing, ICTAC 2016, Taipei, Taiwan, Province of China, 24/10/16. https://doi.org/10.1007/978-3-319-46750-4_8

Schedulers and finishers : On generating the behaviours of an event structure. / McIver, Annabelle; Rabehaja, Tahiry; Struth, Georg.

Theoretical Aspects of Computing - ICTAC 2016, 13th International Colloquium, Proceedings. ed. / Augusto Sampaio; Farn Wang. Vol. 9965 LNCS Cham, Switzerland : Springer, Springer Nature, 2016. p. 121-138 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9965 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution

TY - GEN

T1 - Schedulers and finishers

T2 - On generating the behaviours of an event structure

AU - McIver, Annabelle

AU - Rabehaja, Tahiry

AU - Struth, Georg

PY - 2016

Y1 - 2016

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84996598152&partnerID=8YFLogxK

UR - http://purl.org/au-research/grants/arc/DP1092464

U2 - 10.1007/978-3-319-46750-4_8

DO - 10.1007/978-3-319-46750-4_8

M3 - Conference proceeding contribution

SN - 9783319467498

VL - 9965 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 121

EP - 138

BT - Theoretical Aspects of Computing - ICTAC 2016, 13th International Colloquium, Proceedings

A2 - Sampaio, Augusto

A2 - Wang, Farn

PB - Springer, Springer Nature

CY - Cham, Switzerland

ER -

McIver A, Rabehaja T, Struth G. Schedulers and finishers: On generating the behaviours of an event structure. In Sampaio A, Wang F, editors, Theoretical Aspects of Computing - ICTAC 2016, 13th International Colloquium, Proceedings. Vol. 9965 LNCS. Cham, Switzerland: Springer, Springer Nature. 2016. p. 121-138. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-46750-4_8