Please use this identifier to cite or link to this item:
Title: Anti-chain based algorithms for timed/probabilistic refinement checking
Authors: Wang, Ting
Chen, Tieming
Liu, Yang
Wang, Ye
Keywords: Engineering::Computer science and engineering
Issue Date: 2017
Source: Wang, T., Chen, T., Liu, Y., & Wang, Y. (2018). Anti-chain based algorithms for timed/probabilistic refinement checking. Science China Information Sciences, 61(5), 052105-. doi:10.1007/s11432-017-9133-4
Journal: Science China Information Sciences
Abstract: Refinement checking answers the question on whether an implementation model is a refinement of a specification model, which is of great value for system verification. Some refinement relationships, e.g., trace refinement and failures/divergence refinement, have been recognized for different verification purposes. In general, refinement checking algorithms often rely on subset construction, which incurs in the state space explosion problem. Recently the anti-chain based approach has been suggested for trace refinement checking, and the results show a significant improvement. In this paper, we investigate the problems of applying the anti-chain approach to timed refinement checking (a timed implementation vs. a timed or untimed specification) and probabilistic refinement checking (a probabilistic implementation vs. a non-probabilistic specification), and show that the state space can be reduced considerably by employing the anti-chain approach. All the algorithms have been integrated into the model checking tool PAT, and the experiments have been conducted to show the efficiency of the application of anti-chains.
ISSN: 1674-733X
DOI: 10.1007/s11432-017-9133-4
Rights: © 2017 Science China Press and Springer-Verlag GmbH Germany. All rights reserved.
Fulltext Permission: none
Fulltext Availability: No Fulltext
Appears in Collections:SCSE Journal Articles

Citations 50

Updated on Mar 10, 2021

Citations 20

Updated on Mar 9, 2021

Page view(s)

Updated on May 28, 2022

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.