Language Inclusion for Finite Prime Event Structures
Abstrak
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.
Topik & Kata Kunci
Penulis (3)
Andreas Fellner
Thorsten Tarrach
Georg Weissenbacher
Akses Cepat
- Tahun Terbit
- 2019
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓