CS Paper Radar

Quantifying the Advantage of Coarser DPOR

Minjian Zhang, Rupak Majumdar, Umang Mathur, C. -H. Luke Ong

cs.PL ·submitted 2026-11-13 11:51 UTC · v1
benchmark

Abstract

Dynamic partial-order reduction (DPOR) has emerged as a promising approach to addressing interleaving explosion in bounded model checking of concurrent programs. Given an equivalence relation on interleavings, the model checker explores a program's executions while minimizing repeated visits to the same class; optimal model checkers avoid such repetition altogether. A coarser equivalence promises faster exploration by reducing the number of classes. This has motivated alternatives to Mazurkiewicz's trace equivalence such as reads-from and reads-value-from equivalence. This promise, however, does not always materialize in practice: while a coarser equivalence can yield exponentially fewer classes on some families of programs, it may offer little or no reduction for the program at hand. We show how to quantify the advantage of coarser equivalences for individual programs. We focus on the problem of counting the reads-from (RF) equivalence classes induced by a given program, as well as the problem of computing the ratio of RF to Mazurkiewicz class counts under sequential consistency. We show that both problems are $\#\mathrm{P}$-hard and that the reduction ratio remains hard to approximate accurately under standard complexity assumptions. Guided by these limits, we present CoEst, a sampling-based algorithm for estimating both the RF count and its ratio to the Mazurkiewicz count. For a fixed number of threads, each trial runs in polynomial time and yields unbiased count estimates. As the number of independent trials grows, the count and ratio estimates converge almost surely to their true values. Our algorithm can provide statistical evidence for deciding whether Mazurkiewicz or RF model checking is likely to be faster for a given program. In experiments across 34 benchmark configurations, our method selects the faster checker in 99.4% of runs using a one-minute estimation budget.

Comment
32 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

Tree Equivalence of Higher-Order Recursion Schemes Is Undecidable

cs.FL cs.LO ·2026-10-29 ·Mingkun Xiao, Yixuan Sun
theory similarity 0.62
Abstract · 31 pages, 3 figures. Rocq artifact: https://doi.org/10.5281/zenodo.23734555

Higher-order recursion schemes (HORS) are finite, simply typed recursive programs that generate potentially infinite trees. Their monadic second-order model-checking problem is decidable. We prove that tree equivalence of deterministic HORS is undecidable and, more precisely, $Π^0_1$-complete under total computable many-one reductions. The lower bound holds for safe, productive schemes of order at most four over the fixed ranked alphabet $Σ_2=\{e:0,d:2\}$, consisting of one nullary and one binary symbol. Adapting the counter-guard witness of Boiret, Piorkowski, and Schmude, we generate all candidate executions of a two-counter machine by producing both continuations at every counter test. An integer weight is nonzero exactly on legal prefixes. Functions at fixed simple types represent the polynomial of growing degree. A shift recurrence updates them without storing a separate step counter, allowing the witness to be implemented by safe applicative HORS rules. At candidate halts, the intermediate schemes generate unary observation subtrees whose lengths encode the two natural-number components of the signed weight. Invalid candidates give matching observations; a legal halt produces a finite discrepancy. Fixed constructor contexts encode these intermediate trees over $Σ_2$. For the upper bound, a finite monotone semantics decides head convergence and supports an algorithm computing exact tree prefixes at any prescribed finite depth, including positions labelled $\bot$.

0.32

Propositional Dynamic Logic with Program Costs

cs.LO math.LO ·2026-11-02 ·Krishna Manoorkar, Wolfgang Poiger
similarity 0.61
Abstract

We introduce $\mathbb{N}\mathtt{PDL}$, a resource-aware variant of Propositional Dynamic Logic ($\mathtt{PDL}$) capable of accounting for program costs measured by natural numbers (such as time or space in the sense of computability theory). In this framework, programs correspond to transition systems weighted by extended natural numbers, and the syntax of our logic includes formulas expressing which properties are reachable by program executions within specific cost constraints. First, we explain how the standard program constructs of non-deterministic choice, sequential composition, iteration, and tests are interpreted in this weighted setting and establish the validity of their corresponding reduction axioms. Using an appropriate adaptation of the (Fischer-Ladner) filtration technique, we proceed to prove decidability and completeness for $\mathbb{N}\mathtt{PDL}$ as our main results. We furthermore provide upper and lower complexity bounds for this logic using translations between standard $\mathtt{PDL}$ and $\mathbb{N}\mathtt{PDL}$.

0.13

A Unifying Metatheorem on Weak-Memory Robustness

cs.PL cs.LO ·2026-11-17 ·Giovanna Kobus Conrado, Stephan Spengler, Mohamed Faouzi Atig, Andreas Pavlogiannis
theory similarity 0.60
Abstract

Memory models specify the behaviors that concurrent programs may exhibit under compiler and hardware optimizations, which often deviate from Sequential Consistency (SC). Robustness is the property of a program P not exhibiting any weak behaviors when executing under a weak memory model MM, compared to SC. As such, the algorithmic problem of deciding whether $P$ is robust against MM has been studied extensively, and has been repeatedly shown to be in PSPACE for many memory models, such as TSO, PSO, and Release/Acquire. However, each model has required its own, dedicated proof, raising the natural question of whether robustness admits a unifying treatment across memory models. In this work, we answer this question affirmatively for a broad class of memory models definable in Kleene Algebra with Tests (KAT). We prove that robustness against any prefix-closed, KAT-definable memory model is in PSPACE. This metatheorem recovers nearly all prior PSPACE robustness results, and establishes PSPACE membership for several new models, including the full RC11 and the OCaml memory model. We have further formalized the correctness of our approach in Lean. On the other hand, we prove that robustness against the KAT-definable Relaxed model is undecidable, and thus prefix-closedness cannot be dropped, in general. Finally, we implement our algorithm in a prototype tool RoboKAT, and demonstrate its flexibility by checking robustness against nine memory models, several of which are not handled by prior work.

0.34

Reconfiguration of Time-Bounded Descriptions

cs.CC cs.DM ·2026-11-06 ·Dimitrios Myrisiotis
similarity 0.59
Abstract · 50 pages

Time-bounded Kolmogorov complexity measures a string by the length of its shortest program that prints it within a deadline. An adjunction-universal machine (Bauwens, Kozachinskiy, and Shen, arXiv, 2025) is a Turing machine that simulates every Turing machine $M$ on every input $z$ with polynomial overhead when given a code of $M$, computable from $M$ in polynomial time, followed by $z$ unchanged. Any two adjunction-universal machines give the same measure up to an additive constant and a polynomial change of the deadline. However, this measure records only the shortest program for a string. We study all programs of one length that print a string within one deadline, join two of them when they differ in one bit, and ask when this graph is connected. Fix any adjunction-universal machine. For almost all $m$-bit strings and every deadline beyond some polynomial, the graph is disconnected at program length $m+O(1)$ and has at least $2^{m-O(1)}$ components at length $2m+3$. In contrast, we build an adjunction-universal machine in which every such graph is connected or empty, at every deadline, once the program length reaches a computable threshold that is at most exponential in the length of the string. Exponential thresholds are unavoidable: for every adjunction-universal machine with such thresholds and every large $m$, more than three quarters of the $m$-bit strings need a threshold exponential in $m$. For our machine, above the threshold, every program for the string is within three bit flips of a connected set of fastest programs for the string, along a path inside the graph, at every deadline by which that program halts. For this machine, deciding whether two given programs are connected in this graph is $\mathsf{PSPACE}$-complete when the input is the string, the deadline in unary and the two programs; for each fixed string it takes polynomial time.

0.29

count-catcher: Lean Theorems from Model Counting Certificates

cs.LO cs.AI ·2026-10-26 ·Johannes K. Fichte, Stefan Szeider
theory similarity 0.59
Abstract

We present count-catcher, a tool that turns a CPOG certificate of a count by the exact model counter d4 into a Lean theorem that a CNF formula defined in Lean has exactly N models over V variables. With an encoding lemma, this theorem becomes a theorem about the number of combinatorial objects. A CPOG certificate consists of a Boolean circuit equivalent to the formula and a proof of equivalence. count-catcher checks in Lean that the formula implies the circuit (forward check) and the circuit implies the formula (reverse check). For the forward check, lrat-catcher streams a refutation through the LRAT checker of Lean's standard library. The reverse check and the validity check of the circuit are computations proved correct in Lean. Lean runs all three checks as compiled code, so the theorem depends on Lean's kernel, compiler and runtime, as does CPOG's verified checker. We combine the theorem with results from Mathlib, for instance with Burnside's lemma to count graphs up to isomorphism. We prove the number of Latin squares of order 8 as a weighted sum of hundreds of certified counts from about eight terabytes of certificates. We turn about half of the 2022 Model Counting Competition formulas into theorems, with the three checks taking about a quarter of the time of CPOG's verified checker. We found that CPOG's unverified checker reported wrong counts, and removed its verified checker's dependence on two unproved lemmas. End to end, a theorem costs about the same as a checked count.

0.36

An Engineering Reading of the Bounded Halting Problem and Observable Properties of a Universal Machine

cs.CC cs.AIcs.FLmath.LO ·2026-11-04 ·Sergey Salishev
published similarity 0.58
Abstract · 9 pages, 1 table

The halting problem asks whether a program eventually halts, with unrestricted resources. Engineering systems instead certify bounded halting: given a program, an input, and a step budget T, decide whether the program halts within T steps. This paper studies two of its uses. First, it defines an exact finite-budget problem, placing the simulated program and the checker on the same unit-cost timescale, so the checker can be embedded in an adversarial program. A diagonal argument with explicit additive overhead shows that no fixed deterministic checker decides every instance within any fixed fraction of T below one, for large T. In the nondeterministic case, T bounds the branch depth allowed for a stable observable decision. Second, bounded-halting instances give adversarial tests for finitary universality, since a universal model must support arbitrary finite computations as T grows. The tests check resource growth with T, the absence of a fixed deliberation bound, and later access to intermediate data. They separate a fixed model with extendable external resources, a model family that grows with T, and a larger system built around a fixed component. For machine-learning systems, this identifies the resource growth a universality claim assumes and whether it fails for deployed models.

0.41

Order Maintenance in Worst-Case Constant Time, Verified

cs.LO cs.DS ·2026-10-28 ·Denis Firsov
theory similarity 0.58
Abstract

Order maintenance asks for a data structure that keeps a sequence of elements under insertions and deletions and tells which of two elements comes first. We give an algorithm, assembled from published components, that performs each operation in worst-case constant time, and verify it in Lean 4. The algorithm is a program for a random-access machine deeply embedded in Lean, whose interpreter counts every instruction. We prove that the program answers every query as a simple reference specification does, that each operation takes at most a fixed number of steps, independent of the number of elements and of the history, and that after $t$ operations no value it has computed has more than $O(\log t)$ bits, so it runs unchanged on a machine with words of that size. A verified translation that preserves step counts exactly connects the high-level proofs to the machine program, so the interpreter is the only cost model to trust. An unverified native implementation shows the algorithm's practical cost.

0.36

Domain Theory Meets Interaction Trees in Rocq

cs.LO ·2026-09-28 ·David Nowak, Vlad Rusu
published similarity 0.58
Abstract · In Proceedings FROM 2026, arXiv:2609.30324

We present a domain-theoretical formalization of interaction trees in the Rocq prover. Unlike existing formalizations, ours does not rely on Rocq's built-in coinduction. Hence, we avoid complications occurring in earlier works, such as artificially including silent steps to comply with Rocq's productivity checker, treating monad laws as weak bisimulations, and coinductive bisimulation reasoning. We define an inductive program equivalence relation as the congruence closure of a base relation on primitive effects with respect to action sequencing and least upper bounds. This enables reasoning about possibly non-terminating programs by reducing their equivalences to equivalences of their terminating approximations, which are then proved by induction. This relation is proved correct: provided the base relation is correct, equivalent computations have equal denotations in any monad that faithfully implements the effects. We illustrate the framework by showing the equivalence of two programs encoding the Syracuse sequence, whose termination is an open mathematical conjecture.

0.38