Guided search for hybrid systems based on coarse-grained space abstractions

S. Bogomolov, A. Donzé, G. Frehse, R. Grosu, T. Johnson, H. Ladan, A. Podelski, M. Wehrle, International Journal on Software Tools for Technology Transfer 18 (2016) 449–467.

Download
OA IST-2016-457-v1+1_s10009-015-0393-y.pdf 2.30 MB

Journal Article | Published | English

Scopus indexed
Author
Bogomolov, SergiyIST Austria ; Donzé, Alexandre; Frehse, Goran; Grosu, Radu; Johnson, Taylor; Ladan, Hamed; Podelski, Andreas; Wehrle, Martin
Department
Abstract
Hybrid systems represent an important and powerful formalism for modeling real-world applications such as embedded systems. A verification tool like SpaceEx is based on the exploration of a symbolic search space (the region space). As a verification tool, it is typically optimized towards proving the absence of errors. In some settings, e.g., when the verification tool is employed in a feedback-directed design cycle, one would like to have the option to call a version that is optimized towards finding an error trajectory in the region space. A recent approach in this direction is based on guided search. Guided search relies on a cost function that indicates which states are promising to be explored, and preferably explores more promising states first. In this paper, we propose an abstraction-based cost function based on coarse-grained space abstractions for guiding the reachability analysis. For this purpose, a suitable abstraction technique that exploits the flexible granularity of modern reachability analysis algorithms is introduced. The new cost function is an effective extension of pattern database approaches that have been successfully applied in other areas. The approach has been implemented in the SpaceEx model checker. The evaluation shows its practical potential.
Publishing Year
Date Published
2016-08-01
Journal Title
International Journal on Software Tools for Technology Transfer
Volume
18
Issue
4
Page
449 - 467
IST-REx-ID

Cite this

Bogomolov S, Donzé A, Frehse G, et al. Guided search for hybrid systems based on coarse-grained space abstractions. International Journal on Software Tools for Technology Transfer. 2016;18(4):449-467. doi:10.1007/s10009-015-0393-y
Bogomolov, S., Donzé, A., Frehse, G., Grosu, R., Johnson, T., Ladan, H., … Wehrle, M. (2016). Guided search for hybrid systems based on coarse-grained space abstractions. International Journal on Software Tools for Technology Transfer, 18(4), 449–467. https://doi.org/10.1007/s10009-015-0393-y
Bogomolov, Sergiy, Alexandre Donzé, Goran Frehse, Radu Grosu, Taylor Johnson, Hamed Ladan, Andreas Podelski, and Martin Wehrle. “Guided Search for Hybrid Systems Based on Coarse-Grained Space Abstractions.” International Journal on Software Tools for Technology Transfer 18, no. 4 (2016): 449–67. https://doi.org/10.1007/s10009-015-0393-y.
S. Bogomolov et al., “Guided search for hybrid systems based on coarse-grained space abstractions,” International Journal on Software Tools for Technology Transfer, vol. 18, no. 4, pp. 449–467, 2016.
Bogomolov S, Donzé A, Frehse G, Grosu R, Johnson T, Ladan H, Podelski A, Wehrle M. 2016. Guided search for hybrid systems based on coarse-grained space abstractions. International Journal on Software Tools for Technology Transfer. 18(4), 449–467.
Bogomolov, Sergiy, et al. “Guided Search for Hybrid Systems Based on Coarse-Grained Space Abstractions.” International Journal on Software Tools for Technology Transfer, vol. 18, no. 4, Springer, 2016, pp. 449–67, doi:10.1007/s10009-015-0393-y.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
Access Level
OA Open Access
Date Uploaded
2018-12-12
MD5 Checksum
31561d7705599a9bd4ea816accc0752e


Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar