K. Etessami, M. Kwiatkowska, M. Y. Vardi, M. Yannakakis
Abstract. We study and provide efficient algorithms for multi-objective model checking problems for Markov Decision Processes (MDPs). Given an MDP, M, and given multiple linear-time (ω-regular or...
K. Etessami, M. Kwiatkowska, M. Y. Vardi, M. Yannakakis
Abstract. We study and provide efficient algorithms for multi-objective model checking problems for Markov Decision Processes (MDPs). Given an MDP, M, and given multiple linear-time (ω-regular or...
E. G. Coffman, C. Courcoubetis, M. R. Garey, D. S. Johnson, P. W. Shor, R. R. Weber, ...
Abstract. We consider the one-dimensional bin packing problem under the discrete uniform distributions U{j, k}, 1 ≤ j ≤ k − 1, in which the bin capacity is k and item sizes are chosen uniformly...
E. G. Coffman, C. Courcoubetis, M. R. Garey, D. S. Johnson, P.W. Shor, ...
We consider the one-dimensional bin packing problem with unit-capacity bins and item sizes chosen according to the discrete uniform distribution Ufj; kg, 1 ! j k; where each item size in f1=k; 2=k; :...
Topics in Probabilistic Verification (2007)
Costas Courcoubetis, R. Alur, D. Dill, M. Yannakakis
Contents 1. Motivation 2. General concepts 3. Examples 4. Part I: discrete time (a) Background: temporal logic, !-automata, probabilistic programs (b) Summary of problems (c) Verifying TL...
G. J. Holzmann, D. Peled, M. Yannakakis
non-progress cycles ([Hol92]) are both incompatible with partial order reduction, such as proposed in [Peled94, HP94]. We have discussed a modi cation of one of the two algorithms that secures...
Perfect packing theorems and the average-case behavior of optimal and online bin packing (2007)
E. G. Coffman, C. Courcoubetis, M. R. Garey, D. S. Johnson, P. W. Shor, R. R. Weber, ...
Abstract. We consider the one-dimensional bin packing problem under the discrete uniform distributions U{j, k}, 1
E. G. Coffman, C. Courcoubetis, M. R. Garey, D. S. Johnson, P. W. Shor, R. R. Weber, ...
We consider the one-dimensional bin packing problem with unit-capacity bins and item sizes chosen according to the discrete uniform distribution Ufj; kg, 1! j k; where each item size in f1=k; 2=k; :...
The complexity of multiterminal cuts (1994)
E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, M. Yannakakis
In the Multiterminal Cut problem we are given an edge-weighted graph and a subset of the vertices called terminals, and asked for a minimum weight set of edges that separates each terminal from all...
The complexity of multiterminal cuts (1994)
E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, M. Yannakakis
In the Multiterminal Cut problem we are given an edge-weighted graph and a subset of the vertices called terminals, and asked for a minimum weight set of edges that separates each terminal from all...
Memory-Efficient Algorithms for the Verification of Temporal Properties (1992)
Courcoubetis Inst Of, C. Courcoubetis, M. Vardi, P. Wolper, M. Yannakakis
This paper addresses the problem of designing memory-efficient algorithms for the verification of temporal properties of finite-state programs. Both the programs and their desired temporal properties...
Memory-Efficient Algorithms for the Verification of Temporal Properties (1992)
Courcoubetis Vardi Wolper, C. Courcoubetis, C. Courcoubetis, M. Vardi, M. Vardi, P. Wolper, ...
This paper addresses the problem of designing memory-efficient algorithms for the verification of temporal properties of finite-state programs. Both the programs and their desired temporal properties...
Timing Verification by Successive Approximation (1992)
R. Alur, A. Itai, R. P. Kurshan, M. Yannakakis
. We present an algorithm for verifying that a model M with timing constraints satisfies a given temporal property T . The model M is given as a parallel composition of !-automata P i , where each...
Memory-efficient algorithms for the verification of temporal properties (1992)
C. Courcoubetis, M. Vardi, P. Wolper, M. Yannakakis, Sart Tilman, Belgium Phone, ...
Address: Universit'e de Li`ege