Logo der Universität Wien

Conditionally Optimal Algorithms for Generalized Büchi Games

Abstract

Games on graphs provide the appropriate framework to study several central problems in computer science, such as verification and synthesis of reactive systems. One of the most basic objectives for games on graphs is the liveness (or Büchi) objective that given a target set of vertices requires that some vertex in the target set is visited infinitely often. We study generalized Büchi objectives (i.e., conjunction of liveness objectives), and implications between two generalized Büchi objectives (known as GR(1) objectives), that arise in numerous applications in computer-aided verification. We present improved algorithms and conditional super-linear lower bounds based on widely believed assumptions about the complexity of (A1) combinatorial Boolean matrix multiplication and (A2) CNF-SAT. We consider graph games with n vertices, m edges, and generalized Büchi objectives with k conjunctions. First, we present an algorithm with running time O(k · n^2 ), improving the previously known O(k · n · m) and O(k^2 · n^2 ) worst-case bounds. Our algorithm is optimal for dense graphs under (A1). Second, we show that the basic algorithm for the problem is optimal for sparse graphs when the target sets have constant size under (A2). Finally, we consider GR(1) objectives, with k1 conjunctions in the antecedent and k2 conjunctions in the consequent, and present an O(k1 · k2 · n^2.5)-time algorithm, improving the previously known O(k1 · k2 · n · m)-time algorithm for m > n^1.5.

GrafikTop
Citation
Category
Paper in Conference Proceedings or in Workshop Proceedings (Full Paper in Proceedings)
Event Title
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Divisions
Theory and Applications of Algorithms
Subjects
Theoretische Informatik
Event Location
Krakow (Poland)
Event Type
Conference
Event Dates
August 22-26, 2016
Series Name
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}
Page Range
25:1-25:15
Date
July 2016
Export
GrafikTop
Contact us
Faculty of Computer Science
University of Vienna

Währinger Straße 29
A-1090 Vienna