Disjunctive coBüchi Objectives

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 coBüchi: given a set of target vertices TVT\subseteq V, determine whether or not there is a path that visits the set TT a finite amount of times. Furthermore, in the disjunctive problem, you are given multiple coBüchi objectives (i.e. multiple target sets TiT_i) and you are to determine whether or not there is a path where at least one of the coBüchi objectives is satisfied (i.e. whether or not an infinite path visits any target set TiT_i a finite amount of times).

Parameters

  • nn: number of vertices
  • mm: number of edges
  • MECMEC: O(\min(n^2, m^{1.5}))

Insufficient data to display graph

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Insuffient Data to display table

Reductions Table

Displaying 1 of 1 reductions

Other relevant algorithms

Insuffient Data to display table