Publication
On Satisfiability for Quantified Formulas in Instantiation-Based Procedures
Related publications (35)
Orthologic with Axioms
We study the proof theory and algorithms for orthologic, a logical system based on ortholattices, which have shown practical relevance in simplification and normalization of verification conditions. Ortholattices weaken Boolean algebras while having po ...
The Complexity of Checking Non-Emptiness in Symbolic Tree Automata
We study the satisfiability problem of symbolic tree automata and decompose it into the satisfiability problem of the existential first-order theory of the input characters and the existential monadic second-order theory of the indices of the accepted word ...
2023LISA – A Modern Proof System
Viktor Kuncak, Simon Guilloud, Sankalp Gambhir
We present LISA, a proof system and proof assistant for constructing proofs in schematic first-order logic and axiomatic set theory. The logical kernel of the system is a proof checker for first-order logic with equality and schematic predicate and fun ...
2023The Complexity of Satisfiability Checking for Symbolic Finite Automata
We study the satisfiability problem of symbolic finite automata and decompose it into the satisfiability problem of the theory of the input characters and the monadic second-order theory of the indices of accepted words. We use our decomposition to obtain ...
2023Decision Procedures for Power Structures
We study the decision problem for the existential fragment of the theory of power structures. We prove complexity results that parallel the decidability results of Feferman-Vaught for the theories of product structures thereby showing that the construction ...
EPFL2023Scaling Language Features for Program Verification
Formal verification of real-world software systems remains challenging for a number of reasons, including lack of automation, friction in specifying properties, and limited support for the diverse programming paradigms used in industry. In this thesis we m ...
EPFL2022NP Satisfiability for Arrays as Powers
We show that the satisfiability problem for the quantifier-free theory of product structures with the equicardinality relation is inNP. As an application, we extend the combinatory array logic fragmentto handle cardinality constraints. The resulting fragme ...
Springer, Cham2022Refutation-based synthesis in SMT
Viktor Kuncak, Andrew Joseph Reynolds
We introduce the first program synthesis engine implemented inside an SMT solver. We present an approach that extracts solution functions from unsatisfiability proofs of the negated form of synthesis conjectures. We also discuss novel counterexample-guided ...
SPRINGER2019Satisfiability-Based Methods for Digital Circuit Design, Debug, and Optimization
Designing digital circuits well is notoriously difficult. This difficulty stems in part from the very
many degrees of freedom inherent in circuit design, typically coupled with the need to satisfy
various constraints. In this thesis, we demonstrate how for ...
EPFL2018Canonical Computation without Canonical Representation
Mathias Soeken, Luca Gaetano Amarù, Ana Petkovska
A representation of a Boolean function is canonical if, given a variable order, only one instance of the representation is possible for the function. A computation is canonical if the result depends only on the Boolean function and a variable order, and do ...
IEEE2018