Talks and Poster Presentations (with Proceedings-Entry):
A. Fellner, T. Tarrach, G. Weissenbacher:
"Language Inclusion for Finite Prime Event Structures";
Talk: International Conference on Verification, Model Checking, and Abstract Interpretation (VMCAI),
New Orleans, LA, USA;
- 2020-01-21; in: "Verification, Model Checking, and Abstract Interpretation",
We study the problem of language inclusion between finite, labeled prime event structures. Prime event structures are a formalism to compactly represent concurrent behavior of discrete systems. A labeled prime event structure induces a language of sequences of labels produced by the represented system. We study the problem of deciding inclusion and membership for languages encoded by finite prime event structures and provide complexity results for both problems. We provide a family of examples where prime event structures are exponentially more succinct than formalisms that do not take concurrency into account. We provide a decision algorithm for language inclusion that exploits this succinctness. Furthermore, we provide an implementation of the algorithm and an evaluation on a series of benchmarks. Finally, we demonstrate how our results can be applied to mutation-based test case generation.
Event structures, Language inclusion, Concurrency, Mutation-based test case generation
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
Created from the Publication Database of the Vienna University of Technology.