CS Paper Radar

Selective Chaining of Parameterised Boolean Equation Systems

Jore J. Booy, Tim A. C. Willemse

cs.LO ·submitted 2026-11-12 13:51 UTC · v1

Abstract

Parameterised Boolean Equations Systems (PBESs) are used to verify properties of formal industrial models. We introduce a technique called selective chaining to simplify these PBESs by unfolding specific predicate variable instances when the unfolding results in a PBES that is likely to be simpler. For determining the latter we propose a set of heuristics. We show the formal correctness of the chaining operator and provide theoretical upper bounds using relevancy graphs on the size of the verification problem after chaining. Lastly, we study the effectiveness of our heuristics, showing that selective chaining can reduce memory usage and yield significant speed-ups solving PBESs that encode model checking problems for complex industrial systems.

Comment
Pre-print for FSEN 2027

Closest papers

Nearest neighbours by meaning across the whole index.

Translating finite-domain integer constraint models to CP/SMT/ILP/PB/SAT solvers with CPMpy

cs.AI ·2026-08-15 ·Tias Guns, Ignace Bleukx, Hendrik Bierlee, Jo Devriendt, Emilio Gamba +6 more
code/data similarity 0.61
Abstract

Constraint solving is a declarative approach for solving combinatorial satisfaction and optimization problems. The user specifies their problem through constraints and decision variables, and a generic solver is used to find a solution. Several constraint-solving technologies exist, and certain solvers perform well on certain problems. Therefore, it is useful to try different solvers given a particular application. However, each solving paradigm supports different types of constraints and decision variables. Our goal is to translate high-level constraint satisfaction and optimization problems into any lower-level formalism, including CP, SMT QF-LIA, ILP, PB and (Max)SAT. This allows for comparing different solving technologies for a particular problem, without requiring a user to manually remodel it for each solving paradigm. We define a high-level language of logical and arithmetic operations, and useful additional functions and constraints, which are known as global constraints in the CP community. We then present a modular framework for transforming our high-level modeling language to CP/SMT/ILP/PB and (Max)SAT solvers. While many transformations are partly described in the literature, we observe that they can be implemented through a modular waterfall of smaller components, where lower-level paradigms reuse the transformations of higher-level paradigms. Two recurring challenges are handling the negation of arbitrary subexpressions and avoiding the introduction of auxiliary variables. Additionally, we take special care linearizing non-linear operators for ILP, PB and SAT-solvers. The transformation waterfall is implemented and evaluated in the open-source CPMpy library. Our results show that constraint models significantly change throughout the transformations, and that optimizations to the linearization of constraints are essential for ILP and PB solvers.

0.20

TRACE: Traversal and Reasoning Algebraic Computing Engine for Formal Hardware Verification

cs.AR ·2026-08-17 ·Jan Kleinekathöfer, Lennart Weingarten, Kamalika Datta, Rolf Drechsler
hot direction similarity 0.60
Abstract

Modern hardware verification of complex circuits relies heavily on the efficiency of formal methods. For complex arithmetic circuits in particular Symbolic Computer Algebra (SCA) engines which represent pseudo-boolean functions using polynomials are crucial. As circuit complexity grows in the age of AI, verification of arithmetic primitives, including Multiplication, Addition, Multiply-Accumulate (MAC), becomes a computational bottleneck. To address this, we introduce TRACE (Traversal and Reasoning Algebraic Computing Engine), a highly efficient framework designed to investigate the intersection of traversal strategies and proof efficiency. Unlike existing SCA tools which are mainly limited to multipliers, TRACE offers a flexible framework for researchers to analyze memory usage and verification time across a wide range of arithmetic circuits (adder, multiplier and MAC). To overcome the state-explosion problem inherent in polynomial expansion, the engine incorporates advanced reduction techniques, including optimized traversal strategies, conflict removal, and polarity-based optimization for compact symbolic representations. Our experimental results show that for optimized MAC, for the first time, TRACE was able to verify previously unverifiable circuits

0.35

Solving QBF with Counterexample Guided Refinement

cs.LO ·2026-08-14 ·Mikoláš Janota, William Klieber, Joao Marques-Silva, Edmund Clarke
top venuehighly cited similarity 0.59
Abstract

We propose two novel approaches for using Counterexample-Guided Abstraction Refinement (CEGAR) in Quantified Boolean Formula (QBF) solvers. The first approach develops a recursive algorithm whose search is driven by CEGAR (rather than by DPLL). The second approach employs CEGAR as an additional learning technique in an existing DPLL-based QBF solver. Experimental evaluation of the implemented prototypes shows that the CEGAR-driven solver outperforms existing solvers on a number of families in the QBF-LIB and that the DPLL solver benefits from the additional type of learning. Thus this article opens two promising avenues in QBF: CEGAR-driven solvers as an alternative to existing approaches and a novel type of learning in DPLL.

0.69

Symbolic Execution of Constrained Horn Clauses

cs.LO cs.PL ·2026-10-02 ·Johannes Weiser, Zafer Esen, Philipp Rümmer
similarity 0.59
Abstract · 34 pages, 8 figures

Constrained Horn clauses (CHCs) are a fragment of first-order logic widely used as an intermediate language for verification. We study constrained resolution as a calculus for reasoning about the satisfiability of sets of CHCs. Constrained resolution forms a simple alternative to model checking algorithms such as CEGAR and IC3 and is here shown to exhibit complementary features. We show that, when CHCs encode programs, forward symbolic execution corresponds to positive unit hyper-resolution, and backward symbolic execution to SLD resolution, which are special cases of constrained resolution. We formalize forward and backward reasoning for linear and non-linear CHCs and transition systems, prove refutational completeness under fair strategies, and develop subsumption criteria for pruning redundant derivations. We moreover show that backward resolution with subsumption generalizes $k$-induction to non-linear CHCs, and that forward constrained resolution is related to the problem of constructing proofs in incorrectness logic. Lastly, we provide an experimental evaluation in the Eldarica CHC solver on benchmarks from CHC-COMP.

0.19

Reasoning with Probabilities: Relating Weighted Model Counting and Probabilistic Model Checking

cs.LO ·2026-08-23 ·Bahare Salmani, Vincent Derkinderen
similarity 0.57
Abstract

Weighted model counting (WMC) and probabilistic model checking (PMC) are two well- established frameworks that are independently developed, the former for probabilistic inference, the latter traditionally for probabilistic verification, though recently also applied to inference. The formal relationship between the two frameworks, however, remains largely unexplored. In this paper, we lay the foundations for how they relate: we present (1) a mapping from cycle- free parametric Markov chains (pMCs) to arithmetic circuits (ACs), enabling the reduction of reachability probability computations in such pMCs to a weighted model counting problem on the corresponding ACs, and (2) a mapping from a subclass of arithmetic circuits -- with probabilistic semantics -- back to parametric Markov chains. We propose a detailed correspondence between the entities of WMC and PMC, and discuss how our mappings enable transferring optimization techniques such as bisimulation minimization across the frameworks.

0.21

Enhancing Word-Level Property Directed Reachability with LLM-Driven Semantic Guidance

cs.AR ·2026-09-24 ·Guangyu Hu, Mingkai Miao, Zhiyuan Yan, Xiaofeng Zhou, Wei Zhang +1 more
code/data similarity 0.56
Abstract · 14 pages, 8 figures

Property Directed Reachability (PDR) is a prominent algorithm for hardware formal verification. However, bit-level PDR often struggles with datapath-heavy designs because bit-blasting obscures high-level semantics. While word-level PDR addresses this by reasoning over bit-vector and array theories, its performance remains bottlenecked by discovering proof-relevant word-level relations. We propose LLM4PDR, a framework leveraging Large Language Models (LLMs) to guide word-level PDR search through three mechanisms: (1) Predicate Generation, extracting state relationships as candidate predicates during inductive generalization; (2) Clause Generation, producing candidate frame lemmas to accelerate convergence after formal validation; and (3) Assertion Generation, synthesizing helper assertions that strengthen the target property under counterexample-guided refinement. We implement LLM4PDR in the Pono model checker and evaluate it on arithmetic micro-benchmarks, HLS-generated pipelines, open-source RTL components, and hardware model checking competition (HWMCC) instances. Results show LLM-generated guidance improves both solved instances and runtime on datapath-heavy and control-plus-datapath designs. The strongest configuration solves 28 of 33 arithmetic benchmarks, compared to 13 for vanilla Pono and 11 for AVR. On HLS pipelines and open-source RTL, different modes provide complementary speedups: clause guidance is effective for deep pipelines and predicate guidance for bus and memory-controller designs. On HWMCC benchmarks, benefits are instance-dependent, demonstrating notable speedups and timeout avoidance on hard cases. These results suggest that LLM-generated, verifier-checked semantic hints can serve as a practical complement to conventional word-level PDR.

0.46

The QBF Gallery 2026

cs.LO ·2026-11-13 ·Cynthia Peyrer, Luca Pulina, Martina Seidl
benchmark similarity 0.55
Abstract · Open access version

The QBF Gallery 2026 is the latest evaluation event of (dependency) quantified Boolean formula (QBF) solving technology. Its goal is to assess the current state-of-the-art, enable the evaluation of novel solvers on newly curated benchmark instances and present the progress made since the previous competition. This report discusses the solvers, instances and tools submitted by the community and introduces new benchmark collections for evaluation. We evaluate solvers in three tracks, reflecting most common input formats in (dependency) QBF solving. In addition to those main evaluations, we investigate effects of preprocessing and include a track of new crafted benchmark families. The results are analyzed using various metrics and complementary statistics on solver similarities, different memory limitations and performance across formula families. Finally, the dedicated benchmarks for each track are made available as an artifact to support future research and reproducible evaluation.

0.46

Solving QBF by Clause Selection

cs.LO ·2026-08-14 ·Mikoláš Janota, Joao Marques-Silva
top venuehighly cited similarity 0.55
Abstract

Algorithms based on the enumeration of implicit hitting sets find a growing number of applications, which include maximum satisfiability and model based diagnosis, among others. This paper exploits enumeration of implicit hitting sets in the context of Quantified Boolean Formulas (QBF). The paper starts by developing a simple algorithm for QBF with two levels of quantification, which is shown to relate with existing work on enumeration of implicit hitting sets, but also with recent work on QBF based on abstraction refinement. The paper then extends these ideas and develops a novel QBF algorithm, which generalizes the concept of enumeration of implicit hitting sets. Experimental results, obtained on representative problem instances, show that the novel algorithm is competitive with, and often outperforms, the state of the art in QBF solving.

0.74