Generalized Büchi Games

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