Compositional Verification of Railway Interlocking Systems
Formal Aspects of Computing · 31.03.2023 · 35 (1) · 1-46
DOI: 10.1145/3549736 ↗Kurz gefasst
Fachartikel in der Zeitschrift Formal Aspects of Computing, online erschienen am 12.01.2023. Verfasst von Anne Elisabeth Haxthausen und 1 weiteren Autor:innen. Die Arbeit wurde bisher 24-mal zitiert (Crossref) und nennt 33 Literaturangaben.
Abstract (Originalsprache)
Model checking techniques have often been applied to the verification of railway interlocking systems, responsible for guiding trains safely through a given railway network. However, these techniques fail to scale to the interlocking systems controlling large stations, composed of hundreds and even thousands of controlled entities, due to the state space explosion problem. Indeed, interlocking systems exhibit a certain degree of locality that allows some reasoning only on the mere set of entities that regard the train movements, but safe routing through a complex station layout requires a global reservation policy, which can require global state conditions to be taken into account. In this article, we present a compositional approach aimed at chopping the verification of a large interlocking system into that of smaller fragments, exploiting in each fragment a proper abstraction of the global information on routing state. A proof is given of the thesis that verifying the safety of the smaller fragments is sufficient to verify the safety of the whole network. Experiments using this compositional approach have shown important gains in performance of the verification, as well as in the size of affordable station layouts.
Zitieren
APA
Haxthausen, A. E., & Fantechi, A. (2023). Compositional Verification of Railway Interlocking Systems. Formal Aspects of Computing, 35(1), 1-46. https://doi.org/10.1145/3549736
Vancouver
Haxthausen AE, Fantechi A. Compositional Verification of Railway Interlocking Systems. Formal Aspects of Computing. 2023;35(1):1-46. doi:10.1145/3549736
BibTeX
@article{Haxthausen2023,
author = {Haxthausen, Anne Elisabeth and Fantechi, Alessandro},
title = {Compositional Verification of Railway Interlocking Systems},
journal = {Formal Aspects of Computing},
year = {2023},
volume = {35},
number = {1},
pages = {1--46},
doi = {10.1145/3549736}
}
EUVIMED