Publication

Solving quantified linear arithmetic by counterexample-guided instantiation

Related publications (21)

Interpolation and Quantifiers in Ortholattices

Viktor Kuncak, Simon Guilloud, Sankalp Gambhir

We study quantifiers and interpolation properties in orthologic, 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 pro ...

Springer International Publishing Ag2024

Interpolation and Quantifiers in Ortholattices

Viktor Kuncak, Simon Guilloud, Sankalp Gambhir

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

2024

Decision Procedures for Power Structures

Rodrigo Raya

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

EPFL2023

Bayes Security: A Not So Average Metric

Carmela González Troncoso, Giovanni Cherubin

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

IEEE2023

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

Kyojin Choo

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

Ieee-Inst Electrical Electronics Engineers Inc2023

Scaling Language Features for Program Verification

Georg Stefan Schmid

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

EPFL2022

NP Satisfiability for Arrays as Powers

Viktor Kuncak, Rodrigo Raya

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, Cham2022

Formula Normalizations in Verification

Viktor Kuncak, Mario Bucev, Simon Guilloud, Dragana Milovancevic

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

2023

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

Robin Alexander Denhardt-Eriksson

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

EPFL2021

Verified Functional Programming

Nicolas Charles Yves Voirol

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

EPFL2019

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

Kai Johnsson, Luc Patiny, Elena Katsyuba, Johan Auwerx, Qiuliyang Yu, Lin Xue

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

NATURE PUBLISHING GROUP2019

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

Anton Schleiss, Walter Gostner, Mário Jorge Rodrigues Pereira Da Franca, Christopher Robinson, Severin Stähly

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

2018

Exploiting Satisfiability Solvers for Efficient Logic Synthesis

Ana Petkovska

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

EPFL2017

Busy Man’s Synthesis: Combinational Delay Optimization With SAT

Giovanni De Micheli, Mathias Soeken

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

Ieee2017

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

Paolo Ienne, Giovanni De Micheli, Ana Petkovska, Grace Zgheib, Luca Gaetano Amarù, Xifan Tang, Pierre-Emmanuel Julien Marc Gaillardon, Mathias Soeken, Zhufei Chu

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

ACM2017

A Sound and Complete Axiomatization of Majority-n Logic

Giovanni De Micheli, Luca Gaetano Amarù, Pierre-Emmanuel Julien Marc Gaillardon, Anupam Chattopadhyay

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

Institute of Electrical and Electronics Engineers2016

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

Andrew Joseph Reynolds

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

Springer-Verlag Berlin2015

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

David Atienza Alonso, Srinivasan Murali, Andreas Peter Burg, Aviinaash Sankaranarayanan, Georgios Karakonstantis

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

2015

Induction for SMT Solvers

Viktor Kuncak, Andrew Joseph Reynolds

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

Springer-Verlag2015

Analysis of the CICC Performance Through the Measurement of the Thermal Strain Distribution of the Nb-3 Sn Filaments in the Cable Cross Section

Pierluigi Bruzzone, Ciro Calzolaio

The knowledge of the thermal strain distribution of the Nb3Sn filaments in a cable in conduit conductor (CICC) cross section is a key parameter in understanding the cable performance evolution when it undergoes electromagnetic (EM) cyclic loading. A CICC i ...

IEEE Institute of Electrical and Electronics Engineers2014