Simon Guilloud
EPFL IC IINFCOM LARA
INR 318 (Bâtiment INR)
Station 14
CH-1015 Lausanne
Web site: Web site: https://lara.epfl.ch
Fields of expertise
My main domains of research are proof assistants and algorithms for logic-related problems.
I also have interests in various areas of computer science and mathematics and their applicability in proof systems such as probabilistic proofs, type theory, quantum computing and more.
Current work
My main current work consists in designing and developping the LISA proof assistant (work in progress).I also study applicability of decision procedures and datastructures for lattice-like algebras as partial solutions for propositional logic problems.
Biography
I am a PhD student at EPFL working in the Laboratory of Automated Reasoning and Analysis with Prof. Viktor Kunčak.I have previously completed my Bachelor and Master degree at EPFL and made an internship in quantum computing.
Publications
Infoscience publications
2023
Conference Papers
* LISA – A Modern Proof System
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 function symbols. It implements polynomial-time proof checking and uses the axioms of ortholattices (which implies the irrelevance of the order of conjuncts and disjuncts and additional propositional laws). The kernel supports the notion of theorems (whose proofs are not expanded), as well as definitions of predicate symbols and objects whose unique existence is proven. A domain-specific language enables construction of proofs and development of proof tactics with user-friendly tools and presentation, while remaining within the general-purpose language, Scala. We describe the LISA proof system and illustrate the flavour and the level of abstraction of proofs written in LISA. This includes a proof-generating tactic for propositional tautologies, leveraging the ortholattice properties to reduce the size of proofs. We also present early formalization of set theory in LISA, including Cantor's theorem.
2023-06-30. 14th Conference on Interactive Theorem Proving, Białystok, Poland, 2023, July 31 - August 4, 2023.* Formula Normalizations in Verification
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 for two subtheories of Boolean algebra, giving a sound procedure for propositional logical equivalence that is incomplete in general but complete with respect to a subset of Boolean algebra axioms. We first show a new algorithm to produce a normal form for expressions in the theory of ortholattices (OL) in time O(n^2). We also consider an algorithm, recently presented but never evaluated in practice, producing a normal form for a slightly weaker theory, orthocomplemented bisemilattices (OCBSL), in time O(n log(n)^2). For both algorithms, we present an implementation and show efficiency in two domains. First, we evaluate the algorithms on large propositional expressions, specifically combinatorial circuits from a benchmark suite, as well as on large random formulas. Second, we implement and evaluate the algorithms in the Stainless verifier, a tool for verifying the correctness of Scala programs. We used these algorithms as a basis for a new formula simplifier, which is applied before valid verification conditions are saved into a persistent cache. The results show that normalization substantially increases cache hit ratio in large benchmarks.
2023-06-16. 35th International Conference on Computer Aided Verification, Paris, France.2022
Conference Papers
* Equivalence 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 isomorphism which we combine with a term rewriting system to decide equivalence of two terms. We prove that the rewriting system is terminating and confluent and hence the existence of a normal form, and that our algorithm is computing it. We also discuss applications and present an effective implementation in Scala.
2022. 28th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (ETAPS 2022), Munich, Germany, April 2-7, 2022. p. 196-214. DOI : 10.1007/978-3-030-99527-0_11.