Disjunctive Queries of Safety in Graphs: Difference between revisions
(Created page with "{{DISPLAYTITLE:Disjunctive Queries of Safety in Graphs (Model-Checking Problem)}} == Description == Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective. In this case, the model is a standard graph, and the objective is safety: given a set of target vertices $T\subseteq V$, determine whether or not there is a path that does not visit any vertex in $T$ (i.e. you want to avoid all vertices in $T$). Furthe...") |
No edit summary |
||
| Line 18: | Line 18: | ||
== Parameters == | == Parameters == | ||
n: number of vertices | |||
m: number of edges | m: number of edges | ||
k: number of objectives | k: number of objectives | ||
MEC: O(\min(n^2, m^{1.5})) | |||
MEC: O(\min(n^2, m^{1.5})) | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Revision as of 12:04, 15 February 2023
Description
Given a model of a system and an objective, the model-checking problem asks whether the model satisfies the objective.
In this case, the model is a standard graph, and the objective is safety: given a set of target vertices $T\subseteq V$, determine whether or not there is a path that does not visit any vertex in $T$ (i.e. you want to avoid all vertices in $T$).
Furthermore, in the disjunctive queries problem, you are given multiple safety objectives (i.e. multiple target sets $T_i$) and you are to determine whether or not there is a path where at least one of the safety objectives is satisfied (i.e. whether or not an infinite path avoids all vertices in at least one of the target sets).
Disjunctive queries coincide with disjunctive objectives on graphs.
Related Problems
Generalizations: Safety in Graphs
Related: Reachability in MDPs, Disjunctive Reachability Queries in MDPs, Conjunctive Reachability Queries in MDPs, Safety in MDPs, Disjunctive Safety Queries in MDPs, Conjunctive Safety Queries in MDPs, Disjunctive coBüchi Objectives, Generalized Büchi Games
Parameters
n: number of vertices
m: number of edges
k: number of objectives
MEC: O(\min(n^2, m^{1.5}))
Table of Algorithms
Currently no algorithms in our database for the given problem.
Reductions FROM Problem
| Problem | Implication | Year | Citation | Reduction |
|---|---|---|---|---|
| Triangle Detection | assume: Strong Triangle then: there is no combinatorial $O(n^{3-\epsilon})$ or $O((k \cdot n^{2})^{1-\epsilon})$ algorithm, for any $\epsilon > {0}$ for disjunctive safety (objectives or queries) in graphs. |
2016 | https://dl-acm-org.ezproxy.canberra.edu.au/doi/pdf/10.1145/2933575.2935304 | link |
| OV | assume: OVH then: there is no $O(m^{2-\epsilon})$ or $O((k \cdot m)^{1 - \epsilon})$ algorithm for any $\epsilon > {0}$ for disjunctive safety ovjectives/queries in MDPs. |
2016 | https://dl-acm-org.ezproxy.canberra.edu.au/doi/pdf/10.1145/2933575.2935304 | link |