Journal of Automated Reasoning
Publisher: Springer Nature · ISSN 0168-7433,1573-0670 · 53 articles
- LTL Reactive Synthesis with a Few Hints
-
Computing Expected Visiting Times and Stationary Distributions in Markov Chains: Fast and Accurate
Abstract We study the accurate and efficient computation of the expected number of times each state is visited in discrete- and continuous-time Markov chains. To obtain sound accuracy guarantees efficiently, we lift interval iteration,...
-
Structured Monads for Generic First-Order Syntax Metatheory
Abstract Reasoning about substitution remains one of the most tedious and error-prone aspects of formal metatheory. We present Tealeaves, a framework implemented in Coq for developing such infrastructure generically and modularly....
-
Formally Verified Suffix Array Construction
Abstract Suffix arrays are a data structure with numerous real-world applications. They are extensively used in text retrieval and data compression applications, including query suggestion mechanisms in web search, and in bioinformatics...
-
Solving a problem with GeoGebra current possibilities and limits of CAS tools
Abstract In the article we show what a Dynamic Geometry Environment ( DGE ) and Computer Algebra System ( CAS ) software is capable of exploring, computing and proving a geometry problem that is closely related to the well-known...
-
Automated reasoning for proving non-orderability of groups
Abstract We demonstrate how a generic automated theorem prover can be applied to establish the non-orderability of groups. Our approach incorporates various tools such as reasoning from the first principles, positive cones, torsions,...
-
Constructing the Lie Algebra of Smooth Vector Fields on a Lie Group in Isabelle/HOL
Abstract This paper describes a formal theory of smooth vector fields, Lie groups and the Lie algebra of a Lie group in the theorem prover Isabelle. Lie groups are abstract structures that are composable, invertible and differentiable;...
- Double Auctions: Formalization and Automated Checkers
-
Active Learning for SAT Solver Benchmarking
Abstract Benchmarking is crucial for developing new algorithms. This also applies to solvers for the propositional satisfiability (SAT) problem. Benchmark selection is about choosing representative problem instances that reliably...
- Timed Automata Verification and Synthesis Via Finite Automata Learning
-
A Sound and Complete Projection for Global Types
Abstract Multiparty session types is a typing discipline used to write specifications, known as global types, for branching and recursive message-passing systems. A necessary operation on global types is projection to abstractions of...
-
The QSMA Algorithm for Quantifiers in SMT
Abstract Deciding the satisfiability of formulas involving both quantifiers and theory defined symbols is a challenge in automated reasoning. This article presents an algorithm, called $$\textsf{QSMA}$$ QSMA ( Quantified Satisfiability...
-
Producing Proofs of Unsatisfiability with Distributed Clause-Sharing SAT Solvers
Abstract Distributed clause-sharing SAT solvers can solve challenging problems hundreds of times faster than sequential SAT solvers by sharing derived information among multiple sequential solvers. Unlike sequential solvers, however,...
-
A Mechanically Verified Garbage Collector for OCaml
Abstract The OCaml programming language finds application across diverse domains, including systems programming, web development, scientific computing, formal verification, and symbolic mathematics. OCaml is a memory-safe programming...
- A Direct Procedure to Test Entailment in a Separation Logic of Relations
-
A Proof-Producing Compiler for Blockchain Applications
Abstract CairoZero is a programming language for running decentralized applications (dApps) at scale. Programs written in the CairoZero language are compiled to machine code for the Cairo CPU architecture and cryptographic protocols are...
-
Lessons for Interactive Theorem Proving Researchers from a Survey of Coq Users
Abstract The Coq Community Survey 2022 was an online public survey of users of the Coq proof assistant conducted during February 2022. Broadly, the survey asked about use of Coq features, user interfaces, libraries, plugins, and tools,...
-
Fast, Verified Computation for HOL ITPs
Abstract We add an efficient function for computation to the kernels of higher-order logic interactive theorem provers. First, we develop and prove sound our approach for Candle. Candle is a port of HOL Light which has been proved sound...
-
Interpolation and SAT-Based Model Checking Revisited: Adoption to Software Verification
Abstract The article Interpolation and SAT-Based Model Checking (McMillan in: Proc. CAV 2003, LNCS, Springer [56]) describes a formal-verification algorithm, which was originally devised to verify safety properties of finite-state...
- Formalization of the Prime Number Theorem with a Remainder Term
- Satisfiability of Non-linear Transcendental Arithmetic as a Certificate Search Problem
-
Computer-Assisted Proofs for Lyapunov Stability via Sums of Squares Certificates and Constructive Analysis
Abstract We provide a computer-assisted approach to ensure that a given discrete-time polynomial system is (asymptotically) stable. Our framework relies on constructive analysis together with formally certified sums of squares Lyapunov...
-
Use and Abuse of Instance Parameters in the Lean Mathematical Library
Abstract The Lean mathematical library Mathlib features extensive use of the typeclass pattern for organising mathematical structures, based on Lean’s mechanism of instance parameters. Related mechanisms for typeclasses are available in...