Model and objective separation with conditional lower bounds disjunction is harder than conjunction

K. Chatterjee, W. Dvoák, M. Henzinger, V. Loitzenbauer, in:, Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2016, pp. 197–206.


Conference Paper | Published | English
Author
; ; ;
Department
Series Title
Proceedings Symposium on Logic in Computer Science
Abstract
Given a model of a system and an objective, the model-checking question asks whether the model satisfies the objective. We study polynomial-time problems in two classical models, graphs and Markov Decision Processes (MDPs), with respect to several fundamental -regular objectives, e.g., Rabin and Streett objectives. For many of these problems the best-known upper bounds are quadratic or cubic, yet no super-linear lower bounds are known. In this work our contributions are two-fold: First, we present several improved algorithms, and second, we present the first conditional super-linear lower bounds based on widely believed assumptions about the complexity of CNF-SAT and combinatorial Boolean matrix multiplication. A separation result for two models with respect to an objective means a conditional lower bound for one model that is strictly higher than the existing upper bound for the other model, and similarly for two objectives with respect to a model. Our results establish the following separation results: (1) A separation of models (graphs and MDPs) for disjunctive queries of reachability and Büchi objectives. (2) Two kinds of separations of objectives, both for graphs and MDPs, namely, (2a) the separation of dual objectives such as Streett/Rabin objectives, and (2b) the separation of conjunction and disjunction of multiple objectives of the same type such as safety, Büchi, and coBüchi. In summary, our results establish the first model and objective separation results for graphs and MDPs for various classical -regular objectives. Quite strikingly, we establish conditional lower bounds for the disjunction of objectives that are strictly higher than the existing upper bounds for the conjunction of the same objectives. © 2016 ACM.
Publishing Year
Date Published
2016-07-05
Proceedings Title
Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science
Acknowledgement
K. C., M. H., and W. D. are partially supported by the Vienna Science and Technology Fund (WWTF) through project ICT15-003. K. C. is partially supported by the Austrian Science Fund (FWF) NFN Grant No S11407-N23 (RiSE/SHiNE) and an ERC Start grant (279307: Graph Games). For W. D., M. H., and V. L. the research leading to these results has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement no. 340506.
Page
197 - 206
Conference
LICS: Logic in Computer Science
Conference Location
New York, NY, USA
Conference Date
2016-07-05 – 2016-07-08
IST-REx-ID

Cite this

Chatterjee K, Dvoák W, Henzinger M, Loitzenbauer V. Model and objective separation with conditional lower bounds disjunction is harder than conjunction. In: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science. IEEE; 2016:197-206. doi:10.1145/2933575.2935304
Chatterjee, K., Dvoák, W., Henzinger, M., & Loitzenbauer, V. (2016). Model and objective separation with conditional lower bounds disjunction is harder than conjunction. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (pp. 197–206). New York, NY, USA: IEEE. https://doi.org/10.1145/2933575.2935304
Chatterjee, Krishnendu, Wolfgang Dvoák, Monika Henzinger, and Veronika Loitzenbauer. “Model and Objective Separation with Conditional Lower Bounds Disjunction Is Harder than Conjunction.” In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, 197–206. IEEE, 2016. https://doi.org/10.1145/2933575.2935304.
K. Chatterjee, W. Dvoák, M. Henzinger, and V. Loitzenbauer, “Model and objective separation with conditional lower bounds disjunction is harder than conjunction,” in Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, New York, NY, USA, 2016, pp. 197–206.
Chatterjee K, Dvoák W, Henzinger M, Loitzenbauer V. 2016. Model and objective separation with conditional lower bounds disjunction is harder than conjunction. Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science, Proceedings Symposium on Logic in Computer Science, 197–206.
Chatterjee, Krishnendu, et al. “Model and Objective Separation with Conditional Lower Bounds Disjunction Is Harder than Conjunction.” Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, IEEE, 2016, pp. 197–206, doi:10.1145/2933575.2935304.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar