TY - GEN
T1 - Model Verification Through Dependency Graphs
AU - Enevoldsen, Søren
AU - Larsen, Kim Guldstrand
AU - Srba, Jiri
PY - 2019
Y1 - 2019
N2 - Dependency graphs, as introduced more than 20 years ago by Liu and Smolka, are oriented graphs with hyperedges that connect nodes with sets of target nodes in order to represent causal dependencies in the graph. Numerous verification problems can be reduced into the problem of computing a minimum or maximum fixed-point assignment on dependency graphs. In the original definition, assignments link each node with a Boolean value, however, in the recent work the assignment domains have been extended to more general setting, even including infinite domains. We present an overview of the recent results on extensions of dependency graphs in order to deal with verification of quantitative, probabilistic and timed systems.
AB - Dependency graphs, as introduced more than 20 years ago by Liu and Smolka, are oriented graphs with hyperedges that connect nodes with sets of target nodes in order to represent causal dependencies in the graph. Numerous verification problems can be reduced into the problem of computing a minimum or maximum fixed-point assignment on dependency graphs. In the original definition, assignments link each node with a Boolean value, however, in the recent work the assignment domains have been extended to more general setting, even including infinite domains. We present an overview of the recent results on extensions of dependency graphs in order to deal with verification of quantitative, probabilistic and timed systems.
KW - Dependency graphs
KW - Fixed-point computation
KW - On-the-fly algorithms
KW - Verification
UR - http://www.scopus.com/inward/record.url?scp=85075546005&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-30923-7_1
DO - 10.1007/978-3-030-30923-7_1
M3 - Article in proceeding
SN - 978-3-030-30922-0
T3 - Lecture Notes in Computer Science
SP - 1
EP - 19
BT - Proceedings of the 26th International SPIN Symposium on Model Checking of Software (SPIN'19)
A2 - Biondi, Fabrizio
A2 - Given-Wilson, Thomas
A2 - Legay, Axel
PB - Springer
T2 - International Symposium on Model Checking Software
Y2 - 15 July 2019 through 19 July 2019
ER -