Dependency graphs with applications to verification

Søren Enevoldsen, Kim G. Larsen, Anders Mariegaard, Jiří Srba*


Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

1 Citationer (Scopus)


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. In this survey paper, we present an overview of the recent results on extensions of dependency graphs in order to deal with verification of quantitative, probabilistic, parameterized and timed systems.

TidsskriftInternational Journal on Software Tools for Technology Transfer
Udgave nummer5
Sider (fra-til)635-654
Antal sider20
StatusUdgivet - 1 okt. 2020


Dyk ned i forskningsemnerne om 'Dependency graphs with applications to verification'. Sammen danner de et unikt fingeraftryk.