Journal of Automated Reasoning
Publisher: Springer Nature · ISSN 0168-7433,1573-0670 · 53 articles
- A Polynomial Approach to Evidence: Algorithmic-Algebraic Methods for $$\textsf{FDE}$$ and $$\mathsf {LET_F}$$
-
Automatic Data Dependence Analysis by Deductive Verification
Abstract Parallelization of programs is of essence in the high-performance computing (HPC) area. But parallelization is only correct if certain data dependences can be reliably excluded, for example, read-after-write dependences, where...
- A Formalization of the Ionescu-Tulcea Theorem in Mathlib
-
A Continuation-Based Solution of the Linearity Challenge
Abstract The formalisation of session calculi is made difficult by the management of session channels, which are linear resources that cannot be discarded or duplicated and whose type changes over time, as input/output operations are...
-
Formally Verified Matching of Regular Expressions
Abstract We demonstrate the benefit of computer assisted reasoning by proving correctness of some matching algorithms for regular expressions. We give a brief survey of the system used for verification, illustrate the problem, discuss...
-
Formalizing Multi-graded Brenner–Schröer Proj Schemes and Dilatations of Rings in Lean4
Abstract We present a formalization in Lean4 of some multi-graded algebraic geometry constructions, focusing on the Brenner–Schröer Proj construction and algebraic dilatations of rings. Multi-graded Proj schemes, defined from rings...
- A Rocq Prover STL Formalization with Transformations for Mission Planning
-
Proving Total Correctness of Top-Down Solvers with Widening and Narrowing
Abstract The top-down solver TD is a generic fixpoint algorithm that can be used to compute partial post-solutions of equation systems for abstract interpretation. We consider two extensions of the TD to deal with infinite strictly...
-
$${SL}^{\lambda }$$: A Scalable Algorithm for Register Automata Learning
Abstract Existing active automata learning (AAL) algorithms have demonstrated their potential in capturing the behavior of complex systems (e.g., in analyzing network protocol implementations). The most widely used AAL algorithms...
- Geometric Interpretation and Application of Non-degenerate Conditions in Geometric Theorem Proving
-
The Relative Strength of #SAT Proof Systems
Abstract The propositional model counting problem #SAT asks to compute the number of satisfying assignments for a given propositional formula. Recently, three #SAT proof systems $$\textsf{kcps}$$ kcps (knowledge compilation proof...
-
Probabilistic Automaton Classifier Applied to Examples Related to the Andrews-Curtis Conjecture
Abstract The unsolved Andrews-Curtis conjecture in group theory gives rise to many famously challenging theorem-proving problems. Automated reasoning is one of the best state-of-the-art approaches to solving them. We have developed a...
-
Typed Compositional Quantum Computation with Lenses
Abstract We propose a type-theoretic framework for describing and proving properties of quantum computations, in particular those presented as quantum circuits. Our proposal is based on an observation that, in the polymorphic type...
- YALLA: Yet Another Deep Embedding of Linear Logic in Rocq
-
Verified Tableaux: from Modal Logics to Modal Fixpoint Logics
Abstract We formalise tableau procedures for the modal logics K, KT, and S4, and the modal fixpoint logic LTL, in the proof assistant Coq version 8.17.1. This involves encoding the algorithms, and formally proving their termination and...
- The Rewster: Type Preserving Rewrite Rules for the Rocq Prover
-
Targeting Completeness: Automated Complexity Analysis of Integer Programs
Abstract There exist several approaches to infer runtime or resource bounds for integer programs automatically. In this paper, we study the subclass of periodic rational solvable loops (prs-loops) , where questions regarding the runtime...
- Applying Saturation-Based Theorem Proving to Open Problems in Positive Implicational Logic
- Feature Necessity and Relevancy in Machine Learning Explanations
-
Unsatisfiability-based Algorithms for Multi-Objective Combinatorial Optimization
Abstract In the last decade, numerous algorithms for single-objective Boolean optimization have been proposed that rely on the iterative usage of a highly effective Propositional Satisfiability (SAT) solver. But the use of SAT solvers...
-
A Formal Correctness Proof of Edmonds’ Blossom Shrinking Algorithm
Abstract We present the first formal correctness proof of Edmonds’ blossom shrinking algorithm for maximum cardinality matching in general graphs. We focus on formalising the mathematical structures and properties that allow the...
-
Combining Combination Properties, Part I: Nelson-Oppen and Politeness
Abstract This is the first part of an analysis of the interplay between multiple properties that are related to combination methodologies for theories in the field of satisfiability modulo theories. We here focus on Nelson-Oppen and...
-
Candle: A Verified Implementation of HOL Light (Extended Version)
Abstract This paper presents a fully verified interactive theorem prover for higher-order logic, more specifically: a fully verified clone of HOL Light. Our verification proof of this new system results in an end-to-end correctness...
-
Relative Security: (Dis)Proving Resilience Against Semantic Optimization Vulnerabilities in Isabelle/HOL
Abstract Meltdown and Spectre are vulnerabilities known as transient execution vulnerabilities, where an attacker exploits speculative execution (a semantic optimization present in most modern processors) to break confidentiality. We...
-
Runtime vs. Extracted Proof Size: An Exponential Gap for CDCL on QBFs
Abstract Conflict-driven clause learning (CDCL) is the dominating algorithmic paradigm for SAT solving and hugely successful in practice. In its lifted version QCDCL, it is one of the main approaches for solving quantified Boolean...
- Theorem Proving as Constraint Solving for Coherent Logic with Function Symbols
- Formalization of Convergence Rates of Four First-order Algorithms for Convex Optimization
- A simple proof of correctness of folding the regular heptagon
-
First-order Hybrid Separation Logic
Abstract The basic set-theoretic interpretation of the separating connectives of first-order separation logic allows for an effective, sound and complete axiomatization in a hybrid extension.
-
Reasoning About Incompletely Defined Programs
Abstract We consider automated reasoning about recursively defined partial functions with decidable domain, i.e. functions computed by incompletely defined (or underspecified) but terminating functional programs. We define an...