MOOC
Parallel programming
Related publications (100)
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 ...
Scalable Logic Rewriting Using Don’t Cares
Giovanni De Micheli, Alessandro Tempia Calvino
Logic rewriting is a powerful optimization technique that replaces small sections of a Boolean network with better implementations. Typically, exact synthesis is used to compute optimum replacement on-the-fly, with possible support for Boolean don't cares. ...
2024Interpolation 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 ...
Cham2024Interpolation 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 ...
2024The 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 ...
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 ...
EPFL2023On Polynomial Algorithms for Normalizing Formulas
Viktor Kuncak, Simon Guilloud, Mario Bucev
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 ...
2022Scaling 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 ...
EPFL2022Equivalence Checking for Orthocomplemented Bisemilattices in Log-Linear Time
We present a quasilinear time algorithm to decide the word problem on a natural algebraic structures we call orthocomplemented bisemilattices, a subtheory of boolean algebra. We use as a base a variation of Hopcroft, Ullman and Aho algorithm for tree isomo ...
Springer2022