Solving quantified linear arithmetic by counterexample-guided instantiation

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

We study quantifiers and interpolation properties in ortho- logic, a non-distributive weakening of classical logic that is sound for formula validity with respect to classical logic, yet has a quadratic-time decision procedure. We present a sequent-based p ...

Security system designers favor worst-case security metrics, such as those derived from differential privacy (DP), due to the strong guarantees they provide. On the downside, these guarantees result in a high penalty on the system's performance. In this pa ...

Devices based on the spin as the fundamental computing unit provide a promising beyond-complementary metal-oxide-semiconductor (CMOS) device option, thanks to their energy efficiency and compatibility with CMOS. One such option is a magnetoelectric spin-or ...

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 ...

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 ...

We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms for computing a normal form and deciding the word problem ...

Modelling and analysis of biological systems is crucial in order to quantitatively explain and predict their behaviour. The importance of modelling in systems biology becomes even more evident when tackling complex, large systems. Approaches that rely on ...

In this thesis, we present Stainless, a verification system for an expressive subset of the Scala language. Our system is based on a dependently-typed language and an algorithmic type checking procedure which ensures total correctness. We rely on SMT solve ...

The cellular level of nicotinamide adenine dinucleotide (NAD(+)), through its different functions, affects cellular metabolism and signalling(1-3). A decrease in the NAD(+) content has been associated with various pathologies and physiological aging(4,5), ...

Hydromorphological conditions are a key factor for the habitat diversity in riverine ecosystems. The Hydromorphological Index of Diversity (HMID) is a tool to quantify the habitat diversity in a river reach based on local flow depths and flow velocities. T ...

Logic synthesis is an important part of electronic design automation (EDA) flows, which enable the implementation of digital systems. As the design size and complexity increase, the data structures and algorithms for logic synthesis must adapt and improve ...

Boolean SAT solving can be used to find a minimum- size logic network for a given small Boolean function. This paper extends the SAT formulation to find a minimum-size network under delay constraints. Delay constraints are given in terms of input arrival t ...

Hard-wired carry chains in FPGAs are designed to improve efficiency of important arithmetic primitives. Although they are proven to be effective for arithmetic-rich functions, there are very few studies on the optimization opportunities of carry chains for ...

Manipulating logic functions via majority operators recently drew the attention of researchers in computer science. For example, circuit optimization based on majority operators enables superior results as compared to traditional logic systems. Also, the B ...

We prove that the quantifier-free fragment of the theory of character strings with regular language membership constraints and linear integer constraints over string lengths is decidable. We do that by describing a sound, complete and terminating tableaux ...

A method and device for reducing the computational complexity of a processing algorithm, of a discrete signal, in particular of the spectral estimation and analysis of bio-signals, with minimum or no quality loss, which comprises steps of (a) choosing a do ...

Satisfiability modulo theory solvers are increasingly being used to solve quantified formulas over structures such as integers and term algebras. Quantifier instantiation combined with ground decision procedure alone is insufficient to prove many formulas ...

The various meanings of discourse connectives like while and however are difficult to identify and annotate, even for trained human annotators. This problem is all the more important that connectives are salient textual markers of cohesion and need to be c ...

Solving quantified linear arithmetic by counterexample-guided instantiation

Chat with Graph Search

Interpolation and Quantifiers in Ortholattices

Bayes Security: A Not So Average Metric

Energy Efficient Logic and Memory Design With Beyond-CMOS Magnetoelectric Spin-Orbit (MESO) Technology Toward Ultralow Supply Voltage

Scaling Language Features for Program Verification

NP Satisfiability for Arrays as Powers

Formula Normalizations in Verification

Modelling the Intracellular Environment under Uncertainty, from Post-translational Modification to Metabolic Networks

Verified Functional Programming

A biosensor for measuring NAD(+) levels at the point of care

Analysis of the sensitivity of the hydromorphological index of diversity, HMID

Exploiting Satisfiability Solvers for Efficient Logic Synthesis

Busy Man’s Synthesis: Combinational Delay Optimization With SAT

Improving Circuit Mapping Performance Through MIG-based Synthesis for Carry Chains

A Sound and Complete Axiomatization of Majority-n Logic

A Decision Procedure for Regular Membership and Length Constraints over Unbounded Strings

Method and apparatus for low complexity spectral analysis of bio-signals

Induction for SMT Solvers

Annotating the meaning of discourse connectives by looking at their translation: The translation-spotting technique