The Experts below are selected from a list of 4695 Experts worldwide ranked by ideXlab platform
David Monniaux - One of the best experts on this subject based on the ideXlab platform.
-
Quantifier Elimination by lazy model enumeration
Computer Aided Verification, 2010Co-Authors: David MonniauxAbstract:We propose a Quantifier Elimination scheme based on nested lazy model enumeration through SMT-solving, and projections This scheme may be applied to any logic that fulfills certain conditions; we illustrate it for linear real arithmetic The Quantifier Elimination problem for linear real arithmetic is doubly exponential in the worst case, and so is our method We have implemented it and benchmarked it against other methods from the literature.
-
CAV - Quantifier Elimination by lazy model enumeration
Computer Aided Verification, 2010Co-Authors: David MonniauxAbstract:We propose a Quantifier Elimination scheme based on nested lazy model enumeration through SMT-solving, and projections This scheme may be applied to any logic that fulfills certain conditions; we illustrate it for linear real arithmetic The Quantifier Elimination problem for linear real arithmetic is doubly exponential in the worst case, and so is our method We have implemented it and benchmarked it against other methods from the literature.
-
a Quantifier Elimination algorithm for linear real arithmetic
International Conference on Logic Programming, 2008Co-Authors: David MonniauxAbstract:We propose a new Quantifier Elimination algorithm for the theory of linear real arithmetic. This algorithm uses as subroutines satisfiability modulo this theory and polyhedral projection; there are good algorithms and implementations for both of these. The Quantifier Elimination algorithm presented in the paper is compared, on examples arising from program analysis problems and on random examples, to several other implementations, all of which cannot solve some of the examples that our algorithm solves easily.
-
A Quantifier Elimination Algorithm for Linear Real Arithmetic
arXiv: Logic in Computer Science, 2008Co-Authors: David MonniauxAbstract:We propose a new Quantifier Elimination algorithm for the theory of linear real arithmetic. This algorithm uses as subroutine satisfiability modulo this theory, a problem for which there are several implementations available. The Quantifier Elimination algorithm presented in the paper is compared, on examples arising from program analysis problems, to several other implementations, all of which cannot solve some of the examples that our algorithm solves easily.
-
LPAR - A Quantifier Elimination Algorithm for Linear Real Arithmetic
Logic for Programming Artificial Intelligence and Reasoning, 2008Co-Authors: David MonniauxAbstract:We propose a new Quantifier Elimination algorithm for the theory of linear real arithmetic. This algorithm uses as subroutines satisfiability modulo this theory and polyhedral projection; there are good algorithms and implementations for both of these. The Quantifier Elimination algorithm presented in the paper is compared, on examples arising from program analysis problems and on random examples, to several other implementations, all of which cannot solve some of the examples that our algorithm solves easily.
Andy King - One of the best experts on this subject based on the ideXlab platform.
-
Transfer Function Synthesis without Quantifier Elimination
Logical Methods in Computer Science, 2012Co-Authors: Jorg Brauer, Andy KingAbstract:Traditionally, transfer functions have been designed manually for each operation in a program, instruction by instruction. In such a setting, a transfer function describes the semantics of a single instruction, detailing how a given abstract input state is mapped to an abstract output state. The net effect of a sequence of instructions, a basic block, can then be calculated by composing the transfer functions of the constituent instructions. However, precision can be improved by applying a single transfer function that captures the semantics of the block as a whole. Since blocks are program-dependent, this approach necessitates automation. There has thus been growing interest in computing transfer functions automatically, most notably using techniques based on Quantifier Elimination. Although conceptually elegant, Quantifier Elimination inevitably induces a computational bottleneck, which limits the applicability of these methods to small blocks. This paper contributes a method for calculating transfer functions that finesses Quantifier Elimination altogether, and can thus be seen as a response to this problem. The practicality of the method is demonstrated by generating transfer functions for input and output states that are described by linear template constraints, which include intervals and octagons.
-
Transfer Function Synthesis without Quantifier Elimination (long version)
2012Co-Authors: Jorg Brauer, Andy KingAbstract:Traditionally, transfer functions have been designed manually for each operation in a program, instruction by instruction. In such a setting, a transfer function describes the semantics of a single instruction, detailing how a given abstract input state is mapped to an abstract output state. The net effect of a sequence of instructions, a basic block, can then be calculated by composing the transfer functions of the constituent instructions. However, precision can be improved by applying a single transfer function that captures the semantics of the block as a whole. Since blocks are program-dependent, this approach necessitates automation. There has thus been growing interest in computing transfer functions automatically, most notably using techniques based on Quantifier Elimination. Although conceptually elegant, Quantifier Elimination inevitably induces a computational bottleneck, which limits the applicability of these methods to small blocks. This paper contributes a method for calculating transfer functions that finesses Quantifier Elimination altogether, and can thus be seen as a response to this problem. The practicality of the method is demonstrated by generating transfer functions for input and output states that are described by linear template constraints, which include intervals and octagons.
-
ESOP - Transfer function synthesis without Quantifier Elimination
Programming Languages and Systems, 2011Co-Authors: Jorg Brauer, Andy KingAbstract:Recently it has been shown how transfer functions for linear template constraints can be derived for bit-vector programs by operating over propositional Boolean formulae. The drawback of this method is that it relies on existential Quantifier Elimination, which induces a computational bottleneck. The contribution of this paper is a novel method for synthesising transfer functions that does not rely on Quantifier Elimination. We demonstrate the practicality of the method for generating transfer functions for both intervals and octagons.
-
transfer function synthesis without Quantifier Elimination
European Symposium on Programming, 2011Co-Authors: Jorg Brauer, Andy KingAbstract:Recently it has been shown how transfer functions for linear template constraints can be derived for bit-vector programs by operating over propositional Boolean formulae. The drawback of this method is that it relies on existential Quantifier Elimination, which induces a computational bottleneck. The contribution of this paper is a novel method for synthesising transfer functions that does not rely on Quantifier Elimination. We demonstrate the practicality of the method for generating transfer functions for both intervals and octagons.
Thomas Sturm - One of the best experts on this subject based on the ideXlab platform.
-
A Survey of Some Methods for Real Quantifier Elimination, Decision, and Satisfiability and Their Applications
Mathematics in Computer Science, 2017Co-Authors: Thomas SturmAbstract:Effective Quantifier Elimination procedures for first-order theories provide a powerful tool for generically solving a wide range of problems based on logical specifications. In contrast to general first-order provers, Quantifier Elimination procedures are based on a fixed set of admissible logical symbolswith an implicitly fixed semantics. This admits the use of sub-algorithms from symbolic computation. We are going to focus on Quantifier Elimination for the reals and its applications giving examples from geometry, verification, and the life sciences. Beyond Quantifier Elimination we are going to discuss recent results with a subtropical procedure for an existential fragment of the reals. This incomplete decision procedure has been successfully applied to the analysis of reaction systems in chemistry and in the life sciences.
-
verification and synthesis using real Quantifier Elimination
International Symposium on Symbolic and Algebraic Computation, 2011Co-Authors: Thomas Sturm, Ashish TiwariAbstract:We present the application of real Quantifier Elimination to formal verification and synthesis of continuous and switched dynamical systems. Through a series of case studies, we show how first-order formulas over the reals arise when formally analyzing models of complex control systems. Existing off-the-shelf Quantifier Elimination procedures are not successful in eliminating Quantifiers from many of our benchmarks. We therefore automatically combine three established software components: virtual subtitution based Quantifier Elimination in Reduce/Redlog, cylindrical algebraic decomposition implemented in Qepcad, and the simplifier Slfq implemented on top of Qepcad. We use this combination to successfully analyze various models of systems including adaptive cruise control in automobiles, adaptive flight control system, and the classical inverted pendulum problem studied in control theory.
-
ISSAC - Verification and synthesis using real Quantifier Elimination
Proceedings of the 36th international symposium on Symbolic and algebraic computation - ISSAC '11, 2011Co-Authors: Thomas Sturm, Ashish TiwariAbstract:We present the application of real Quantifier Elimination to formal verification and synthesis of continuous and switched dynamical systems. Through a series of case studies, we show how first-order formulas over the reals arise when formally analyzing models of complex control systems. Existing off-the-shelf Quantifier Elimination procedures are not successful in eliminating Quantifiers from many of our benchmarks. We therefore automatically combine three established software components: virtual subtitution based Quantifier Elimination in Reduce/Redlog, cylindrical algebraic decomposition implemented in Qepcad, and the simplifier Slfq implemented on top of Qepcad. We use this combination to successfully analyze various models of systems including adaptive cruise control in automobiles, adaptive flight control system, and the classical inverted pendulum problem studied in control theory.
-
CASC - Effective Quantifier Elimination for Presburger Arithmetic with Infinity
Computer Algebra in Scientific Computing, 2009Co-Authors: Aless Lasaruk, Thomas SturmAbstract:We consider Presburger arithmetic extended by infinity. For this we give an effective Quantifier Elimination and decision procedure which implies also the completeness of our extension. The asymptotic worst-case complexity of our procedure is bounded by a function that is triply exponential in the input word length, which is known to be a tight bound for regular Presburger arithmetic. Possible application areas include Quantifier Elimination and decision procedures for Boolean algebras with cardinality constraints, which have recently moved into the focus of computer science research for software verification, and deductive database queries.
-
Quantifier Elimination in Term Algebras The Case of Finite Languages
2002Co-Authors: Thomas Sturm, Volker WeispfenningAbstract:We give a Quantifier Elimination procedure for term algebras over suitably expanded finite first-order languages. Our expansion is purely functional. Our method works by substituting finitely many parametric test terms. This allows us to obtain in addition sample solutions for an outermost existential Quantifier block. The existence of our method implies that the considered Quantifier Elimination problem and as well the corresponding decision problem are in the fourth Grzegorcyk complexity class. For prenex input formulas with a bounded number of Quantifiers our Quantifier Elimination procedure is elementary recursive. The same applies to arbitrary input formulas in case the language has only constants and unary function symbols. As a corollary we get corresponding upper bounds for the decision problem for term algebras.
Ashish Tiwari - One of the best experts on this subject based on the ideXlab platform.
-
verification and synthesis using real Quantifier Elimination
International Symposium on Symbolic and Algebraic Computation, 2011Co-Authors: Thomas Sturm, Ashish TiwariAbstract:We present the application of real Quantifier Elimination to formal verification and synthesis of continuous and switched dynamical systems. Through a series of case studies, we show how first-order formulas over the reals arise when formally analyzing models of complex control systems. Existing off-the-shelf Quantifier Elimination procedures are not successful in eliminating Quantifiers from many of our benchmarks. We therefore automatically combine three established software components: virtual subtitution based Quantifier Elimination in Reduce/Redlog, cylindrical algebraic decomposition implemented in Qepcad, and the simplifier Slfq implemented on top of Qepcad. We use this combination to successfully analyze various models of systems including adaptive cruise control in automobiles, adaptive flight control system, and the classical inverted pendulum problem studied in control theory.
-
ISSAC - Verification and synthesis using real Quantifier Elimination
Proceedings of the 36th international symposium on Symbolic and algebraic computation - ISSAC '11, 2011Co-Authors: Thomas Sturm, Ashish TiwariAbstract:We present the application of real Quantifier Elimination to formal verification and synthesis of continuous and switched dynamical systems. Through a series of case studies, we show how first-order formulas over the reals arise when formally analyzing models of complex control systems. Existing off-the-shelf Quantifier Elimination procedures are not successful in eliminating Quantifiers from many of our benchmarks. We therefore automatically combine three established software components: virtual subtitution based Quantifier Elimination in Reduce/Redlog, cylindrical algebraic decomposition implemented in Qepcad, and the simplifier Slfq implemented on top of Qepcad. We use this combination to successfully analyze various models of systems including adaptive cruise control in automobiles, adaptive flight control system, and the classical inverted pendulum problem studied in control theory.
Markus N Rabe - One of the best experts on this subject based on the ideXlab platform.
-
incremental determinization for Quantifier Elimination and functional synthesis
Computer Aided Verification, 2019Co-Authors: Markus N RabeAbstract:Quantifier Elimination and its cousin functional synthesis are fundamental problems in automated reasoning that could be used in many applications of formal methods. But, effective algorithms are still elusive. In this paper, we suggest a simple modification to a QBF algorithm to adapt it for Quantifier Elimination and functional synthesis. We demonstrate that the approach significantly outperforms previous algorithms for functional synthesis.
-
CAV (2) - Incremental Determinization for Quantifier Elimination and Functional Synthesis
Computer Aided Verification, 2019Co-Authors: Markus N RabeAbstract:Quantifier Elimination and its cousin functional synthesis are fundamental problems in automated reasoning that could be used in many applications of formal methods. But, effective algorithms are still elusive. In this paper, we suggest a simple modification to a QBF algorithm to adapt it for Quantifier Elimination and functional synthesis. We demonstrate that the approach significantly outperforms previous algorithms for functional synthesis.
