The Experts below are selected from a list of 360 Experts worldwide ranked by ideXlab platform
Cesare Tinelli  One of the best experts on this subject based on the ideXlab platform.

syntax guided quantifier Instantiation
Tools and Algorithms for Construction and Analysis of Systems, 2021CoAuthors: Aina Niemetz, Andrew Reynolds, Clark Barrett, Mathias Preiner, Cesare TinelliAbstract:This paper presents a novel approach for quantifier Instantiation in Satisfiability Modulo Theories (SMT) that leverages syntaxguided synthesis (SyGuS) to choose Instantiation terms. It targets quantified constraints over background theories such as (non)linear integer, reals and floatingpoint arithmetic, bitvectors, and their combinations. Unlike previous approaches for quantifier Instantiation in these domains which rely on theoryspecific strategies, the new approach can be applied to any (combined) theory, when provided with a grammar for Instantiation terms for all sorts in the theory. We implement syntaxguided Instantiation in the SMT solver CVC4, leveraging its support for enumerative SyGuS. Our experiments demonstrate the versatility of the approach, showing that it is competitive with or exceeds the performance of stateoftheart solvers on a range of background theories.

On solving quantified bitvector constraints using invertibility conditions
Formal Methods in System Design, 2021CoAuthors: Aina Niemetz, Andrew Reynolds, Clark Barrett, Mathias Preiner, Cesare TinelliAbstract:We present a novel approach for solving quantified bitvector constraints in Satisfiability Modulo Theories (SMT) based on computing symbolic inverses of bitvector operators. We derive conditions that precisely characterize when bitvector constraints are invertible for a representative set of bitvector operators commonly supported by SMT solvers. We utilize syntaxguided synthesis techniques to aid in establishing these conditions and verify them independently by using several SMT solvers. We show that invertibility conditions can be embedded into quantifier Instantiations using Hilbert choice expressions and give experimental evidence that a counterexampleguided approach for quantifier Instantiation utilizing these techniques leads to performance improvements with respect to stateoftheart solvers for quantified bitvector constraints.

On Solving Quantified BitVectors using Invertibility Conditions.
arXiv: Logic in Computer Science, 2018CoAuthors: Aina Niemetz, Andrew Reynolds, Clark Barrett, Mathias Preiner, Cesare TinelliAbstract:We present a novel approach for solving quantified bitvector formulas in Satisfiability Modulo Theories (SMT) based on computing symbolic inverses of bitvector operators. We derive conditions that precisely characterize when bitvector constraints are invertible for a representative set of bitvector operators commonly supported by SMT solvers. We utilize syntaxguided synthesis techniques to aid in establishing these conditions and verify them independently by using several SMT solvers. We show that invertibility conditions can be embedded into quantifier Instantiations using Hilbert choice expressions, and give experimental evidence that a counterexampleguided approach for quantifier Instantiation utilizing these techniques leads to performance improvements with respect to stateoftheart solvers for quantified bitvector constraints.

quantifier Instantiation techniques for finite model finding in smt
Conference on Automated Deduction, 2013CoAuthors: Andrew Reynolds, Cesare Tinelli, Amit Goel, Sava Krstic, Morgan Deters, Clark BarrettAbstract:SMTbased applications increasingly rely on SMT solvers being able to deal with quantified formulas. Current work shows that for formulas with quantifiers over uninterpreted sorts countermodels can be obtained by integrating a finite model finding capability into the architecture of a modern SMT solver. We examine various strategies for ondemand quantifier Instantiation in this setting. Here, completeness can be achieved by considering all ground instances over the finite domain of each quantifier. However, exhaustive Instantiation quickly becomes unfeasible with larger domain sizes. We propose Instantiation strategies to identify and consider only a selection of ground instances that suffices to determine the satisfiability of the input formula. We also examine heuristic quantifier Instantiation techniques such as Ematching for the purpose of accelerating the search. We give experimental evidence that our approach is practical for use in industrial applications and is competitive with other approaches.

Instantiation based invariant discovery
NASA Formal Methods, 2011CoAuthors: Temesghen Kahsai, Cesare TinelliAbstract:We present a general scheme for automated Instantiationbased invariant discovery. Given a transition system, the scheme produces kinductive invariants from templates representing decidable predicates over the system's data types. The proposed scheme relies on efficient reasoning engines such as SAT and SMT solvers, and capitalizes on their ability to quickly generate countermodels of noninvariant conjectures. We discuss in detail two practical specializations of the general scheme in which templates represent partial orders. Our experimental results show that both specializations are able to quickly produce invariants from a variety of synchronous systems which prove quite useful in proving safety properties for these systems.
Stefan Schneider  One of the best experts on this subject based on the ideXlab platform.

on the fine grained complexity of one dimensional dynamic programming
arXiv: Computational Complexity, 2017CoAuthors: Marvin Kunnemann, Ramamohan Paturi, Stefan SchneiderAbstract:In this paper, we investigate the complexity of onedimensional dynamic programming, or more specifically, of the LeastWeight Subsequence (LWS) problem: Given a sequence of $n$ data items together with weights for every pair of the items, the task is to determine a subsequence $S$ minimizing the total weight of the pairs adjacent in $S$. A large number of natural problems can be formulated as LWS problems, yielding obvious $O(n^2)$time solutions. In many interesting instances, the $O(n^2)$many weights can be succinctly represented. Yet except for nearlinear time algorithms for some specific special cases, little is known about when an LWS Instantiation admits a subquadratictime algorithm and when it does not. In particular, no lower bounds for LWS Instantiations have been known before. In an attempt to remedy this situation, we provide a general approach to study the finegrained complexity of succinct Instantiations of the LWS problem. In particular, given an LWS Instantiation we identify a highly parallel core problem that is subquadratically equivalent. This provides either an explanation for the apparent hardness of the problem or an avenue to find improved algorithms as the case may be. More specifically, we prove subquadratic equivalences between the following pairs (an LWS Instantiation and the corresponding core problem) of problems: a lowrank version of LWS and minimum inner product, finding the longest chain of nested boxes and vector domination, and a coin change problem which is closely related to the knapsack problem and (min,+)convolution. Using these equivalences and known SETHhardness results for some of the core problems, we deduce tight conditional lower bounds for the corresponding LWS Instantiations. We also establish the (min,+)convolutionhardness of the knapsack problem.

on the fine grained complexity of one dimensional dynamic programming
International Colloquium on Automata Languages and Programming, 2017CoAuthors: Marvin Kunnemann, Ramamohan Paturi, Stefan SchneiderAbstract:In this paper, we investigate the complexity of onedimensional dynamic programming, or more specifically, of the LeastWeight Subsequence (LWS) problem: Given a sequence of n data items together with weights for every pair of the items, the task is to determine a subsequence S minimizing the total weight of the pairs adjacent in S. A large number of natural problems can be formulated as LWS problems, yielding obvious O(n^2)time solutions. In many interesting instances, the O(n^2)many weights can be succinctly represented. Yet except for nearlinear time algorithms for some specific special cases, little is known about when an LWS Instantiation admits a subquadratictime algorithm and when it does not. In particular, no lower bounds for LWS Instantiations have been known before. In an attempt to remedy this situation, we provide a general approach to study the finegrained complexity of succinct Instantiations of the LWS problem: Given an LWS Instantiation we identify a highly parallel core problem that is subquadratically equivalent. This provides either an explanation for the apparent hardness of the problem or an avenue to find improved algorithms as the case may be. More specifically, we prove subquadratic equivalences between the following pairs (an LWS Instantiation and the corresponding core problem) of problems: a lowrank version of LWS and minimum inner product, finding the longest chain of nested boxes and vector domination, and a coin change problem which is closely related to the knapsack problem and (min,+)convolution. Using these equivalences and known SETHhardness results for some of the core problems, we deduce tight conditional lower bounds for the corresponding LWS Instantiations. We also establish the (min,+)convolutionhardness of the knapsack problem. Furthermore, we revisit some of the LWS Instantiations which are known to be solvable in nearlinear time and explain their easiness in terms of the easiness of the corresponding core problems.
Andrew Reynolds  One of the best experts on this subject based on the ideXlab platform.

syntax guided quantifier Instantiation
Tools and Algorithms for Construction and Analysis of Systems, 2021CoAuthors: Aina Niemetz, Andrew Reynolds, Clark Barrett, Mathias Preiner, Cesare TinelliAbstract:This paper presents a novel approach for quantifier Instantiation in Satisfiability Modulo Theories (SMT) that leverages syntaxguided synthesis (SyGuS) to choose Instantiation terms. It targets quantified constraints over background theories such as (non)linear integer, reals and floatingpoint arithmetic, bitvectors, and their combinations. Unlike previous approaches for quantifier Instantiation in these domains which rely on theoryspecific strategies, the new approach can be applied to any (combined) theory, when provided with a grammar for Instantiation terms for all sorts in the theory. We implement syntaxguided Instantiation in the SMT solver CVC4, leveraging its support for enumerative SyGuS. Our experiments demonstrate the versatility of the approach, showing that it is competitive with or exceeds the performance of stateoftheart solvers on a range of background theories.

On solving quantified bitvector constraints using invertibility conditions
Formal Methods in System Design, 2021CoAuthors: Aina Niemetz, Andrew Reynolds, Clark Barrett, Mathias Preiner, Cesare TinelliAbstract:We present a novel approach for solving quantified bitvector constraints in Satisfiability Modulo Theories (SMT) based on computing symbolic inverses of bitvector operators. We derive conditions that precisely characterize when bitvector constraints are invertible for a representative set of bitvector operators commonly supported by SMT solvers. We utilize syntaxguided synthesis techniques to aid in establishing these conditions and verify them independently by using several SMT solvers. We show that invertibility conditions can be embedded into quantifier Instantiations using Hilbert choice expressions and give experimental evidence that a counterexampleguided approach for quantifier Instantiation utilizing these techniques leads to performance improvements with respect to stateoftheart solvers for quantified bitvector constraints.

revisiting enumerative Instantiation
Tools and Algorithms for Construction and Analysis of Systems, 2018CoAuthors: Andrew Reynolds, Haniel Barbosa, Pascal FontaineAbstract:Formal methods applications often rely on SMT solvers to automatically discharge proof obligations. SMT solvers handle quantified formulas using incomplete heuristic techniques like Ematching, and often resort to modelbased quantifier Instantiation (MBQI) when these techniques fail. This paper revisits enumerative Instantiation, a technique that considers Instantiations based on exhaustive enumeration of ground terms. Although simple, we argue that enumerative Instantiation can supplement other Instantiation techniques and be a viable alternative to MBQI for valid proof obligations. We first present a stronger Herbrand Theorem, better suited as a basis for the Instantiation loop used in SMT solvers; it furthermore requires considering less instances than classical Herbrand Instantiation. Based on this result, we present different strategies for combining enumerative Instantiation with other Instantiation techniques in an effective way. The experimental evaluation shows that the implementation of these new techniques in the SMT solver CVC4 leads to significant improvements in several benchmark libraries, including many stemming from verification efforts.

On Solving Quantified BitVectors using Invertibility Conditions.
arXiv: Logic in Computer Science, 2018CoAuthors: Aina Niemetz, Andrew Reynolds, Clark Barrett, Mathias Preiner, Cesare TinelliAbstract:We present a novel approach for solving quantified bitvector formulas in Satisfiability Modulo Theories (SMT) based on computing symbolic inverses of bitvector operators. We derive conditions that precisely characterize when bitvector constraints are invertible for a representative set of bitvector operators commonly supported by SMT solvers. We utilize syntaxguided synthesis techniques to aid in establishing these conditions and verify them independently by using several SMT solvers. We show that invertibility conditions can be embedded into quantifier Instantiations using Hilbert choice expressions, and give experimental evidence that a counterexampleguided approach for quantifier Instantiation utilizing these techniques leads to performance improvements with respect to stateoftheart solvers for quantified bitvector constraints.

Revisiting Enumerative Instantiation  Artifact
2018CoAuthors: Andrew Reynolds, Haniel Barbosa, Pascal FontaineAbstract:This artifact contains the binaries of the SMT solvers CVC4 and Z3, the benchmarks on which they were evaluated, and the running scripts for each configuration evaluated. An overview of the results obtained from this evaluation in the StarExec cluster is presented in Section 5 of the TACAS 2018 proceedings paper:Revisiting Enumerative InstantiationAndrew Reynolds, Haniel Barbosa, and Pascal Fontaine24th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2018). Thessaloniki, Grécia.The related paper presents a strengthened version of the Herbrand theorem, designed as an bettersuited basis for the Instantiation loop used in SMT solvers. The experimental evaluation code employs different strategies of effectively combining enumerative Instantiation with other Instantiation techniques.The subdirectory benchmarks contains a bash shell script (.sh) to be used in conjunction with the TPTP benchmarks accessible via http://www.cs.miami.edu/~tptp/TPTP/Distribution/TPTPv7.0.0.tgz see readme.txt for more detailed instructions on how to use the artifact.The subdirectory solvers contains archived CVC4 and Z3 solvers; corresponding to the experimental evaluation of different enumerative Instantiation strategies. All results were produced on StarExec, a public execution service for running comparative evaluations of solvers, with a timeout of 300 seconds.All files are in openlyaccessible text format holding bash shell scripts or documentation such as READMEs.
Aina Niemetz  One of the best experts on this subject based on the ideXlab platform.

syntax guided quantifier Instantiation
Tools and Algorithms for Construction and Analysis of Systems, 2021CoAuthors: Aina Niemetz, Andrew Reynolds, Clark Barrett, Mathias Preiner, Cesare TinelliAbstract:This paper presents a novel approach for quantifier Instantiation in Satisfiability Modulo Theories (SMT) that leverages syntaxguided synthesis (SyGuS) to choose Instantiation terms. It targets quantified constraints over background theories such as (non)linear integer, reals and floatingpoint arithmetic, bitvectors, and their combinations. Unlike previous approaches for quantifier Instantiation in these domains which rely on theoryspecific strategies, the new approach can be applied to any (combined) theory, when provided with a grammar for Instantiation terms for all sorts in the theory. We implement syntaxguided Instantiation in the SMT solver CVC4, leveraging its support for enumerative SyGuS. Our experiments demonstrate the versatility of the approach, showing that it is competitive with or exceeds the performance of stateoftheart solvers on a range of background theories.

On solving quantified bitvector constraints using invertibility conditions
Formal Methods in System Design, 2021CoAuthors: Aina Niemetz, Andrew Reynolds, Clark Barrett, Mathias Preiner, Cesare TinelliAbstract:We present a novel approach for solving quantified bitvector constraints in Satisfiability Modulo Theories (SMT) based on computing symbolic inverses of bitvector operators. We derive conditions that precisely characterize when bitvector constraints are invertible for a representative set of bitvector operators commonly supported by SMT solvers. We utilize syntaxguided synthesis techniques to aid in establishing these conditions and verify them independently by using several SMT solvers. We show that invertibility conditions can be embedded into quantifier Instantiations using Hilbert choice expressions and give experimental evidence that a counterexampleguided approach for quantifier Instantiation utilizing these techniques leads to performance improvements with respect to stateoftheart solvers for quantified bitvector constraints.

On Solving Quantified BitVectors using Invertibility Conditions.
arXiv: Logic in Computer Science, 2018CoAuthors: Aina Niemetz, Andrew Reynolds, Clark Barrett, Mathias Preiner, Cesare TinelliAbstract:We present a novel approach for solving quantified bitvector formulas in Satisfiability Modulo Theories (SMT) based on computing symbolic inverses of bitvector operators. We derive conditions that precisely characterize when bitvector constraints are invertible for a representative set of bitvector operators commonly supported by SMT solvers. We utilize syntaxguided synthesis techniques to aid in establishing these conditions and verify them independently by using several SMT solvers. We show that invertibility conditions can be embedded into quantifier Instantiations using Hilbert choice expressions, and give experimental evidence that a counterexampleguided approach for quantifier Instantiation utilizing these techniques leads to performance improvements with respect to stateoftheart solvers for quantified bitvector constraints.

counterexample guided model synthesis
Tools and Algorithms for Construction and Analysis of Systems, 2017CoAuthors: Mathias Preiner, Aina Niemetz, Armin BiereAbstract:In this paper we present a new approach for solving quantified formulas in Satisfiability Modulo Theories (SMT), with a particular focus on the theory of fixedsize bitvectors. We combine counterexampleguided quantifier Instantiation with a syntaxguided synthesis approach, which allows us to synthesize both Skolem functions and terms for quantifier Instantiations. Our approach employs two ground theory solvers to reason about quantified formulas. It neither relies on quantifier specific simplifications nor heuristic quantifier Instantiation techniques, which makes it a simple yet effective approach for solving quantified formulas. We implemented our approach in our SMT solver Boolector and show in our experiments that our techniques are competitive compared to the stateoftheart in solving quantified bitvectors.
Marvin Kunnemann  One of the best experts on this subject based on the ideXlab platform.

on the fine grained complexity of one dimensional dynamic programming
arXiv: Computational Complexity, 2017CoAuthors: Marvin Kunnemann, Ramamohan Paturi, Stefan SchneiderAbstract:In this paper, we investigate the complexity of onedimensional dynamic programming, or more specifically, of the LeastWeight Subsequence (LWS) problem: Given a sequence of $n$ data items together with weights for every pair of the items, the task is to determine a subsequence $S$ minimizing the total weight of the pairs adjacent in $S$. A large number of natural problems can be formulated as LWS problems, yielding obvious $O(n^2)$time solutions. In many interesting instances, the $O(n^2)$many weights can be succinctly represented. Yet except for nearlinear time algorithms for some specific special cases, little is known about when an LWS Instantiation admits a subquadratictime algorithm and when it does not. In particular, no lower bounds for LWS Instantiations have been known before. In an attempt to remedy this situation, we provide a general approach to study the finegrained complexity of succinct Instantiations of the LWS problem. In particular, given an LWS Instantiation we identify a highly parallel core problem that is subquadratically equivalent. This provides either an explanation for the apparent hardness of the problem or an avenue to find improved algorithms as the case may be. More specifically, we prove subquadratic equivalences between the following pairs (an LWS Instantiation and the corresponding core problem) of problems: a lowrank version of LWS and minimum inner product, finding the longest chain of nested boxes and vector domination, and a coin change problem which is closely related to the knapsack problem and (min,+)convolution. Using these equivalences and known SETHhardness results for some of the core problems, we deduce tight conditional lower bounds for the corresponding LWS Instantiations. We also establish the (min,+)convolutionhardness of the knapsack problem.

on the fine grained complexity of one dimensional dynamic programming
International Colloquium on Automata Languages and Programming, 2017CoAuthors: Marvin Kunnemann, Ramamohan Paturi, Stefan SchneiderAbstract:In this paper, we investigate the complexity of onedimensional dynamic programming, or more specifically, of the LeastWeight Subsequence (LWS) problem: Given a sequence of n data items together with weights for every pair of the items, the task is to determine a subsequence S minimizing the total weight of the pairs adjacent in S. A large number of natural problems can be formulated as LWS problems, yielding obvious O(n^2)time solutions. In many interesting instances, the O(n^2)many weights can be succinctly represented. Yet except for nearlinear time algorithms for some specific special cases, little is known about when an LWS Instantiation admits a subquadratictime algorithm and when it does not. In particular, no lower bounds for LWS Instantiations have been known before. In an attempt to remedy this situation, we provide a general approach to study the finegrained complexity of succinct Instantiations of the LWS problem: Given an LWS Instantiation we identify a highly parallel core problem that is subquadratically equivalent. This provides either an explanation for the apparent hardness of the problem or an avenue to find improved algorithms as the case may be. More specifically, we prove subquadratic equivalences between the following pairs (an LWS Instantiation and the corresponding core problem) of problems: a lowrank version of LWS and minimum inner product, finding the longest chain of nested boxes and vector domination, and a coin change problem which is closely related to the knapsack problem and (min,+)convolution. Using these equivalences and known SETHhardness results for some of the core problems, we deduce tight conditional lower bounds for the corresponding LWS Instantiations. We also establish the (min,+)convolutionhardness of the knapsack problem. Furthermore, we revisit some of the LWS Instantiations which are known to be solvable in nearlinear time and explain their easiness in terms of the easiness of the corresponding core problems.