arXiv weekly literature review

Formal Proof Assistants · primary corpus · published 2026-09-14T02:00:18Z
Celio Boulay, Alexander Chai, Anthony Chang, Thomas Moulin
arXiv categories: cs.LO

The mathematics of Origami have been well studied and shown to develop several interesting results. We use Lean 4 tactics and build on Mathlib to redefine the 7 Huzita operations as theorems instead of axioms and prove their existence. We develop proofs for important origami constructions (such as trisecting an angle), implement origami-constructible numbers and prove the associated Cardano's formula, and formalize Haga's theorem. A Crease Pattern Inspector explores physical folding by providing a full pipeline to create and visualize models constrained by the Huzita formalism. The Lean codebase brings 100+ theorems and lemmas.

arXiv abstract · PDF

Formal Proof Assistants · primary corpus · published 2026-09-14T14:30:11Z
Henning Ulfarsson
arXiv categories: math.CO, cs.DM, cs.DS, cs.LO

We give an exact algorithm counting the permutations that avoid a fixed pattern from the following family: the direct sum of an increasing pattern and the pattern 231. The first members of the family are 1342 and 12453. For each member, the algorithm computes the number of avoiding permutations of every length up to a given bound using polynomially many arithmetic operations and polynomially many stored integers, with degrees that grow linearly in the length of the pattern. We first obtain an exact recurrence by reading a permutation from left to right and recording, at each step, the constraints that the letters read so far impose on those still unread. Its state space grows exponentially, so evaluating it directly takes exponential time. We then show that part of the state is protected: later steps carry it along unchanged and do not depend on it. Factoring the protected part out turns the recurrence into a dynamic program with polynomially many stored transfer entries, and this gives the polynomial bounds for every member of the family. For the pattern 12453, a translation symmetry sharpens the bounds to degree seven for the operations and degree four for the storage. Separately written implementations and exact Chinese-remainder certification determine the number of 12453-avoiding permutations of every length up to 150. The previously published series reached length 38. The same tables also generate uniformly random avoiders in polynomial time. We illustrate this with a heatmap of one million 12453-avoiding permutations of length 300 sampled with floating-point tables. The counting recurrences for 1342 and 12453 are verified in the Lean 4 proof assistant.

arXiv abstract · PDF

Formal Proof Assistants · primary corpus · published 2026-09-14T19:58:03Z
Yuquan Fu, Carlo Angiuli, Sam Tobin-Hochstadt
arXiv categories: cs.PL

Over the past two decades, numerous systems have brought some of the benefits of dependent typing to a wide variety of new programming languages, often by restricting which terms can appear inside types. Such techniques are known as refinement types, occurrence typing, liquid types, and path dependent types, among others. However, the restrictions adopted by these systems often break the substitution property, because they explicitly disallow the ability to substitute arbitrary terms for variables inside types. This leads to significant complexity in the design and metatheory of these systems, increasing the possibility of significant errors. We consider a specific line of work on occurrence typing, namely, the calculus underlying Typed Racket due to Tobin-Hochstadt and Felleisen 2010. We show that the fundamental challenge of substitution into types resulted in multiple flaws in the formalism and the syntactic type soundness theorem of this work. These flaws are replicated in several other papers building on this work, and also surface as a soundness bug in Typed Racket itself. We identify and repair these problems, revising the core calculus of Typed Racket and giving a \emph{semantic type soundness} proof using step-indexed logical relations, formalized in Lean. We argue that this approach is simpler than it may seem, and easily scales to handle the complexity of the occurrence typing in Typed Racket.

arXiv abstract · PDF

Formal Proof Assistants · primary corpus · published 2026-09-16T07:39:15Z
Pierre Senellart, Anton Gnatenko
arXiv categories: cs.LO, cs.CC

We show that descriptive complexity can serve as a foundation for formalizing computational complexity results in a proof assistant, by constructing a Lean library centered around the following concepts: decision problems are isomorphism-invariant predicates on finite structures; complexity classes are defined by their logical characterization; membership is shown by definability witnesses; hardness is shown by first-order reductions from a known hard problem. We also establish bridges to traditional machine models such as (non)deterministic Turing machines. The library proves 73 completeness results, on 68 problems or problem families, over 14 different classes; relations between the classes established inside the logic and not by machine simulation, among them NL = coNL and the Abiteboul-Vianu theorem; and unconditional lower bounds, among them $\mathrm{FO}(\leq) \subsetneq \mathrm{FO}(\leq, \mathrm{TC})$ and the failure of order-free FO(IFP) to capture PTIME.

arXiv abstract · PDF

Formal Proof Assistants · primary corpus · published 2026-09-16T10:01:12Z
Angeliki Koutsoukou-Argyraki, Lawrence C. Paulson
arXiv categories: cs.LO

A 2021 proof of a special case of the Union-Closed Conjecture, by Aaronson, Ellis and Leader, has been formalised in the proof assistant Isabelle/HOL. Our discussion involves sketching their proof and displaying snippets from the Isabelle version of the proof, illustrating the extent to which mathematical reasoning can be rendered clearly in a formal language.

arXiv abstract · PDF

Formal Proof Assistants · primary corpus · published 2026-09-16T19:27:55Z
Robert Joseph George, Will Adkisson, Anima Anandkumar
arXiv categories: cs.LO, cs.PL

We present FloatLib, a verified arbitrary-precision floating-point arithmetic library in Lean 4 that combines broad format coverage, machine-checked correctness, and efficient certified execution. To our knowledge, FloatLib is the first Lean library to unify IEEE binary and decimal arithmetic, arbitrary-width posits, P3109, and user-defined formats and rounding rules behind interchangeable certified software backends. Every certified backend is proved equal to a complete encoded specification, preserving signed zeros and exceptional values, while numerical theorems connect execution to real rounding, error bounds, and exactness. FloatLib combines exhaustive certified tables for small formats with verified word and limb kernels based on guard-and-sticky invariants and independently checked quotient candidates. Its posit development additionally proves standard rounding thresholds and exact quire accumulation within capacity for arbitrary widths. Across matched workloads, FloatLib achieves speedups of up to 1.46x over FLoPS and 116x over Universal, while remaining slower in some regimes such as binary arithmetic against MPFR. Independent conformance testing includes more than 102 million TestFloat evaluations with zero differences under the tested relation. We release the library, proofs, benchmarks, evaluation data, and guide as open source.

arXiv abstract · PDF

Formal Proof Assistants · primary corpus · published 2026-09-16T22:44:05Z
Daniel O. Mart\'inez-Rivillas, Arthur F. Ramos, Ruy J. G. B. de Queiroz
arXiv categories: cs.LO

We present a typed two-dimensional $\lambda$-calculus whose equality evidence is \emph{computational}: a path between two terms is an explicit finite sequence of one-step conversions (the $\beta$- and $\eta$-contractions, the congruences, and the structural rules), and every property of paths is proved \emph{by recursion over that sequence}, with any step as a base case --- in deliberate contrast with Martin-L\"of type theory, where identity is generated by reflexivity alone and all properties go through the non-computational $J$-eliminator. The higher structure is imported from the $2\beta$- and $2\eta$-conversions of the theory of an arbitrary higher $\lambda$-model: we obtain 2-dimensional coherence laws, computable naturality of homotopies (via inductive homotopies and their explicit evaluations), a 2-dimensional path type with transport, and a parity invariant that proves the system consistent and \emph{really intensional}: the $\beta$- and $\eta$-contractions are provably distinct evidence, while in the native syntax of Idris (core MLTT) they are identified by definitional equality. Commutative diagrams accompany the main constructions, and the theory is fully formalized in Idris 2. A parallel Lean formalization is published in the Palomar registry \cite{palomar2026lean}. A philosophical reading closes the paper: constructivism in the BHK sense, proof-relevant intensionality, and the boundary between syntax and semantics, drawn relative to MLTT and HoTT.}

arXiv abstract · PDF

Formal Proof Assistants · primary corpus · published 2026-09-17T02:11:52Z
Chunhao Liao, Hongxu Xu, Xintong Zhou, Yizhou Zhang, Chengnian Sun
arXiv categories: cs.PL

LLVM is the cornerstone of modern compilers, but its subtle intermediate representation (IR) semantics make transformations error-prone and necessitate formal verification. Alive2, a state-of-the-art translation validator based on satisfiability modulo theories, has achieved substantial success in automating the validation of LLVM transformations. However, it still faces scalability limitations, does not support symbolic bitwidths, and offers only bounded guarantees for loops. In contrast, interactive theorem provers such as Lean can address these cases but require substantial proof engineering. In this paper, we present Trivet, a framework combining large language models (LLMs) and Lean for automated translation validation of LLVM transformations. Trivet generates structured proof scaffolds based on source and target functions, automatically discharges obligations amenable to deterministic reasoning, and delegates transformationspecific obligations to LLMs. It produces refinement proofs or counterexample-based refutations, with every successful verdict checked by the Lean kernel. On 148 LLVM transformations, Trivet verifies or refutes 147, leaving one invalid case unresolved. Successful cases include 60 loop-free transformations with symbolic bitwidths, 27 cases from a restricted class of loop-containing transformations, and 10 complex valid fixed-bitwidth cases on which Alive2 times out. Compared with an unscaffolded baseline, scaffolding enables 26 additional proofs. On cases solved by both configurations, it reduces mean proof time by 75.9% and mean monetary cost by 88%.

arXiv abstract · PDF

Formal Proof Assistants · primary corpus · published 2026-09-17T07:26:49Z
Sirui Lu, Ruixuan Deng, Yanqiao Zhu, Zhengfeng Ji
arXiv categories: quant-ph, cs.AI, cs.LO

Landmark mathematical formalizations have taken specialist teams years to complete. We present FormalFlow, a system that coordinates AI proving agents under human supervision to address statement drift and proof composition in long-horizon formalization. Drawing on software engineering principles and practices, it uses a shared blueprint to guide nested planning, proving and review loops. Agents strengthen verification and review throughout formalization. We completed a machine-checked Lean 4 proof of the quantum soundness of the classical low individual-degree test, a core theorem underlying MIP* = RE. Developing the proof took 63 days; greater parallelism could further reduce this time. The final library contains 126,367 lines of Lean code, all generated by agents. The formalization corrects side conditions and intermediate errors while preserving the published final error bound under corrected assumptions. This work provides a verified foundation for quantum complexity and demonstrates a route to affordable verification of major research proofs by small teams.

arXiv abstract · PDF

Formal Proof Assistants · primary corpus · published 2026-09-17T12:22:36Z
Gabriella Clemente, Hugo Herbelin, Carlos Simpson
arXiv categories: math.DG, cs.LO

We introduce a synthetic framework for doing local Riemannian geometry that is influenced by a reverse-engineering method for formalizing in Rocq. These new perspectives and techniques lead to a synthetic Taylor formula for a Riemannian metric in normal coordinates, which is the main contribution of this work.

arXiv abstract · PDF

Formal Proof Assistants · primary corpus · published 2026-09-17T13:28:04Z
MingKun Xiao, YiXuan Sun
arXiv categories: cs.LO

Escard\'o's dialogue interpretation assigns to each closed term $t:(\iota\to\iota)\to\iota$ of G\"odel's System~T a well-founded, countably branching tree $D(t)$, where $\iota$ is the natural-number type. We give a direct proof that its classical ordinal height is below $\epsilon_0$. More precisely, we compute a natural number $K(t)\ge2$ from the type levels occurring in the source term and prove $h(D(t))<\theta_{K(t)}$, where $\theta_0=\omega$ and $\theta_{n+1}=\omega^{\theta_n}$. Our proof translates recursors into closed infinitary templates and eliminates $\beta$-redexes by a finite sequence of passes indexed by ordinary type level. The translation and every pass preserve the dialogue denotation exactly. An auxiliary rank $\rho$ satisfies an additive substitution bound; each pass sends rank $\alpha$ to at most $2^\alpha$. Combining these estimates with a computable initial bound $\omega+m(t)$ and a dialogue-height bound $2^{\rho(N)}$ for closed ground normal forms $N$ yields the stated tower bound. A semantics-preserving translation transfers the result to Escard\'o's original combinatory interpretation. We formalise the proof in Agda over classical ordinals under explicit foundational assumptions.

arXiv abstract · PDF

Formal Proof Assistants · primary corpus · published 2026-09-17T23:50:08Z
Ibrahim Mian, Shayaan Siddique
arXiv categories: math.GR, cs.LO

Kaplansky's zero-divisor conjecture asserts that the group ring of a torsion-free group over a field has no zero divisors. It holds for every group with the unique-product property, so a counterexample can only come from a torsion-free group without unique products. In lectures in 2021, Gardam announced that the torsion-free $\tilde{A}_2$ lattice $\Gamma = \langle a, b \mid a b a^2 b^{-1} a^2 b^{-2}, a b^3 a b^4 a^{-1} b \rangle$ does not have unique products and presented it as a new candidate group: it has property (T), and the known methods for proving the conjecture do not apply to it. To our knowledge, no proof of the announcement has been published. We give a proof checked by the Lean 4 kernel and stated against Mathlib's UniqueProds class. The witness is an explicit pair of finite subsets with $|A| = 32$ and $|B| = 28$ in which each of the 896 products coincides with another product. For 658 products the certificate is an identity in the free group; the other 238 certificates are explicit products of conjugated relators, 970 conjugates in all, checked by free reduction. A homomorphism onto $\mathbb{Z}/42$ shows that each pair $(u,v)$ differs from its partner $(u',v')$ as a pair of group elements, which is all the theorem requires. Together with a homomorphism onto the alternating group $A_4$ it also shows that the listed words are pairwise distinct, so the sets have exactly 32 and 28 elements. The witness and certificates come from an untrusted search program and are re-checked by Lean. The development uses only the axioms propext, Classical.choice and Quot.sound, with no sorry and no native_decide. The mathematical statement is Gardam's. To our knowledge this is the first verification in a proof assistant of a unique-product failure in a torsion-free group; torsion-freeness of $\Gamma$ is taken from Gardam and is not formalized here.

arXiv abstract · PDF

Formal Proof Assistants · cs.SE candidate · published 2026-09-18T01:16:53Z
George Ma, Benjamin Mikek, Haoyu Li, Ferhat Erata, Yuhao Zhang, Zeren Shui, Behrooz Omidvar Tehrani, Jun Huan, Murali Krishna Ramanathan, Somayeh Sojoudi, Hao Zhou, Anoop Deoras
arXiv categories: cs.LG, cs.AI, cs.SE

Ensuring the correctness of LLM-generated code is a core challenge for modern software engineering. Benchmarks for agentic code generation check correctness with held-out test suites, which are inherently incomplete and increasingly susceptible to memorization. Formal verification avoids both problems, but existing work covers only standalone tasks whose specifications are given as input, not real issues, which touch large repositories and state intent in vague natural language. We present Benchproofer, a pipeline that turns a coding task with a known correct patch into a formally verified one: it writes a specification for the new code, summarizes the existing functions that code calls with axioms, and admits an instance only after mechanical and adversarial gates agree. Applying it to SWE-bench Verified yields SWE-Proof, 500 real issues whose correctness is formally verified rather than tested, and it extends to SWE-bench Pro. Across two frontier models, verification catches what tests miss: a quarter to a half of test-passing patches admit counterexamples, which a structured natural-language specification does not fix, while a correct formal one lifts resolution from 85% to 95% for Opus 4.8. Writing that specification is the hard part: models that must write their own gain nothing over an unaided baseline, and only 62% of their specifications pass our audit. The usual failure is faithfulness, a specification that constrains part of the required behavior and leaves the rest free. Specification quality still tracks the outcome, failing on 89% of unresolved instances against 47% of resolved ones, making faithful specification synthesis a concrete open problem.

arXiv abstract · PDF

Formal Proof Assistants · primary corpus · published 2026-09-19T13:32:02Z
Kamil Braun
arXiv categories: cs.CC, cs.LO

Resolution over parities, $\mathrm{Res}(\oplus)$, is the characteristic-two version of resolution over linear equations: clauses are disjunctions of affine equations over $\mathbb F_2$. Superpolynomial size lower bounds were previously known only for restricted refutations: tree-like, regular, or of bounded depth. We prove that every DAG-like $\mathrm{Res} (\oplus)$ refutation of the bit pigeonhole principle with $n+1$ pigeons and $n=2^\ell$ holes has more than $\exp(n/(32768\ell^2))=2^{\Omega(n/\log^2 n)}$ clauses, for every $\ell\ge32$, with no restriction on regularity or depth. The proof translates an arbitrary refutation with $S$ clauses into a polynomial calculus refutation of degree $O(\log n)$ over $O(S+n^2)$ groups of extension variables in the style of Buss, Impagliazzo, Krajicek, Pudlak, Razborov, and Sgall. One substitution then removes all extension variables at once and leaves a nonzero low-degree polynomial derived from the pigeonhole axioms alone at degree at most $n/2$; a degree lower bound in the style of Razborov, proved through the homology of chessboard complexes, shows that no such derivation exists. The argument also yields a general sufficient condition for $\mathrm{Res}(\oplus)$ size lower bounds. The main theorem, this condition, and all their dependencies are formalized in Lean 4, and every statement links to its formal proof. The proof was developed with substantial AI assistance within an open research framework described in the final section.

arXiv abstract · PDF

Formal Proof Assistants · primary corpus · published 2026-09-19T17:19:24Z
Mario Carneiro
arXiv categories: math.LO, cs.LO

The sets-as-trees interpretation of set theory in a dependent type theory with an impredicative universe of propositions validates Zermelo set theory, and it validates Replacement if the type theory has a choice or description operator, which turns a functional relation into a function. It has been natural to expect that without such an operator the strength of the type theory drops well below that of $\mathrm{ZF}$. We show that it does not. In the type theory of Lean with two predicative universes, from excluded middle as the only assumption and with no axiom (no choice, no propositional extensionality, no quotients), we prove the consistency of $\mathrm{ZF}$, stated outright for a first-order proof system. The proof is formalized. The mechanism is the large elimination of the accessibility predicate over a type as large as the type of sets: a recursion on accessibility whose recursive calls are guarded by propositions, and whose later calls are indexed by the value of an earlier call, computes as a term any ordinal that is specified by a proposition through a well-founded tree of a certain shape. We give a rule that produces such a tree for every ordinal, unless some $V_\rho$ is already a model of $\mathrm{ZF}$; the rule does not choose a cofinal map into a limit ordinal but takes all definable ones at once. In the first case the sets-as-trees satisfy Replacement for arbitrary propositional relations. Either way $\mathrm{ZF}$ has a model. Finally, the double negation of excluded middle suffices, and what remains of it is exactly that membership is not not well-founded in the stable reading of sets; this in turn implies the double negation of Markov's principle.

arXiv abstract · PDF

Automated Reasoning and Verification · primary corpus · published 2026-09-14T06:45:58Z
Dylan Waldner, Yiannis Kantaros, Guido Governatori, Risto Miikkulainen, Amir Banifatemi
arXiv categories: cs.RO, cs.AI, cs.LO

As robotic systems grow more general, legal norms are needed to integrate them into society. This paper extends the isomorphism problem of aligning legal source texts with their encodings, and measures two key challenges to robot normative control: (1) the grounding isomorphism gap, where perception error grounds false atoms for legal reasoning, and (2) the ontological isomorphism gap, where one legal conclusion admits many faithful translations into planning constraints. The paper introduces a legal planning stack that employs Defeasible Deontic Logic (DDL) to constrain a motion planner. The stack leverages learned world models to plan and to provide legal context, enabling ex ante governance that intervenes before an illegal action is executed. It was deployed on a simulated robot arm pushing a cube across a 3x3 grid. The findings were (1) the legislated agent abided substantially more often than the non-legislated one, and modeling perception uncertainty lifted abidance even further, (2) the legal reasoning ran efficiently at runtime and its verdicts were auditable, and (3) the stack adapted to exogenous signals and endogenous rule changes. Both gaps were measured: (4) world model and probe error corrupted the factual input for the DDL reasoner, and (5) a single law admitted several faithful metric interpretations yielding drastically different abidance. Thus, ex ante legislation functions as intended, and closing these gaps with a standardized mapping from the law to runtime constraints and improved fact grounding from perception will yield robust laws that align robot behavior with society's norms. Project page: https://dylanwaldner-cail.github.io/Legislated-Planner/.

arXiv abstract · PDF

Automated Reasoning and Verification · primary corpus · published 2026-09-14T12:01:25Z
Rhea Malhotra, Tanya Sharma, Krisha Patel, Satvika Sharma, Heena Purkait, Mehak Nehal Makhija, Aellison Cassimiro, Everett Hildenbrandt, Palina Tolmach, Jaidev Shastri
arXiv categories: cs.SE, cs.CY, cs.LO

An artificial organ carries failure consequences on the scale of an aircraft or a reactor, but the software driving it is rarely held to the same standard. Teams building them rely on testing, which only reaches the failure modes someone thought of in advance. In a pump or controller that runs inside a patient for months, the dangerous cases are the ones nobody anticipated. Formal verification closes that gap. Applied to the device's software, it proves the code meets its specification for every execution that specification allows, and where a proof fails, it returns the exact input sequence that breaks it. The same methods already protect rail, aviation, and nuclear control systems, and they extend the IEC 62304 lifecycle that a manufacturer already follows rather than replacing it. In this paper, we explore how to apply formal verification to artificial organs, stage by stage, and what each technique actually guarantees about the device.

arXiv abstract · PDF

Automated Reasoning and Verification · primary corpus · published 2026-09-14T16:58:57Z
Clotilde Bizi\`ere, J\'er\^ome Leroux, Gr\'egoire Sutre
arXiv categories: cs.LO, cs.FL

Vectors addition systems with states (VASS), a model equivalent to Petri nets, are finite-state machines with finitely many counters ranging over the natural numbers. The decidable reachability problem for VASS has many applications in logic, automata, and verification. In this paper we study the reachability problem for BVASS, a branching generalization of VASS. We show that BVASS reachability sets are very similar to VASS reachability sets, namely that they are sections of VASS. Our proof relies on a new well-quasi-order (wqo) on BVASS runs that generalizes the well-known wqo on VASS runs. By leveraging an amalgamation property, we prove that every BVASS run can be transformed into an equivalent one of bounded branching complexity. This allows us to derive several results on the geometry of BVASS reachability sets. As an application we obtain that reachability sets of 5-dimensional BVAS are effectively semilinear, as is the case for 5-dimensional VAS.

arXiv abstract · PDF

Automated Reasoning and Verification · primary corpus · published 2026-09-14T18:57:41Z
Karel Chvalovsk\'y, Martin Suda, Josef Urban
arXiv categories: cs.LO

A neural clause-selection guidance approach in the Vampire theorem prover was recently shown to substantially improve the success rate of the prover's default strategy on the TPTP benchmark. We experimentally study the impact of the approach across several ITP-derived benchmark sets and its interaction with theorem proving strategies. We find that while the neural guidance consistently improves performance within individual benchmark domains, cross-benchmark application of guiding models underperforms the plain default strategy. This can be remedied by training a single model on all datasets at once. Such a model, although more expensive to obtain, helps Vampire almost catch up in performance across all datasets. The picture when considering combined strategies is less clear-cut, indicating persisting value of neural guidance but under diminishing returns.

arXiv abstract · PDF

Automated Reasoning and Verification · primary corpus · published 2026-09-15T06:31:22Z
Mikol\'a\v{s} Janota, Jan Jakub\r{u}v
arXiv categories: cs.LO

This paper presents the SMT solver primo, which is fully vibe-coded and then parameter-tuned, achieving state-of-the-art results on linear real arithmetic (QF-LRA). The performance of primo is achieved by a systematic literature survey, repeated profiling, and parameter tuning. The resulting solver outperforms the winner of the QF-LRA track of SMT-COMP~2026. This confirms that vibe-coding of automated reasoning tools will enable us to make great strides in the future.

arXiv abstract · PDF

Automated Reasoning and Verification · primary corpus · published 2026-09-16T06:01:22Z
Rohan Pandey
arXiv categories: cs.LO, cs.LG

Synthesis pipelines increasingly claim not just that a program is correct, but that it is optimal. Such a claim has two halves with radically different verification stories. The upper bound, "a program of size m exists", is witnessed by an artifact that can be re-executed, proved equivalent to its specification, and shipped with a machine-checked certificate. The lower bound, "no program of size m-1 exists", has no witness and is discharged by running a solver until it reports UNSAT. Combinatorial optimization has known this asymmetry for decades and has largely addressed it: certifying algorithms make it explicit (McConnell et al., 2011), and pseudo-Boolean proof logging can certify optimality end to end with a formally verified checker (Bogaerts et al., 2023; Koops et al., 2025). That discipline has not reached circuit minimization. We call this the refutation gap: published gate counts for minimal XOR circuits provide no certificate for either half of the claim, and neither did 121 optimality results we ourselves produced. We close the gap with a pipeline that synthesizes minimal linear straight-line programs over GF(2), where every decisive UNSAT answer emits a DRAT proof checked by an independent third-party checker. We certify all 121 optimality results established by the project, across n = 6 to 9: 111 carry independently verified refutations, 10 are closed by a free counting bound, and none disagrees with the uncertified value. The median proof is 1.1 MB and checking costs 1.9x solving. We give five case studies where verification caught defects that code review did not, report two interface obstacles that push practitioners toward the uncertified path, and describe an adversarial audit that revealed a failure tail we were about to attribute to the problem was actually caused by our own budget.

arXiv abstract · PDF

Automated Reasoning and Verification · primary corpus · published 2026-09-16T11:19:31Z
Matthias Baaz, Mariami Gamsakhurdia
arXiv categories: cs.LO

We investigate the proof-theoretic structure of incorrect/incomplete proofs, that is, derivations containing syntactic errors or incomplete inferential steps that nonetheless preserve partial semantic validity. Building on Hilbert's epsilon calculus, we formalize how such derivations can be corrected through semantic projection and weakest preconditions, leading to valid Herbrand disjunctions. We show that the epsilon calculus provides a natural framework for analyzing tolerance of falsity in proofs and for identifying conditions under which an incorrect proof can be semantically repaired. This approach extends Hilbert's program beyond correctness, toward a logic of error and recovery. Moreover we show that the extended first epsilon theorem is false-tolerant.

arXiv abstract · PDF

Automated Reasoning and Verification · primary corpus · published 2026-09-16T13:52:16Z
Elia Nikolaou, Magnus Wiik Eckhoff, Robert Flood, Gudmund Grov, Vasileios Mavroeidis, David Aspinall
arXiv categories: cs.CR, cs.LO

LLM-based agents generate and execute multi-step plans that invoke external tools which can access private data or execute commands. In this setting, security is a property of the entire execution that a plan creates, not just any single step. The plan itself is a critical artefact that captures the tool calls, control flow, and data dependencies. We present CaMeLoT, a complement to CaMeL, an existing defence against prompt injection in tool-using LLM agents. CaMeLoT extends CaMeL by adding a static verification layer that checks an agent's plan before any tool is invoked. CaMeLoT translates a generated plan into a finite-state transition system, labels it with tool calls, provenance and taint information, and checks it against temporal policies expressed in CTL using the nuXmv model checker. Because verification happens before execution, unsafe plans are rejected without using LLM calls or tool calls, saving tokens that runtime could have cost, as well as the need to unwind changes or teardown temporary sandboxes. When a verification fails, the model checker returns a counterexample to give feedback to the agent to repair the plan. We evaluate CaMeLoT on policies derived from the AgentDojo benchmark, SOC workflows, and prompt-extraction experiments, showing that it verifies a broad class of temporal properties before execution while preserving CaMeL's runtime-checkable coverage.

arXiv abstract · PDF

Automated Reasoning and Verification · primary corpus · published 2026-09-16T17:15:19Z
Hsi-Ming Ho, Shankara Narayanan Krishna, Khushraj Madnani, Rupak Majumdar, Paritosh Pandya
arXiv categories: cs.LO

The theoretical foundation for model checking timed systems against Metric Interval Temporal Logic (MITL) was established in the early 1990s, yet the first practical tool supporting future MITL (MightyL) did not emerge until 2017. Recently, there has been growing interest in extending this toolchain to support more expressive logical operators, including past modalities, Pnueli modalities, and limited use of singular intervals. MightyPPL is one such toolchain. We introduce an upgraded version of MIghtyPPL that enables for the first time, the model checking of Metric Temporal Logic (MTL) properties of the form (whenever an event p occurs, it is eventually followed by some event q after exactly some k time units) in addition to Pnueli and Past modalities. We discuss the tool's underlying architecture and implementation, and present a performance evaluation against the Tempora tool across diverse satisfiability and model checking benchmarks, demonstrating that MightyPPL delivers significantly better performance.

arXiv abstract · PDF

Automated Reasoning and Verification · primary corpus · published 2026-09-16T19:28:06Z
Ashwin Karthikeyan, Ethan Kharitonov, Kuldeep S. Meel, Anwar Hithnawi
arXiv categories: cs.CR, cs.LO

Proofs of UNSAT are a standard primitive in formal verification and software assurance. In many real-world settings, the proof itself encodes proprietary or security-sensitive information, making public disclosure undesirable. Zero-knowledge certification of UNSAT addresses this tension: it enables a prover to convince a verifier that no satisfying assignment exists, without revealing anything about the underlying proof beyond its validity. Luo et al. recently introduced ZkUnsat, a protocol that achieves this goal by proving the validity of a weakened resolution proof in zero knowledge. ZkUnsat demonstrates the feasibility of zero-knowledge certification; however, its scalability to larger, real-world instances is constrained by substantial prover memory overhead, limiting its real-world applicability. Motivated by advances in UNSAT proof formats such as LRAT, which enable efficient plain-text verification, we present a preprocessing technique that improves the efficiency of ZkUnsat without introducing additional leakage. Our approach normalizes the proof so that each derived clause is justified by a resolution chain of fixed public length k. This eliminates chain-length leakage and reduces prover memory usage. With k = 16, our method certifies roughly 62% more instances than baseline ZkUnsat on the SAT 2002 competition benchmarks. Furthermore, for an equivalent number of certified instances, the memory footprint drops to under 25% of that required by the baseline.

arXiv abstract · PDF

Automated Reasoning and Verification · primary corpus · published 2026-09-17T05:57:16Z
Rosa Abbasi, Eva Darulova
arXiv categories: cs.PL

SMT solvers are essential in various domains, including program verification and synthesis. Although their correctness and performance have been extensively studied, performance testing for the floating-point theory remains limited, particularly for real-world queries. We propose a metamorphic testing approach that uses semantics-preserving rewrite rules, focusing on floating-point special values and peep-hole optimizations, to uncover meaningful performance issues in SMT solvers' handling of floating-point formulas. Using real-world test inputs, our approach is able to identify for every solver tested SMT queries for which solving time increases when the queries are simplified; we see slowdowns of up to 33.4x for Z3, 5.6x for MathSAT, 4.5x for cvc5, and 1.8x for Bitwuzla. We further observe that the approach is less successful when using input files that were randomly generated from a grammar.

arXiv abstract · PDF

Automated Reasoning and Verification · primary corpus · published 2026-09-17T17:40:04Z
Ali ArjomandBigdeli, Jiawei Zhou, Stanley Bak
arXiv categories: eess.SY, cs.AI, cs.LO, cs.SE, cs.SY

Falsification searches for counterexamples to formal specifications in cyber-physical systems (CPS). With specifications written in Signal Temporal Logic (STL), falsification can be formulated as a robustness optimization problem, traditionally tackled with black-box search algorithms. In parallel, large language models (LLMs) have recently emerged as surprisingly effective optimizers when coupled with iterative prompting. In this work, we connect these ideas and introduce LLM-Falsifier, an LLM-based approach that falsifies specifications by minimizing the STL robustness degree. Beyond generic prompt-based optimization, our key idea is to expose the LLM to semantic information that is natural for language models but absent from standard numerical optimizers, including natural-language input and output names, output trajectories, and critical-time witnesses for the minimum robustness value. These additions enable smarter and more sample-efficient robustness search. On the ARCH-COMP falsification benchmarks, LLM-Falsifier is shown to outperform existing falsification tools based on a range of optimization paradigms, from surrogate-based and Bayesian optimization to search-based testing, on 14 of 21 specifications when measured by the average number of simulations required to find a counterexample.

arXiv abstract · PDF

Automated Reasoning and Verification · primary corpus · published 2026-09-17T18:12:28Z
Sehee Park, Dominik Gei{\ss}ler, Andrei Aleksandrov, Kim V\"ollinger
arXiv categories: cs.LO

The EU AI Act mandates that datasets for high-risk machine learning (ML) systems meet strict quality criteria such as soundness and bias mitigation. While Satisfiability Modulo Theory (SMT) solving offers a formal approach to verifying these properties, its scalability in realistic ML settings remains unexplored. To bridge this gap, this work presents the first large-scale empirical study of SMT-based dataset verification on two real-world ML datasets. We systematically evaluate how solver performance is shaped by three key dimensions: the type of data-quality property, the specification style, and the dataset encoding strategy. Our findings demonstrate that SMT-based verification is feasible for practical scenarios, but each dimension shapes it: the property type sets the tractability limit, the specification style drives scalability (exceeding 2000x for aggregate properties), and the encoding strategy has a systematic effect, with extracted feature columns performing best.

arXiv abstract · PDF

Automated Reasoning and Verification · primary corpus · published 2026-09-18T08:46:37Z
Jingyu Hu, Shu Yang, Weiru Liu, Di Wang
arXiv categories: cs.AI, cs.LO, cs.SC

Chain-of-Thought (CoT) reasoning has been shown to improve the performance of large language models (LLMs), yet existing optimization methods largely rely on outcome-based feedback, leaving the logical validity of intermediate reasoning steps largely unverified. To address the gap whereby LLMs arrive at correct final answers through logically flawed intermediate reasoning chains, we propose LogicTrack, a neuro-symbolic framework that audits reasoning trajectories by auto-formalizing each reasoning step into symbolic representations and verifying it with automated theorem provers. LogicTrack introduces Solver-Based Backtracking Reward (SBR), a step-wise scoring mechanism that quantifies logical soundness and guides backtracking tree search at inference time. We further extend LogicTrack to construct supervised fine-tuning (SFT) data with backtracking traces from its trajectories, enabling fine-tuned models to internalize step-wise auditing as an intrinsic capability. Extensive experiments across 8 reasoning benchmarks and 7 LLMs demonstrate that LogicTrack effectively improves both the verifiability of reasoning chains and final answer pass rate, thereby enhancing overall CoT quality and trustworthiness in high-stakes domains.

arXiv abstract · PDF

Automated Reasoning and Verification · primary corpus · published 2026-09-18T09:45:26Z
Michael Codish, Mikol\'{a}\v{s} Janota, Peter J. Stuckey
arXiv categories: cs.LO

Symmetry breaking in graph search problems remains challenging: complete symmetry breaking constraints are typically exponential in size, while partial approaches trade precision for scalability. We introduce a strength-driven, redundancy-aware methodology for constructing compact partial symmetry breaking constraints based on graph patterns. Each pattern corresponds to a Boolean clause over equality literals and can be integrated directly into CP or SAT models. Our approach incrementally selects strong, non-redundant graph patterns, yielding partial symmetry breaks that achieve substantial pruning of non-canonical graphs while remaining compact in size. This provides a principled framework for deriving lightweight partial symmetry breaking constraints which are significantly more precise than all published state-of-the-art alternatives. We evaluate the proposed constraints on graph instances with up to 25 vertices using a redundancy ratio metric. The resulting partial symmetry breaks constitute only a small fraction of the size of complete symmetry breaking constraints, while delivering significant performance improvements across several graph search benchmarks compared to previously defined partial symmetry breaking methods.

arXiv abstract · PDF

Programming Languages and Compilers · primary corpus · published 2026-09-14T13:40:04Z
Jacob Malloy, Michael R. Jantz, Terry Jones
arXiv categories: cs.PL, cs.DC, cs.PF

Managed language runtimes often provide concurrent garbage collectors so that latency-critical applications with large working sets can keep running while most collection work proceeds in the background. ZGC is a production-quality, generational, concurrent collector in OpenJDK with sub-millisecond pause times. While ZGC is designed to run concurrently, frequent and excessive collections with ZGC can still slow the mutators due to synchronization costs and interference with shared computing resources. Hence, the ZGC scheduler is conservative by default, and in most cases, will grow the heap toward the maximum allowed before scheduling a collection. While this approach minimizes collection effort, it can be wasteful, or even harmful, if the maximum heap size is not well tuned to the actual working set. We propose Opportunistic ZGC (OppZGC), a feedback-directed ZGC scheduling policy that constrains the heap dynamically and automatically, without per-application tuning. OppZGC identifies periods when CPU cores are underutilized and leverages them for concurrent collection with ZGC. We describe the design and implementation of OppZGC in OpenJDK's HotSpot Java VM and evaluate it with standard and latency-sensitive benchmarks from DaCapo Chopin and SPECjbb. OppZGC limits heap usage when there is CPU capacity sufficient for additional collections, and avoids scheduling extra collections when they would substantially degrade performance. Overall, it reduces maximum heap usage for our DaCapo benchmarks by between 61% and 90%, on average, depending on configuration, with minimal impact on throughput and request latency compared to default ZGC.

arXiv abstract · PDF

Programming Languages and Compilers · primary corpus · published 2026-09-14T21:55:23Z
David Zhao Akeley, Yuka Ikarashi, Jonathan Ragan-Kelley
arXiv categories: cs.PL

Modern GPUs require not only SIMT-style parallelism but also software-managed concurrency between compute and data movement to reach maximum performance. Performance engineers must reason about subdividing work into the hierarchy of computation resources (threads, warps, warpgroups, blocks, clusters), and, in many cases, also must use asynchronous tensor core and memcpy instructions on different levels of the memory hierarchy (registers, tensor core accumulators, shared memory, global memory). Unlike CPUs, where out-of-order execution is managed by hardware and hidden from programmers, GPUs expose explicit instruction reordering to software through these asynchronous instructions. Well-established GPU programming languages generally offer either direct low-level control without safety guarantees (e.g., CUDA C++ inline assembly or intrinsics) or easier-to-analyze, high-level abstractions (e.g., Triton's tile-based model) that hide asynchronous instructions in the compiler backend, which may prevent performance engineers from maximizing performance by tuning critical details. We propose Exo-GPU, an imperative, low-level language that creates minimal abstraction over CUDA. Our key idea is to treat parallelism and synchronization as mere annotations on sequential code rather than as fundamental control flow primitives, enabling verification that these constructs do not alter the program semantics. The benefit is twofold: programmers can reason about code without hidden control flow or mutation, while allowing the Exo-GPU compiler to verify sequential-parallel equivalence--guaranteeing that parallel execution is functionally equivalent to its sequential interpretation. We used Exo-GPU to author GEMM kernels for the H100 GPU, using wgmma, TMA, and split-k. Our kernels achieved over 80% of theoretical peak on large problem sizes, in some cases outperforming the vendor-provided CUBLAS library.

arXiv abstract · PDF

Programming Languages and Compilers · primary corpus · published 2026-09-15T10:12:56Z
Shiqi Liu, Zeyu He, Letian Tao, Guojian Zhan, Jiaxin Gao, Feihong Zhang, Jingliang Duan, Wei Xiong, Kehua Sheng, Bo Zhang, Yang Guan, Shengbo Eben Li
arXiv categories: cs.LG, cs.AI, cs.PL

On-policy distillation (OPD) has emerged as an effective approach for large language model post-training, yet existing objectives face a trade-off between objective fidelity and optimization stability. Token-level OPD provides stable but local supervision, whereas sequence-level OPD captures future credit at the cost of horizon-dependent variance. We establish a unified temporal-credit view of these formulations, showing that practical token-level OPD can be interpreted as a temporal approximation to the sequence-level reverse-KL gradient. Building on this connection, we propose $\gamma$OPD (GammaOPD), which uses discounted temporal credit assignment to balance long-horizon supervision and optimization stability, while admitting a horizon-independent variance bound. We further develop a reward-compatible bounded mixing (RBM) mechanism for $\gamma$OPD that balances verifiable outcome feedback with the discounted OPD advantage to move beyond purely teacher-dependent optimization. Experiments on mathematical and code reasoning demonstrate consistent improvements over existing OPD methods across vanilla, size-mismatched, and multi-teacher distillation settings.

arXiv abstract · PDF

Programming Languages and Compilers · primary corpus · published 2026-09-16T10:24:35Z
Yuyue Wang, Zhenyu Zhang, Glenn Reinman, Huaicheng Li
arXiv categories: cs.AR, cs.PL

In-storage computing (ISC) reduces host--storage data movement by executing computation inside computational storage devices (CSDs). For multi-stage applications, realizing these benefits requires coordinating data placement, I/O--compute overlap, and device-resident state across the workflow, yet existing interfaces lack a unified abstraction for these decisions. We present Epic, an NVMe-based ISC stack that provides this abstraction by capturing data residency and lifetime in the program: location types declare logical residency, dataflow derives lifetimes for intermediate values and operation state within an invocation, and a keep primitive extends selected state across invocations. These semantics expose the complete offloaded workflow as a located, stateful dataflow. A storage-aware compiler transforms this workflow, performs movement-aware logical mapping and fusion, and exposes I/O--compute overlap; a runtime completes the plan using execution-time information, asynchronously binding work to physical resources and managing device-resident state. Across 12 file-scanning, database, and machine learning workloads, Epic is 1.6$\times$ faster on average than the strongest of five prior ISC systems, while achieving 4.2$\times$ speedup on average and up to 16.1$\times$ over the corresponding host baselines, and reducing application-side code by up to 14$\times$ in our implementations.

arXiv abstract · PDF

Programming Languages and Compilers · primary corpus · published 2026-09-16T13:41:42Z
Mingyuan Ma, Hu He
arXiv categories: cs.AR, cs.PL

Modern GPU kernels increasingly stress the instruction supply path, while fixed instruction containers can leave substantial footprint slack. This paper presents an automated encoding-synthesis framework that treats instruction layout as a constrained slot-assignment problem over a validated instruction-form field specification. The formulation separates semantic field identity from physical bit positions and supports tied, pinned, and free placement constraints, making it applicable when recurring decoded fields are not frozen by a public format contract. We instantiate the framework for NVIDIA SASS: raw public encoding text is normalized into a machine-readable specification, a SASS disassembler is validated against nvdisasm on 3.78M instructions, released as an open benchmark, and CP-SAT synthesis is used for fixed-length and variable-length encodings. On 142 Blackwell kernel inputs, variable-length synthesis reduces instruction footprint by 33%, with comparable reductions after re-synthesis on Ampere and Hopper; fixed-length synthesis on the same specification reduces decoder area by 16% against a decoder generated from the NVIDIA-observed 128-bit layout by the same generator and flow. Generated fetch/decode RTL meets 1.5 GHz in TSMC 22 nm with a replicated area delta of 0.12% of a GA100-class die; a same-node SRAM comparison shows the footprint reduction corresponds to about 9x this added logic in instruction-SRAM bit-cell area.

arXiv abstract · PDF

Programming Languages and Compilers · primary corpus · published 2026-09-16T20:47:32Z
Kabilan Mahathevan, Poorna Gunathilaka, Kirshanthan Sundararajah
arXiv categories: cs.PL, cs.AR, cs.PF

Sparse tensor contractions are bottlenecked by sparse-sparse coiteration loops that resist standard loop vectorization. We present Splyce, an auto-vectorization framework in MLIR that overcomes this through a dual-path execution model. By decoupling coordinate intersection from pointer management via selective predication, Splyce inherently eliminates data-dependent branches as a side effect, allowing modern superscalar engines to maximize instruction-level parallelism and hide memory latency. Beyond simple branch elimination, our transformation exposes independent computation that can be executed concurrently, increasing functional-unit utilization that would otherwise be constrained by sequential dependencies. Evaluation across foundational sparse tensor kernels demonstrates performance ranging from 1.96X to 2.86X on synthetic inputs, with consistent speedups sustained across a vast majority of irregular real-world datasets from the SuiteSparse collection. Ultimately, Splyce demonstrates that by converting unpredictable control-flow into a predictable data stream, compiler-driven speculation can effectively reconcile the memory efficiency of compressed storage with the execution-unit throughput of modern superscalar architectures.

arXiv abstract · PDF

Programming Languages and Compilers · primary corpus · published 2026-09-17T00:54:35Z
Yafan Huang, Guanpeng Li
arXiv categories: cs.DC, cs.AI, cs.PL

We propose PaRID (PaRallel Instruction Duplication), a software-directed soft error detection framework that requires only compile-time effort for multithreading parallel programs. PaRID addresses two key challenges: supporting parallel programs with mixed serial and parallel regions and minimizing performance overhead without relying on costly dynamic profiling. It combines parallel-aware code transformation with LLM-tuned performance modeling, guided by eight generalizable findings from an offline characterization study, to enable fast soft error detection in parallel applications. Evaluation on NPB benchmarks shows that PaRID reduces protection overhead from 162.79% to 59.84% on average and achieves up to 5x speedup while maintaining full error detection effectiveness.

arXiv abstract · PDF

Programming Languages and Compilers · primary corpus · published 2026-09-17T01:13:09Z
Priyadarshan Patil, Abhishek Basu, Vikas Reddy, Abhinav Gupta
arXiv categories: math.OC, cs.PL

Systems that turn natural-language descriptions of optimization problems into solver-ready code generally use a language model at every stage, including the final translation from a mathematical formulation into executable model-building code. We propose the ANVIL compiler architecture, where we separate these concerns. A language model is called only once, assisted by constraint guidance based on problem type, to produce a LaTeX formulation. A deterministic compiler then translates that LaTeX into code with no language model involvement. We describe the deterministic compiler (a normalizer, a recursive-descent parser producing a typed intermediate representation, analysis passes that bind symbols to a dataset schema, and a code emitter) and evaluate it on the 354 easy and hard problems of the NLP4LP benchmark. The compiler produced code for 329 of 354 formulations (92.9%), taking the deterministic path in every one of those cases and never falling back to model-generated code. Median compile time was below the 10ms resolution of our timer. Overall, our formulations achieved an accuracy of 98.9% over easy problems and 91.1% for hard problems. The gap between these compilation and accuracy figures is a key point of analysis, and we analyze it: formulations that failed to compile, problems that returned as infeasible, problems raising errors at runtime, and problems returning a wrong objective. Almost all of these errors trace back to the formulation rather than to the translation. ANVIL performs exceptionally well on leading benchmarks by using language models purely where they are effective, rather than as a catch-all tool.

arXiv abstract · PDF

Programming Languages and Compilers · primary corpus · published 2026-09-17T02:54:30Z
Paul Biberstein, Joseph Devietti, Mayur Naik
arXiv categories: cs.PL, cs.LG, cs.SE

Tensor programs, as used in deep learning models, are a prime target for optimization, as small performance improvements can have a large impact across training or inference workloads. However, such optimizations are complicated and can produce subtle bugs. Traditionally, correctness is assumed when differential testing against a reference on random inputs fails to reveal bugs. However, the inputs to these programs are massive tensors, and finding bugs can require generating extremely low likelihood inputs with precise relationships among their values. We propose a novel way to find bugs more consistently by flipping the quantifiers. Rather than generating a single input and checking all output tensor locations for equivalence, what if you could check a single output tensor location's equivalence for all inputs? We implement this idea in a system, \dirigo, by using a novel symbolic execution strategy. We demonstrate that \dirigo can find bugs effectively in a public dataset of 6,988 AI-written CUDA kernels that are all marked correct by differential testing. Of these, \dirigo finds 600 kernels that are actually buggy, and finds 97.3\% of those bugs within two minutes.

arXiv abstract · PDF

Programming Languages and Compilers · primary corpus · published 2026-09-19T13:14:42Z
Bo Joel Svensson, Benjamin Vedder
arXiv categories: cs.PL

LispBM is a Lisp dialect for microcontrollers and embedded systems. This paper is about the changes made to LispBM resulting from it being integrated into the VESC family of firmware and thus gaining a userbase. As a surprise to Author 1, the new users of LispBM wrote programs larger than ever imagined. This used up all available heap space and we were forced to find a way to evaluate Lisp programs partitioned across RAM and flash memory. This story and a couple more, like the one about the Lisp-image system for fast boots, are the core contribution of this paper. When the first versions of the VESC firmware with a built-in Lisp runtime system were released, there was some grumbling here and there about Lisp and its syntax, as expected. To our delight, most seemed very excited about a scripting language in the firmware. To the engineer and builder users, the choice of syntax seemed to matter less than the potential it opened up for them.

arXiv abstract · PDF

Programming Languages and Compilers · primary corpus · published 2026-09-19T14:07:01Z
Madhulatha Mandarapu, Sandeep Kunkunuru (VaidhyaMegha Private Limited, India)
arXiv categories: cs.DB, cs.PL

GQL (ISO/IEC 39075:2024) is the first international standard for a graph query language, and SQL/PGQ (ISO/IEC 9075-16:2023) embeds the same pattern-matching core, GPML, in SQL. Both fix a precise semantics for path patterns: four path modes, four selectors, quantified segments. What engines compute for those patterns has never been measured. Work on GQL is theoretical and runs no engine; cross-engine work measures performance and normalises the semantics away. We build an executable reference semantics for the GPML path core and gate it against the six worked answers printed in the standard's own reference exposition. We then run a 17-construct suite against six releases of five products - Kuzu, DuckPGQ, Neo4j at 5.26 and 2026.04, Memgraph, Apache AGE - scoring each cell as conforming, diverging, rejected, or inexpressible in that dialect. Nine of seventeen constructs draw more than one answer across the engines that accepted them. Of 26 disagreements, 15 are silent - the query runs, returns a different multiset, raises no error - a silence ratio of 0.58. Scoring each divergence against the path mode each engine's manual declares separates language from implementation: 9 of 15 are documented differences, 6 are departures from the standard the engine implements. A metamorphic layer needing no reference semantics finds 39 self-consistency violations, yielding two minimal defects. No engine we measured parses the order the standard's own examples are written in, except the authors' own, which added it after this suite reported the gap. Suite, semantics, reproducers and results are open source.

arXiv abstract · PDF

Programming Languages and Compilers · primary corpus · published 2026-09-20T04:03:33Z
Peishan Huang, Wenmeng Zhang, Yusen Chen, Zhenbang Chen
arXiv categories: cs.PL

The demand for synthetic training data is hindered by the sim-to-real gap, as current data-driven and LLM-based generators often produce physically implausible scenarios. To address this, we propose R2SGEN, a Real-to-Sim framework that synthesizes structured scenario programs from real-world data. To overcome the combinatorial explosion and intractability of monolithic Satisfiability Modulo Theories (SMT) encoding, we introduce a decoupled synthesis strategy. This approach separates the discrete structural program search from continuous geometric resolution using lightweight, atomic SMT constraints. Furthermore, we significantly accelerate the search process by integrating two tailored pruning mechanisms: Common Prefix Abstraction-based pruning for Breadth-First Search and Branch-and-Bound for Depth-First Search. We evaluate R2SGEN on 20 real-world scenes of varying complexity from the nuScenes dataset. Experimental results show that our method guarantees consistency with the input scene and produces substantially lower-cost programs than the LLM-based baselines under the evaluated inputs. Both proposed search paradigms exhibit complementary advantages, proving highly efficient and scalable for high-complexity synthetic data generation.

arXiv abstract · PDF

Programming Languages and Compilers · primary corpus · published 2026-09-20T17:17:01Z
Yusuke Izawa, Kota Hakamada
arXiv categories: cs.PL

Forth is a concatenative language whose words share one data stack across calls, with a depth and call effects that need not be known before execution. That leaves a meta-tracing JIT compiler with no stack location it can name: a cell is reached through the stack pointer, so its accesses stay in the compiled code, and declaring every cell of the stack array instead ties what the compiler carries to the capacity the array reserves rather than to the depth a program uses. We answer with a fixed-width window over the top of the stack, a shared spill holding every deeper cell, and a decoding function that joins the two, on top of which call-entry normalization and adaptive entry are policies. Decoding shows that all of them preserve the logical stack and that a trace exit rebuilds data-stack state bounded by the window's width, not by the stack's depth. RPyForth realizes this in an RPython interpreter covering Forth's Core word set, with two scalar fields and eight frame positions and no static stack-effect analysis, and RPyFactor realizes the same window for a subset of Factor. Exposing the window to the compiler, rather than merely caching cells in it, is what pays. With the layout and the call policy held fixed, annotating the window's fields makes eighteen Shootout kernels 1.44-1.45x faster and six Appbench applications about 1.60x faster on two x86-64 machines, and 1.42-1.56x in RPyFactor. How the window is shaped and whether calls normalize it matter much less, varying by program with no setting winning everywhere. As a complete system, RPyForth is faster than gforth-fast and SwiftForth on both suites and reaches 1.90-2.36x the speed of VFX Forth on the kernels, while the applications, whose stacks are deeper and whose calls are far more frequent, remain its weak point at 0.68-0.76x. All timings measure repeated execution of an already-loaded program.

arXiv abstract · PDF

Programming Languages and Compilers · primary corpus · published 2026-09-20T20:15:28Z
Lenore Mullin, Gaetan Hains
arXiv categories: cs.GL, cs.PL

This article argues that a central development in the history of computing is the mathematical evolution of addressing. During the three decades separating Kateryna Yushchenko's Address Programming Language (1958) from Lenore Mullin's A Mathematics of Arrays (1988), addressing evolved from a machine-level mechanism for locating data into a formal theory of indexing, reduction, and machine realization, passing through Kenneth Iverson's algebra of arrays and Philip Abrams' recognition of shape as an architectural resource. Mullin's theory establishes indexing itself, via the function {\psi}, as the primitive from which array operations compose, reduce to a Denotational Normal Form, transform into an Operational Normal Form, and realize on hardware through dimension lifting. Historical claims are sourced against primary material, with inferences flagged as such; mathematical claims are stated as identities; performance claims are marked validated, theoretically established, or provisional. The result links programming languages, array mathematics, and computer architecture in one account.

arXiv abstract · PDF

Concurrent and Cyberphysical Systems · cs.SE candidate · published 2026-09-14T10:08:48Z
Luca M\"uller, Qian Liu, Rolf Drechsler
arXiv categories: cs.AR, cs.SE

Recently, the use of Large Language Models (LLMs) for different tasks in the Electronic Design Automation (EDA) life-cycle has been studied extensively, but an integrated view is lacking. Specifications are the foundation of this life-cycle, but they suffer from ambiguity when written in natural language, which especially affects the quality of LLM output. Formal specifications mitigate these ambiguities, but they come with their own challenges. On the other hand, Controlled Natural Language (CNL) specifications can serve as a middle-ground, reducing ambiguity while retaining interpretability. In this work, we propose an integrated view on the use of LLMs for EDA and establish an LLM-enabled behavior driven hardware development workflow. We introduce and define Formal Verification Gherkin Scenarios (FV Gherkin Scenarios), unlocking CNL specifications as the foundation for formally verified hardware designs via Formal Property Verification (FPV). Experimental evaluation shows that our workflow is able to outperform other established LLM-based methods by 2.48x in functional correctness of generated Register Transfer Level (RTL) designs and by 2.54x in formal coverage of generated assertions for FPV.

arXiv abstract · PDF

Concurrent and Cyberphysical Systems · cs.SE candidate · published 2026-09-15T14:03:22Z
Laura Brand\'an Briones, Petra van den Bos, Marcus Gerhold
arXiv categories: cs.SE, cs.FL

In Model-Based Testing (MBT), test suites are generated automatically from a formal specification. The theory of testing real-time systems is rich, but often underused in practice, partly because applying the timed machinery demands expertise practitioners should not need. In prior work we addressed this for timed testing with a canonic lifting operator, which lets a modeller specify behaviour as plain labelled transition systems while implicitly obtaining the timed automata that express their quiescent behaviour (the explicit absence of outputs) with timers. This paper takes the next step: we show that our lifting still works when each component carries its own time-out on its own channel. This way, we introduce a multi-channel lifting. We show that it commutes with parallel composition, i.e. composing and lifting is the same as lifting first and then composing. We show that the MBT apparatus survives: conformance, test generation and verdicts are preserved by the lifting, on the testable traces that a time-out based tester can observe.

arXiv abstract · PDF

Concurrent and Cyberphysical Systems · primary corpus · published 2026-09-15T15:29:00Z
Serge Lechenne, Hugo Paquet
arXiv categories: cs.LO, math.CT

It is an established idea in concurrency theory that every Petri net admits an unfolding semantics. This is a denotational object that represents its domain of possible executions. Unfoldings play an important role in practical analysis and verification. This paper is concerned with the following well-known problem: while the unfolding resembles a universal construction in the category of Petri nets, it generally fails to satisfy the expected universal property. This is because the unfolding construction overlooks the net's internal symmetries. There are two solutions: make these symmetries explicit to obtain a weak universal property (one that holds only ''up to symmetry''); or break the symmetries by assigning individual identities to components of the net. We review these two solutions and establish, in each case, a universal unfolding of Petri nets to event structures. This paper demonstrates a 2-categorical approach to Petri net unfoldings. We show that each unfolding semantics determines a 2-categorical relative adjunction involving Petri nets and event structures. Viewed in this way, the above two constructions can be related formally via an appropriate morphism of adjunctions. We exhibit a 2-density property of event structures which implies that unfolding functors are essentially unique.

arXiv abstract · PDF

Concurrent and Cyberphysical Systems · primary corpus · published 2026-09-15T16:26:37Z
Pavlo Tokariev (Laboratoire I3S - COMRED, KAIROS), Julien Deantoni (UniCA, Laboratoire I3S - COMRED, KAIROS)
arXiv categories: cs.LO

Real-time and cyber-physical systems are developed through successive refinements from abstract requirements to platform deployments. While timing knowledge evolves throughout this process, existing stochastic real-time formalisms typically require uncertainty to be embedded from the outset or necessitate model reconstruction when new timing information becomes available, hindering iterative timing engineering. This paper presents a refinement-oriented timing specification framework built upon the Clock Constraint Specification Language (CCSL). It supports the progressive introduction of timing knowledge across three levels: logical timing relations, quantitative real-time constraints, and stochastic timing models. Instead of altering behavioural semantics, stochastic information is attached directly to timing quantities as a refinement. This enables implementation measurements and operational observations to be incorporated incrementally within a unified declarative framework. We implement our approach in an OCaml-based simulation tool and evaluate it on a simplified but representative Software-Defined Vehicle use case.

arXiv abstract · PDF

Concurrent and Cyberphysical Systems · primary corpus · published 2026-09-15T16:27:51Z
Pavlo Tokariev (Laboratoire I3S - COMRED, KAIROS), Yosri Ayari (Laboratoire I3S - COMRED, KAIROS), Julien Deantoni (UniCA, Laboratoire I3S - COMRED, KAIROS)
arXiv categories: cs.LO

Software-Defined Vehicles (SDVs) rely on middleware-based communication and hardware abstraction mechanisms that introduce temporal uncertainty affecting end-to-end timing guarantees. Previous work proposed probabilistic architectural models for early timing analysis, but the representativeness of these abstractions with respect to SDV implementations remained unclear. This paper presents an experimental framework combining probabilistic design-time timing analysis with a monitored Kuksa-based implementation. The same reaction-time analysis is applied both to simulation and implementation traces, enabling direct comparison between predicted and observed timing behaviour. We additionally introduce a comparison methodology separating conservative coverage from predictive fidelity of timing distributions. The results show that the proposed abstractions remain representative under different middleware load conditions while preserving conservative timing guarantees, supporting incremental timing verification approaches for SDV platforms.

arXiv abstract · PDF

Concurrent and Cyberphysical Systems · primary corpus · published 2026-09-15T21:00:45Z
Ali Ataollahi, Fatemeh Ghassemi, Eduard Kamburjan, Marjan Sirjani
arXiv categories: cs.PL, cs.LO

Tiny twins are compact behavioral models derived from timed actor models for selected observable messages. When a source model evolves, regenerating its tiny twin requires state-space exploration and reduction even if the relevant behavior is unchanged. We present a static analysis for Timed Rebeca that compares backward slices of Rebeca dependence graphs for a given set of observable message names. For the Zeno-free fragment with after annotations and no delay statements, we prove that slice equivalence implies weak timed bisimulation under the selected observations. This preserves observable actions and total elapsed time across internal transitions, allowing the existing tiny twin to be reused. We evaluate the implementation on ten benchmark models paired with revisions that preserve their observable slices. The cost of static comparison depends on the size of the graphs representing source statements and their dependencies, while tiny-twin generation depends on the number of reachable states and transitions. This difference is reflected in the measurements: static comparison takes less than one second using tens of megabytes of memory, while tiny-twin generation can take over an hour and use hundreds of gigabytes.

arXiv abstract · PDF

Concurrent and Cyberphysical Systems · primary corpus · published 2026-09-16T05:05:35Z
Yifeng Xiao, Pierluigi Nuzzo
arXiv categories: cs.AI, cs.LO

Large language model (LLM) agents augmented by tools can automate complex, multi-step tasks, such as web navigation, code generation, and workflow orchestration, by acting on external systems through tool calls. However, hallucinations, distributional instability, and adversarial manipulations in LLMs, and the irreversible consequences of certain tool calls can lead to harmful outcomes. Existing safeguards either grade recorded trajectories post hoc with stochastic LLM judges or block unsafe actions one call at a time, and no single deterministic artifact supports both roles. We present ContrAgent, a contract-based framework for symbolic temporal supervision of LLM agents. ContrAgent captures an agent's behavior as a sequence of tool calls and formalizes it as a trace over a fixed set of checkable predicates. It then specifies required behaviors using assume-guarantee contracts in linear temporal logic over finite traces (LTLf). Each contract is compiled to a deterministic finite automaton (DFA) that serves two roles: gating agent actions online and evaluating recorded traces offline. A contract library, acting as a reusable knowledge base, is maintained independently of the agent's model and can be applied across different agents within the same task domain. We show the effectiveness of our approach on four benchmarks spanning both roles, where ContrAgent matches state-of-the-art LLM-judge and rule-based guardrail baselines while producing deterministic, reproducible verdicts and, in the online mode, orders-of-magnitude lower per-call latency.

arXiv abstract · PDF

Concurrent and Cyberphysical Systems · primary corpus · published 2026-09-16T23:26:04Z
Cl\'ement Aubert (Augusta University), Gabriele Cecilia (Augusta University), Iain C. C. Phillips (Imperial College London), Irek Ulidowski (AGH University of Krak\'ow, University of Leicester)
arXiv categories: cs.LO

Among the different ways of approaching the semantics of process calculi, true-concurrency models stand out for their ability to highlight subtle interplays between events. At their heart lie three crucial relations: concurrency, causality and conflict. This paper shows that reversibility, when endowed with a notion of independence, provides a rich tooling to study and characterise these true-concurrency relations. First, we prove that systems admitting pre-reversibility (i.e., that can be extended with an independence relation satisfying some basic axioms) have a unique notion of independence, events, concurrency, causality and conflict. We then analyse the relationship between independence and the true-concurrency relations, establishing novel independence-based characterisations of causality and conflict. Our second series of contributions revolves around two concrete process calculi and two syntactic notions defined on their transition labels, namely independence and dependence; we prove that they partition connected transitions and characterise elegantly concurrency on adjacent transitions. This part of our development was machine-checked using the proof assistant Beluga. Last, we study how the key mechanism commonly used in reversible process algebra can be used as a proxy to retrieve causality and core independence on past events. We conclude by discussing how our results extend beyond reversible systems.

arXiv abstract · PDF

Concurrent and Cyberphysical Systems · primary corpus · published 2026-09-17T08:31:18Z
Pyrros Koussios, Benjamin J\"ager, John Hua Yao, Ajay Sridhar, Violet Xiang, Chenhao Li
arXiv categories: cs.CL, cs.AI, cs.LO

Characterizing LLM reasoning remains an open challenge, as many existing benchmarks isolate specific reasoning skills, rely on external knowledge, or are costly to extend. We introduce PetriBench, a compact, fully self-contained, and scalable benchmark for evaluating LLM reasoning over dynamic state spaces using Petri nets, a mature formalism for modeling real-world concurrent and distributed systems. PetriBench organizes reasoning into four task families varying by scope and temporal horizon, with Easy, Medium, and Hard levels generated by increasing structural complexity and evaluated against exact ground truth. Across a diverse set of proprietary and open-weight models, accuracy decreases consistently with difficulty, while harder instances expose increasingly distinct task-specific capability profiles. Additional analyses show that test-time compute improves performance but interacts differently with different reasoning tasks, and that procedural generation yields smooth scaling with structural complexity. Together, these results show that PetriBench provides a unified and extensible setting for probing the strengths, limits, and scaling behavior of LLM reasoning.

arXiv abstract · PDF

Concurrent and Cyberphysical Systems · primary corpus · published 2026-09-17T14:33:04Z
Antony R. Lee, Peter Ti\v{n}o, Iain B. Styles
arXiv categories: cs.LO, cs.DB, math.CT

Run two process-discovery algorithms on the same event log and they return two different pictures of the same process. Petri nets, causal nets, process trees and BPMN each rely on routing machinery of their own, and their only common ground is the traces they generate. A trace lists activities one after another, so it discards the concurrency the notations exist to express, and two models with identical trace languages can describe genuinely different processes. Whether two discovered models mean the same thing therefore has no notation-independent answer. We show that all four notations admit one canonical presentation, a signature recording a model's activities and the typed interfaces along which they compose, and nothing of the routing machinery. Four construction theorems establish this presentation notation by notation, so two models are compared in a form that each notation determines on its own. Signature equality implies trace equivalence and is strictly finer, separating genuine concurrency from interleaved choice, which a trace comparison cannot, and signature inclusion implies trace inclusion. In a recovery study on one object-centric log, the discovered causal net has exactly the ground-truth signature, while the discovered Petri net's signature strictly contains it and locates every behaviour the Petri net adds in its silent structure. The gain is largest for object-centric data, where a single log supports several notations at once. The four notations become one calculus, in which a translation between them is a claim that can be checked.

arXiv abstract · PDF

Concurrent and Cyberphysical Systems · primary corpus · published 2026-09-17T19:03:20Z
Harrison Bennett, Amin Farjudian
arXiv categories: cs.LO

Robustness analysis plays a central role in the verification and design of computational and hybrid systems, particularly when system behaviour depends continuously on parameters subject to perturbation. Existing domain-theoretic frameworks provide a principled foundation for reasoning about such perturbations via monotone maps on lattices of closed sets. However, these frameworks face significant limitations when the underlying state space is not locally compact, as is the case for the infinite-dimensional spaces that arise in analysis, machine learning, and control theory (e.g., $\ell_p$ and $L_p$ spaces). In these settings, the lattice of closed subsets fails to be continuous, and classical compactifications either sacrifice precision or lack computable structure. We propose Gromov's horofunction compactification as a new tool for robustness analysis over a class of separable metric spaces of practical importance, including separable reflexive Banach spaces. Given a metric space $\mathbb{S}$, we show that its horofunction extension yields a compact metric space together with a Lipschitz embedding, which enables robust approximations of monotone maps via Scott-continuous maps on the compactified domain. For separable spaces, the horofunction compactification is metrizable, which provides a path toward effective domain-theoretic constructions.

arXiv abstract · PDF

Logic Complexity and Formal Languages · primary corpus · published 2026-09-14T04:15:25Z
Shuai Tang
arXiv categories: math.LO

This paper introduces the Higher-Order Quadripolar Argumentation Framework (HQAF), which extends bipolar frameworks by allowing attacks and three types of supports---necessary, deductive, and evidential---to interact at higher order. In HQAF, each interaction may have as its source and target an argument, an attack, or a support. We provide a 3-valued semantics via adjacent complete labellings and equational systems, and define encoded semantics directly in propositional logics, mainly {\L}ukasiewicz three-valued logic for the 3-valued case and fuzzy logics based on continuous t-norms (G\"odel, Product, {\L}ukasiewicz) for the fuzzy case. Model equivalence between HQAF and its normal encoding is established. The fuzzy equational semantics is shown to be a specific formalism of the fuzzy encoded semantics, and ternarization connects fuzzy models to 3-valued complete labellings. The study is confined to non-set HQAF; collective interactions are reserved for future work.

arXiv abstract · PDF

Logic Complexity and Formal Languages · primary corpus · published 2026-09-14T08:37:19Z
Fredrik Engstr\"om, Juha Kontinen
arXiv categories: math.LO

The logic FOT is a team-based logic whose expressive power coincides with first-order logic at the level of both sentences and open formulas. In contrast to dependence and independence logics, which can define stronger second-order team properties, FOT is designed to capture exactly elementary team properties, modulo the empty team. In this paper we consider two modifications of FOT. First, we investigate essentially the inclusion atom free fragment of FOT. Our main result establishes quantifier elimination for the fragment in the empty signature. Second, we study an extension of FOT by the intuitionistic implication. The main conclusion is that adding this single connective increases the expressive strength so that every second-order sentence can be encoded by an open formula evaluated on the full team. Consequently, validity of formulas is equivalent to validity of full second-order logic.

arXiv abstract · PDF

Logic Complexity and Formal Languages · primary corpus · published 2026-09-14T12:26:55Z
J{\'e}rome Clech (Sciences Po)
arXiv categories: cs.LO

We study a conditional model of ontological free will in which a pre-act state structures several coherent global continuations without intrinsically distinguishing one as the future actualisation. The topos-theoretic component is formalised by a choice sheaf and by the action of automorphisms preserving the pre-act data: the absence of a fixed point rules out any natural equivariant selection. An act changes an unpointed object into a pointed one and reduces its symmetry group to a stabiliser. Independently, a causal algorithmic incompressibility axiom imposes nearly maximal online description complexity on the actual choices. Uniformly observable post-act traces then allow their reconstruction. We prove a conditional transfer result: such traces must carry asymptotically all the singularisation information unavailable in the pre-act regime, and no uniform Turing predictor computes the choices from causal histories alone. The formalism proves neither that human beings satisfy the model nor a separation of P from NP; it identifies a boundary at which prediction concerns the existence of a computable function rather than its time complexity.

arXiv abstract · PDF

Logic Complexity and Formal Languages · primary corpus · published 2026-09-14T18:08:37Z
Tikhon Pshenitsyn
arXiv categories: math.LO

We show that the satisfiability problem for Strategy Logic introduced by Mogavero, Murano, and Vardi is $\Pi^1_\infty$-complete, and, more strongly, computably isomorphic to true second-order arithmetic. The lower bound is established for the next-time Boolean-goal fragment of Strategy Logic. Consequently, Strategy Logic is not recursively axiomatizable, even with effectively defined $\omega$-rules.

arXiv abstract · PDF

Logic Complexity and Formal Languages · primary corpus · published 2026-09-15T08:04:30Z
Chad Nester
arXiv categories: math.CT, cs.LO

We construct an adjunction relating two approaches to modelling the planar lambda calculus: semi-closed operads and planar lambda-models. We use this to obtain a planar version of Scott's representation theorem.

arXiv abstract · PDF

Logic Complexity and Formal Languages · primary corpus · published 2026-09-15T16:03:28Z
Simon D\"oring, Daniel Neuen
arXiv categories: cs.DS, cs.DM, cs.LO

The classical Weisfeiler-Leman algorithm (also known as the $2$-dimensional Weisfeiler-Leman algorithm) is a simple combinatorial algorithm that was originally designed as a heuristic for the graph isomorphism problem. However, it has also numerous connections to other areas such as algebraic graph theory, logics, proof complexity, combinatorial optimization and machine learning. We prove that the classical Weisfeiler-Leman algorithm terminates after $5(n-1)$ iterations. This improves over the previous best upper bound of $O(n \log n)$ by Lichter, Ponomarenko and Schweitzer [LICS 2019], and asymptotically matches the known lower bound of $\Omega(n)$ by F\"urer [ICALP 2001]. Additionally, building on our results for the $2$-dimensional case, we obtain an improved upper bound of $O(n^{k-1}/(k-2)! + n^{k-2})$ on the number of iterations performed by the $k$-dimensional Weisfeiler-Leman algorithm, for every $k \geq 3$. Our arguments actually hold for a larger class of sequences of colorings of $k$-tuples; in this larger class our upper bounds are essentially tight for all $k \geq 3$.

arXiv abstract · PDF

Logic Complexity and Formal Languages · primary corpus · published 2026-09-16T02:51:09Z
Daniel Quigley
arXiv categories: cs.CL, cs.LG, cs.LO

We characterize when compressed vector representations admit exact linear or affine readouts of a finite lexicon's truth conditions: one fixed map per predicate, sending each entity vector to the corresponding truth vector. A necessary and sufficient row-space condition determines existence; the augmented truth matrix has rank r, giving minimum dimension r in the linear case, and r-1 in the affine. Exact readouts return values in a shared truth basis on which Boolean connectives act unchanged; separability alone requires an intervening threshold. For binary relations, exact bilinear readout of identity or strict total order requires linearly independent entity vectors. Experiments with GloVe and word2vec distinguish exact affine recovery, linear separability, and held-out prediction: most predicates are strictly separable, but none admits an exact affine readout from the pretrained embeddings. Supervised transductive training attains exact affine recovery to numerical precision at every tested dimension meeting the bound. At the embeddings' original dimension, geometries constrained to exact linear recovery retain 98-99 percent of the pretrained variance on the feature norms, and 80-83 percent on the WordNet lexicon.

arXiv abstract · PDF

Logic Complexity and Formal Languages · primary corpus · published 2026-09-16T11:14:35Z
Stefan G\"oller, Amaldev Manuel
arXiv categories: cs.CC, cs.FL, cs.LO

We study the circuit complexity of regular languages in terms of unbounded fan-in Boolean circuit families. We characterize the regular languages of constant circuit complexity in terms of the one-variable fragment of first-order logic with regular predicates, in terms of the pseudovariety of stamps $\mathbf{QEJ}_\mathbf{1}$, suitable word congruences and regular expressions. We analogously characterize the neutral letter regular languages of constant circuit complexity. Our lower bound result implies that the class of regular languages of sublogarithmic circuit complexity coincides with the one of constant circuit complexity. In addition we show that deciding whether a regular language, given as a nondeterministic finite automaton, has constant circuit complexity is $\mathbf{PSPACE}$-complete. We introduce a strong notion of reduction, called rational truth-table reduction, that is tailored towards algebraically defined classes of languages. We show that, for a class of functions we call mild, rational truth-table reductions preserve both upper and lower bounds on circuit complexity. We show that the class of regular languages, whose circuit complexity is bounded by a mild function, is in fact a length-multiplying variety of languages. Slightly extending the class of regular languages of constant circuit complexity, we analogously characterize the class of regular languages that are in the pseudovariety $\mathbf{QEACom}$. For these we derive logarithmic circuit complexity upper bounds.

arXiv abstract · PDF

Logic Complexity and Formal Languages · primary corpus · published 2026-09-16T16:11:26Z
Steffen van Bergerem, Nicole Schweikardt
arXiv categories: cs.LO

For every effectively nowhere dense class $\mathcal{C}$ of relational structures, we present an algorithm that runs an almost-linear-time preprocessing step on a given structure $\mathcal{A} \in \mathcal{C}$ and a first-order formula $\phi(x_1, \dots, x_k, y_1, \dots, y_\ell)$. After the preprocessing, whenever given a tuple $\bar{v} \in A^k$, the algorithm computes the number of tuples $\bar{w} \in A^\ell$ that satisfy $\mathcal{A} \models \phi(\bar{v}, \bar{w})$ in constant time. Building on this, we provide an algorithm for constant-time query answering and constant-delay enumeration after almost-linear-time preprocessing for the recently introduced logic clique-guarded first-order logic with counting (cgFOC) on effectively nowhere dense classes. This generalises the testing and enumeration results for first-order logic [Schweikardt, Segoufin, and Vigny, JACM 2022] and the evaluation result for the first-order logic with counting FOC1 [Grohe and Schweikardt, PODS 2018] on nowhere dense classes.

arXiv abstract · PDF

Logic Complexity and Formal Languages · primary corpus · published 2026-09-17T13:59:13Z
Toghrul Karimov, Joris Nieuwveld, Jo\"el Ouaknine
arXiv categories: cs.LO, cs.FL

We develop a new framework for proving the undecidability of first-order theories of structures of the form $\langle \mathbb{N}; +, P \rangle$, $\langle \mathbb{N}; <, f \rangle$, and $\langle \mathbb{N}; +, f\rangle$, where $P \subseteq \mathbb{N}$ and $f \colon \mathbb{N} \to \mathbb{N}$. It is based on the recent proof of Hieronymi and Schulz that the first-order theory of $\langle \mathbb{N}; +, \{2^n \colon n \in \mathbb{N}\}, \{3^n \colon n \in \mathbb{N}\}\rangle$ is undecidable, and capable of transforming various randomness results about integer sequences into undecidability proofs. We apply our method to a large class of integer linear recurrence sequences, as well as various special functions, in particular showing that the first-order theories of $\langle \mathbb{N}; +, \{u_n \colon n \in \mathbb{N}\} \cap \mathbb{N}\rangle$, $\langle\mathbb{N}; <, n \mapsto \max\{0,u_n\}\rangle$, and $\langle \mathbb{N}; <, \phi\rangle$ are undecidable, where $(u_n)_{n\in\mathbb{N}}$ is any integer LRS with exactly two non-repeated dominant roots satisfying a non-degeneracy assumption, and $\phi$ is Euler's totient function.

arXiv abstract · PDF

Logic Complexity and Formal Languages · primary corpus · published 2026-09-18T04:51:24Z
Eiji Yamada
arXiv categories: cs.LO

In this paper, we define a formula $\varphi$ to be unbelievable if $\Box\varphi$ is unsatisfiable, and unknowable if $\Box\varphi\land\varphi$ is unsatisfiable. We then analyze the sources of unknowability and unbelievability in different classes of frames K, KD, KD45, and S5. We first show that any unbelievable formula is a fixed point of the Moore function defined by $f(\varphi)=\varphi\land\lnot\Box\varphi.$ Our main result shows that in S5, the static notions of unknowability and unbelievability in epistemic logic, and the dynamic notions of always informativeness and eventual self-refutation in dynamic epistemic logic are all equivalent to ``Moorean phenomena.'' We also generalize the result to the multi-agent case, showing that although all unknowable formulas still manifest Moorean phenomena, new mechanisms arise due to their interactive nature. Finally, we briefly analyze whether the Brandenburger-Keisler paradox in epistemic game theory can be considered Moorean.

arXiv abstract · PDF

Logic Complexity and Formal Languages · primary corpus · published 2026-09-18T09:53:18Z
Lei Li, Jialiang Yan
arXiv categories: cs.LO, cs.SI, math.LO

Filter bubbles can be understood as configurations characterized by within-group proximity and separation from outsiders. Personalized feeds may form or preserve such configurations. We develop hybrid-style logics for reasoning about filter bubbles. The static logic characterizes bubble-shaped configurations, while its dynamic extension captures their formation and persistence under personalized feeds. We provide sound and strongly complete axiomatizations for the static and dynamic logics and prove their decidability.

arXiv abstract · PDF

Logic Complexity and Formal Languages · primary corpus · published 2026-09-18T13:35:59Z
Takuma Imamura
arXiv categories: math.LO, cs.LO

Let $B$ be the bluebird combinator with reduction rule $Bxyz \to_{w} x\left(yz\right)$, let $M$ be the mockingbird combinator with reduction rule $Mx \to_{w} xx$, and let $I$ be the identitybird combinator with reduction rule $Ix \to_{w} x$. For a fixed variable $x$, we construct an invariant $\mathrm{Tr}_{x}\left(u\right)$ of a $BMI$-term $u$ with respect to $\to_{w}$. This invariant traces the occurrences of $x$ in the leftmost-innermost reduction sequence of $u$. We then prove that $\mathrm{Tr}_{x}\left(Yx\right) \neq \mathrm{Tr}_{x}\left(x^{r}\left( Yx \right)\right)$ for every $x$-free $BMI$-term $Y$ and every $r\geq 1$. Consequently, there exists no fixed-point combinator in $BMI$-combinatory logic under weak equivalence. This provides a negative answer to the problem posed by Smullyan in 1985.

arXiv abstract · PDF

Logic Complexity and Formal Languages · primary corpus · published 2026-09-19T22:07:19Z
Xin Li, Hanlin Ren, Yan Zhong
arXiv categories: cs.CC, cs.LO

For a propositional proof system $\mathcal{P}$ and a polynomial-time function $G: \{0, 1\}^n \to \{0, 1\}^N$ ($N > 10n$), we say that $G$ is a *proof complexity generator* against $\mathcal{P}$ if $\mathcal{P}$ cannot efficiently prove the (suitably encoded) statement "$y\not\in\mathrm{Range}(G)$" for every $y \in \{0, 1\}^N$, and $G$ is a *demi-bits generator* against $\mathcal{P}$ if $\mathcal{P}$ cannot efficiently prove the statement "$y \not\in\mathrm{Range}(G)$" for a noticeable fraction of $y \in \{0, 1\}^N$. As can be seen from the definitions, proof complexity generators are qualitatively stronger objects than demi-bits generators. Our main result is that, perhaps counter-intuitively, every demi-bits generator "contains" exponentially many proof complexity generators. In fact, a random subset of output bits of a demi-bits generator forms a proof complexity generator with constant probability. This result is an extremely simple corollary of Pajor's Lemma (a strengthening of the well-known Sauer--Shelah Lemma). This result allows us to exhibit the hardness of the Range Avoidance problem ($\text{Avoid}$) in several new, restricted settings of interest. Along the way, we introduce the notion of *zero-error disperser families* that can transform demi-bits generators into proof complexity generators, and show that this family can be computed by projections (i.e., without any circuit complexity overhead). Using a different instantiation of this family, we construct proof complexity generators from *barely non-trivial* demi-bits generators $G: \{0, 1\}^n \to \{0, 1\}^N$, where the number of hard-to-prove statements of the form "$y \not \in \mathrm{Range}(G)$" just slightly exceeds $2^n$ (which is the number of *false* statements of this form).

arXiv abstract · PDF

Logic Complexity and Formal Languages · primary corpus · published 2026-09-20T19:44:00Z
Julian D'Costa
arXiv categories: cs.LO

Given a rational matrix $A$, is every sufficiently large power $A^n$ entrywise nonnegative? We prove that this problem is decidable in deterministic polynomial time. This is in contrast with deciding eventual nonnegativity of a single prescribed entry sequence $(A^n)_{ij}$, which amounts to the Ultimate Positivity Problem for linear recurrence sequences, whose decidability is open. The previous decidability procedure (D'Costa, Ouaknine and Worrell, STACS 2024) splits the matrix powers into residue classes modulo a torsion exponent $D$ whose value can be exponential in the input size. We show that it is sufficient to check a single progression $A^{Dk+1}$: the exponents $n$ with $A^n \geq 0$ are closed under addition, and two consecutive exponents of the progression are coprime, so they generate every sufficiently large exponent. Along the progression, eigenvalues are grouped by their common $D$th power, and the required coefficients for each group are computed without forming $A^D$, any $\lambda^D$, or a splitting field: each summand is evaluated in its own root field $\mathbb{Q}(\lambda)$, and Galois equivariance keeps the degree and height of every class sum polynomially bounded, enabling certified zero and sign tests. The same algorithm with one case rejected decides eventual positivity, and a variant decides whether the matrix has any nonnegative power at all.

arXiv abstract · PDF

Set Theory Model Theory and Computability · primary corpus · published 2026-09-14T04:09:27Z
Junhao Chen, Jie Zou
arXiv categories: math.LO, math.CO

The Borel distinguishing number $D_B(\mathcal{G})$ of a Borel graph $\mathcal{G}$, recently introduced by Bilge and Kaya, is the minimum number of colors required to break the symmetry of $\mathcal{G}$ in a Borel way. In this paper, we investigate the Borel distinguishing number of Schreier graphs induced by the free part of the shift action $\Gamma \curvearrowright n^\Gamma$. We prove that $D_B(\mathcal{G})\le n+1$ for $\Gamma=\mathbb{Z}^d$ equipped with the standard generators. Moreover, we show that $D_B(\mathcal{G})\ge n+1$ if $ \Gamma$ is amenable and $ \{\gamma \in \mathrm{Aut}(\mathrm{Cay}(\Gamma,S)) \mid \gamma(e) = e \}$ is non-trivial. We also show that $D_B(\mathcal{G})$ is finite if $\Gamma$ is finitely generated, and give some applications of our results. These results answer some questions raised by Bilge and Kaya.

arXiv abstract · PDF

Set Theory Model Theory and Computability · primary corpus · published 2026-09-14T11:00:20Z
Franziska Jahnke, Margarete Ketelsen, Floris Vermeulen
arXiv categories: math.LO, math.AC, math.NT

We show that for any henselian valued field of mixed characteristic $(0,p)$, the (existential) $\mathcal{L}_{\mathrm{val}}$-theory of the valued field is determined by the (existential) theory of the value group in $\mathcal{L}_{\mathrm{oag}}$ with a constant for $v(p)$ and the (existential) theory of the residue ring $\mathcal{O}_v/(p)$ in an expansion $\mathcal{L}_{\mathrm{Witt}}$ of the language of rings, provided $\mathcal{O}_v/(p)$ is semi perfect. We moreover show that the $\mathcal{L}_{\mathrm{Witt}}$-structure on $\mathcal{O}_v/(p)$ is $\mathcal{L}_{\mathrm{ring}}$-definable using constants, and that this is exactly the structure induced on $\mathcal{O}_v/(p)$ by the ambient valued field. As a consequence, we obtain a relative quantifier elimination result (eliminating $K$-quantifiers) in a suitable language for the theory of roughly deeply ramified henselian valued fields of mixed characteristic $(0,p)$.

arXiv abstract · PDF

Set Theory Model Theory and Computability · primary corpus · published 2026-09-15T09:14:39Z
Hiroshi Sakai
arXiv categories: math.LO

We prove that the Subcomplete Forcing Axiom is consistent with $\diamondsuit^+$.

arXiv abstract · PDF

Set Theory Model Theory and Computability · primary corpus · published 2026-09-15T10:00:17Z
Tumadhir Alsulami, Marcel Jackson, Michael Kinyon
arXiv categories: math.LO

An algebra with binary operations $+,\cdot,\uparrow$ and constant $1$ is called an HSI algebra if it satisfies the basic commutative semiring laws for $+,\cdot,1$ on~$\mathbb{N}$ as well as the familiar index laws for exponentiation $\uparrow$. These basic axioms, known as the ``High School Identities'' are known to be incomplete, and an algebra satisfying $\HSI$ but failing an equation valid on ${\bf N}:=\langle \mathbb{N};+,\cdot,\uparrow,1\rangle$ is called a \emph{Gurevi\v{c} algebra}. It is currently unknown if there is an algorithm to recognise finite Gurevi\v{c} algebras, and the best current result is that there exists a 12-element Gurevi\v{c} algebra, and that none of the five 2-element HSI algebras are Gurevi\v{c} algebras. We explain how the work of Alex Wilkie can be used to provide an algorithm for deciding validity of the equational laws of $\langle \mathbb{N};+,\cdot,\uparrow,1\rangle$, and use this to show that multiplicatively-idempotent HSI algebras satisfy all valid laws of $\langle \mathbb{N};+,\cdot,\uparrow,1\rangle$. As consequences of this result, we show that all 44 HSI algebras on 3 elements lie in the variety of $\langle \mathbb{N};+,\cdot,\uparrow,1\rangle$ (that is, are not Gurevi\v{c} algebras), as well as 597 of the 657 models on 4 elements and 11158 of the 13577 models on 5 elements. A further consequence is that every Brouwerian lattice lies in the variety of $\langle \mathbb{N};+,\cdot,\uparrow,1\rangle$ (up to a simple term equivalence), showing that the variety of $\langle \mathbb{N};+,\cdot,\uparrow,1\rangle$ has continuum many subvarieties. The constant-free signature is also explored, and it is shown that in this case all $2$-element models of the constant-free High School Laws satisfy all valid constant-free laws in $\langle \mathbb{N};+,\cdot,\uparrow\rangle$.

arXiv abstract · PDF

Set Theory Model Theory and Computability · primary corpus · published 2026-09-15T12:21:29Z
Jindrich Zapletal
arXiv categories: math.LO

If ZFC is consistent, then so is ZF+DC+BPI+there is no Vitali set.

arXiv abstract · PDF

Set Theory Model Theory and Computability · primary corpus · published 2026-09-15T13:17:57Z
Martin Goldstern, Tatsuya Goto
arXiv categories: math.LO

We introduce d-minimal and b-minimal extensions, two weakenings of minimality based respectively on eventual domination and infinitely often domination. We prove that the generic extensions obtained by the full Mathias forcing and by Mathias forcing relative to Ramsey ultrafilters are d-minimal, whereas Hechler extensions are b-minimal. We also construct a d-minimal extension that is weakly $\omega^\omega$-bounding but neither minimal nor $\omega^\omega$-bounding, and realize every constellation of these properties compatible with their natural implications.

arXiv abstract · PDF

Set Theory Model Theory and Computability · primary corpus · published 2026-09-15T13:39:39Z
Ruijun Wang
arXiv categories: math.LO

We prove that every bounded-to-one action of a finitely generated commutative monoid has finite asymptotic dimension, without a freeness assumption. If the group completion has torsion-free rank $r$, we give an explicit upper bound $(3^{r+1}-3)/2$. This answers a question of Shinko, Weilacher and Yu, and extends a theorem of theirs.

arXiv abstract · PDF

Set Theory Model Theory and Computability · primary corpus · published 2026-09-15T20:46:54Z
David Meretzky
arXiv categories: math.LO

This paper gives results which relate the definable Galois theory of [28] to the definable Galois cohomology of [18] in the setting of a totally transcendental first order theory. Firstly, we show that under some common assumptions the definable Galois cohomology of the extrinsic definable Galois group associated to fixed internality data classifies the number of definable Galois extensions inside a copy of the prime model. This generalizes a well-known result for Picard-Vessiot differential Galois theory shown originally via tannakian methods [3]. We then collate some triviality results for differential Galois cohomology [21] and recent results on iterated Picard-Vessiot extensions [10] [15] to give colimit formulas for differential Galois cohomology. Precisely, for an ordinary differential field $K$ of characteristic $0$ and a linear differential algebraic group $G$ over $K$, the differential Galois cohomology $\text{H}^1_{\delta}(K,G)$, is given by a colimit over the family of normal closures of iterated Picard-Vessiot extensions of $K$ of finite type. We then propose a new notion of boundedness for a differential field. We finally show that the minimal closure of a set of parameters $A$, the intersection of all elementary embeddings of a copy of the prime model over $A$ into itself, contains all of the definable Galois cohomological information for definable groups over $A$ satisfying also some strong but common conditions. Lastly, we give some colimit formulas for definable Galois cohomology and propose a model-theoretic definition of a bounded set of parameters.

arXiv abstract · PDF

Set Theory Model Theory and Computability · primary corpus · published 2026-09-16T01:28:04Z
Xuanheng Zhao
arXiv categories: math.LO

A set B is AEWG if almost every set computes a weakly 1-B-generic. Extending two results of Hirschfeldt, Jockusch and Schupp, we prove that there is an AEWG superhigh r.e. set and every low2 r.e. set is AEWG.

arXiv abstract · PDF

Set Theory Model Theory and Computability · primary corpus · published 2026-09-16T01:44:10Z
Xuanheng Zhao
arXiv categories: math.LO

We prove that there is a 1-generic set which computes a uniformly almost everywhere dominating function. The proof has two ingredients: a Baire space version of the Chong-Downey Sigma01-density criterion and the forcing of Cholak-Greenberg-Miller.

arXiv abstract · PDF

Set Theory Model Theory and Computability · primary corpus · published 2026-09-16T14:29:41Z
Piotr Kowalski
arXiv categories: math.LO

We consider the Kolchin-generic complete $1$-type of the inviscid Burgers equation $Dx=x\partial x$ in a differentially closed field of characteristic zero with two commuting derivations. We prove that this type has Lascar rank $1$ and Morley rank $\omega$.

arXiv abstract · PDF

Set Theory Model Theory and Computability · primary corpus · published 2026-09-17T03:49:00Z
Keith A. Kearnes, Andrew Moorhead, Agnes Szendrei
arXiv categories: math.RA, math.CT, math.LO

A variety $\mathcal{V}$ is called a Schreier variety if every subalgebra of a $\mathcal{V}$-free algebra is a $\mathcal{V}$-free algebra. We use ideas from Tame Congruence Theory to classify locally finite Schreier varieties. One version of the classification theorem states that a locally finite variety $\mathcal{V}$ is a Schreier variety if and only if (i) every finite algebra in $\mathcal{V}$ is a $\langle 0,1\rangle$-minimal algebra and (ii) if $\mathcal{V}$ has a constant $1$-ary term operation, then $\mathcal{V}$ also has a constant $0$-ary term operation.

arXiv abstract · PDF

Set Theory Model Theory and Computability · primary corpus · published 2026-09-17T20:07:05Z
David Gonzalez, Java Darleen Villano, Jos\'e Jerem\'ias Valenzuela Morales
arXiv categories: math.LO

Given a noncomputable, computably enumerable set $D$, we construct a computable structure $G$ such that any two computable copies of $G$ are computably isomorphic while there are two $D$-computable copies of $G$ that are not $D$-computably isomorphic. In other words, $G$ is computably categorical, but not computably categorical relative to $D$. Conversely, we construct a computable structure that is not computably categorical, but is computably categorical relative to $D$. These results differ from those in the literature regarding computable categoricity and its relativiziations because the degree $D$ is given instead of constructed. Our work negatively answers a question of Downey, Harrison-Trainor and Melnikov in the computably enumerable case.

arXiv abstract · PDF

Set Theory Model Theory and Computability · primary corpus · published 2026-09-18T03:55:50Z
Anton Bernshteyn, Edward Hou, Forte Shinko, Felix Weilacher
arXiv categories: math.LO, math.CO

Let $G$ be a Borel digraph with maximum out-degree $d \in \mathbb{N}$. We show that $G$ admits a random Borel $(2d+1)$-coloring for which every edge is almost surely not monochromatic. This gives a simpler proof of a recent result of Pelayo-G\'omez: such a graph $G$ admits a measurable proper $(2d+1)$-coloring with respect to any Borel probability measure on $V(G)$. Our proof is an adaptation of Pelayo-G\'omez's proof to the randomized Borel setting.

arXiv abstract · PDF

Set Theory Model Theory and Computability · primary corpus · published 2026-09-18T04:30:04Z
Bilge K\"oksal, Mateusz Lichman, S{\l}awomir Solecki
arXiv categories: math.LO

We give a proof, that does not rely on analytic determinacy, of the existence of an idealistic analytic equivalence relation with Borel classes that is not classwise Borel isomorphic to an orbit equivalence relation. This result answers a question of Becker, and Calderoni and Motto Ros. Our proof proceeds through an analysis of Borel complexity of certain sets of countable rooted trees defined via the notion of the Lusin derivative.

arXiv abstract · PDF

Order Topology and Mathematical Foundations · primary corpus · published 2026-09-16T02:31:15Z
Xiaoquan Xu
arXiv categories: math.LO

We prove that the Scott topology commutes with arbitrary products of countably presented frames and that every such product has a sober Scott space. In particular, this holds for arbitrary products of countable complete Heyting algebras. For a family of consonant spaces, Scott-product compatibility of their open-set lattices is equivalent to consonance of their topological sum. Countable generation does not suffice: a countably generated spatial frame can have a non-sober Scott space and fail the product identity for its square. We also show that the cardinal spectra of Scott non-sober frames and spatial frames are upward closed and, under the Continuum Hypothesis, consist of all uncountable cardinals. Finally, every Artinian $T_0$ web space is a $B$-space; if it is also a $d$-space, it carries the Scott topology of an algebraic dcpo. Consequently, every Artinian meet-continuous dcpo is algebraic. This yields a dichotomy theorem: a dcpo with a non-sober Scott space must fail meet continuity or Artinianity.

arXiv abstract · PDF

Order Topology and Mathematical Foundations · primary corpus · published 2026-09-16T09:26:18Z
Sam Sanders
arXiv categories: math.LO

For various reasons, higher-order objects are often studied in mathematical logic via second-order `codes' or `representations'. An important example hailing from real analysis and topology is provided by open sets, which are represented by unions $\cup_{n\in \mathbb{N}}I_{n}$ where each $I_{n}$ is a basic open interval. Now, Montalb\'an has recently highlighted the importance of robustness of logical systems in Reverse Mathematics (abbreviated RM). It is then a natural RM-question whether basic properties of open sets are robust under slight modifications of the coding of open sets. Here, we study the representation where $I_{n}$ as above is \emph{either} an open interval \emph{or} the union of two such intervals \emph{but} we cannot decide which one. Under this slight variation of the usual coding, basic properties of open and closed sets readily imply the relatively strong system ATR$_{0}$ from RM. Moreover, we obtain equivalences for the former properties and the \emph{enumeration principle}. The latter states that countable sets can be enumerated and boasts many equivalences from Fourier analysis. Along the way, we investigate the RM-properties of the closure, interior, and boundary of sets of reals, a study interesting in its own right.

arXiv abstract · PDF

Order Topology and Mathematical Foundations · primary corpus · published 2026-09-17T02:57:29Z
Xiaoquan Xu, Wei Ji
arXiv categories: math.LO

We prove that every countable meet-continuous lattice is Scott sober. For any family of such lattices, the Scott topology on the product equals the product of the factor Scott topologies, and the product Scott space is sober. These results answer affirmatively Questions 7.1 and 7.2 of Xu (arXiv:2609.18032v1), extending the countable-frame results beyond finite distributivity. A diagonal argument on meet coordinates extracts directed punctured intervals from nonprincipal ideals. Join translates of these intervals form a countable family detecting Scott openness and yield Scott open rectangles by successive finite choices. We also show that the cardinal spectrum of Scott non-sober meet-continuous lattices is upward closed and, under the Continuum Hypothesis, consists of all uncountable cardinals.

arXiv abstract · PDF

Order Topology and Mathematical Foundations · primary corpus · published 2026-09-17T12:31:14Z
Gabriel Fernandes, Renan Maneli Mezabarba, Vinicius de Oliveira Rodrigues
arXiv categories: math.LO

We prove that, in Zermelo--Fraenkel set theory with the axiom of Foundation removed, the statement that every vector space has a basis implies the Axiom of Choice, concluding that the classical equivalence between $\AC$ and the existence of bases does not require the Axiom of Foundation. More specifically, we prove that if every vector space over a field of characteristic zero has a basis, then $\AC$ holds. This result extends to set theory with atoms.

arXiv abstract · PDF

Order Topology and Mathematical Foundations · primary corpus · published 2026-09-17T13:22:39Z
Nicolai Vorobjov
arXiv categories: math.AG, math.CA, math.LO

We prove a generalization of the version, due to A. Gabrielov, of the {\L}ojasiewicz inequality for not necessarily restricted semi-Pfaffian sets. Unlike the most variants of the {\L}ojasiewicz inequality, it describes the rate of growth of a Pfaffian function on a semi-Pfaffian set $X$ not only in a neighbourhood of its zero set in the domain of $X$ but also in a neighbourhood of zeroes on the boundary of the domain. Gabrielov's version is essentially one-dimensional, we generalize it to a multidimensional case.

arXiv abstract · PDF

Order Topology and Mathematical Foundations · primary corpus · published 2026-09-17T13:32:08Z
Christopher Sorg
arXiv categories: math.LO, cs.NA, math.NA

The Solvability Complexity Index (SCI) provides an extensional limit-height formalism for recovering a target map $\Xi$ from finite samples of an evaluation interface $\Lambda$ by finite-height towers of pointwise limits. At first sight this sounds like a typical Type-2 question, so it seems natural to ask how deep and rich the connection of SCI approximation questions and Type-2 computability questions is. This note aims to explain this connection further with explicit examples mostly from the literature.

arXiv abstract · PDF

Order Topology and Mathematical Foundations · primary corpus · published 2026-09-17T16:41:02Z
Clarence Lewis Protin
arXiv categories: math.LO

In this paper we propose a reconstruction of the theory of multiple generality in Stoic Logic using the Natural Term Logic (NTL) developped by the author in \cite{ntl}. Contrary to a frequent misconception, it can be shown conclusively, based on the available evidence, that Stoic logic was far more than a mere propositional logic (we further argue that even identifying the Stoic conditional with any type of propositional connective is misleading). Its more general and complex logical theory - and notable the treatment of multiple generality - were rather patterned after the logico-syntactic mechanisms of natural language (subject to a regimentation which recalls Polish notation) rather than the variable-based quantifier logic of the modern Fregean tradition. NTL is likewise is a variable-free formal framework which captures the core syntactic and logic mechanisms of natural language (and notably a large array of features involving intensionality and anaphoric constructions) and includes as a particular case Quine's reformulation of predicate logic in \cite{quine}. Bobzien and Shogry \cite{bobzienshogry} have presented abundant evidence and arguments for the case that quantified conditionals and multiple generality were treated by the Stoics through a disambiguifying regimentation of syntax using indefinite pronouns and anaphoric constructions involving such pronouns. There are however some patent difficulties involving how exactly the equivalent of universal quantification was treated. In this paper we propose, in light of the above considerations, a formal reconstruction of the Stoic logic of multiple generality based on a variant of NTL.

arXiv abstract · PDF

Order Topology and Mathematical Foundations · primary corpus · published 2026-09-17T16:43:27Z
Gal Binyamini, Oded Carmon, Dmitry Novikov
arXiv categories: math.LO, math.AG, math.NT

We develop a complex-analytic approach to the model theory of the (real) unrestricted exponential. As a consequence we derive sharp forms of many of the foundational results for the structure ${\mathbb R}^\text{RE}_{\exp}$ (and more general structures). In particular we establish sharp o-minimality, a sharp form of Wilkie's theorem of the complement, a sharp form of Wilkie's conjecture and a sharp form of piecewise definability by terms. Our approach is based on a complexification of the LE-preparation theorem of Lion--Rolin. We also develop a parallel complex theory for ${\mathbb R}_\text{an,exp}$, proving for example that the rational points of height $H$ on a nowhere-dense definable set can be interpolated by an algebraic hypersurface of degree $\text{poly}(\log H)$. This generalizes a theorem of Cluckers--Pila--Wilkie who proved the same statement for ${\mathbb R}_\text{an}^\text{pow}$.

arXiv abstract · PDF

Order Topology and Mathematical Foundations · primary corpus · published 2026-09-17T16:52:41Z
M. Ali Khan, Arthur Paul Pedersen, Maxwell B. Stinchcombe
arXiv categories: math.PR, math.FA, math.GN, math.LO, math.ST, stat.TH

We revisit the analysis of Bayesian convergence to the truth under finite additivity in a recent paper by Nielsen (J. Philos. Logic, 2021, doi:10.1007/s10992-020-09569-2) Its principal theorem proves that the posteriors of a probability function converge to the truth almost uniformly if and only if the function has two properties: an approximation property, and so-called countable additivity on conditional hitting times. We show that the two properties are necessary but not sufficient, so that the theorem is false, and we locate the error in its published proof. We construct a merely finitely additive probability function that has both properties and whose posteriors converge to the truth almost surely but not almost uniformly. Three of the paper's four remaining theorems, and its corollary, lose their published proofs as well, two with the failed implication and two to a separate defect that we also identify. Two of the four results we reprove and one we leave undecided; the last is the corollary, which our counterexample does not refute, and which we establish for a family including the counterexample and leave open in general. We also show that almost-sure convergence of posteriors to the truth for every event does not characterize countable additivity. We close with what a repaired characterization of almost-uniform convergence would have to add.

arXiv abstract · PDF

Order Topology and Mathematical Foundations · primary corpus · published 2026-09-17T17:15:17Z
Jananan Arulseelan
arXiv categories: math.OA, math.LO

Christensen and Pedersen proved that every properly infinite $\mathrm{AW}^*$-algebra is monotone sequentially complete. We isolate the part of their argument that extends to an arbitrary cardinal. The property of properly infinite $\mathrm{AW}^*$-algebras used in their proof is the existence of an orthogonal sequence of projections, each equivalent to $1$, with sum $1$. We generalize this by defining a notion of $\kappa$-homogeneity, with the case $\kappa = \aleph_{0}$ recovering the aforementioned property. $\kappa$-homogeneity supplies the fresh orthogonal space needed at each successor stage of a transfinite projection dilation, and normality of $\mathrm{AW}^*$-algebras supplies, at every limit stage and again at the end of the construction, the passage from a join of projections to a supremum in the self-adjoint order. This second point replaces both the addability theorem and the perturbation argument used in the countable case. We prove that every $\kappa$-homogeneous $\mathrm{AW}^*$-algebra is $\kappa$-monotone complete, and that $\kappa$-monotone completeness together with $\kappa$ ordinary states separating positive elements from zero implies monotone completeness. As an application, an $\mathrm{AW}^*$-factor with a corner admitting a faithful state is monotone complete.

arXiv abstract · PDF

Order Topology and Mathematical Foundations · primary corpus · published 2026-09-17T21:51:23Z
Takayuki Kihara
arXiv categories: math.LO, math.CT

For a suitable class of structures $\mathcal{K}$, let ${\rm Sh}(\mathcal{K}_\lambda^{\rm op},J_{\rm at})$ denote the atomic sheaf topos over the opposite of the category $\mathcal{K}_\lambda$ of structures in $\mathcal{K}$ of cardinality at most $\lambda$, with embeddings as morphisms. In this article, we analyze the relationship between model-theoretic properties of $\mathcal{K}$ and logical properties of ${\rm Sh}(\mathcal{K}_\lambda^{\rm op},J_{\rm at})$. For an infinite cardinal $\lambda$, we show that $\mathcal{K}$ is Galois $\lambda$-stable if and only if the atomic sheaf topos ${\rm Sh}(\mathcal{K}_\lambda^{\rm op},J_{\rm at})$ satisfies the axiom of choice for $\lambda^+$-indexed families. We further show that every structure in $\mathcal{K}_\lambda$ extends to a maximal structure if and only if ${\rm Sh}(\mathcal{K}_\lambda^{\rm op},J_{\rm at})$ satisfies the internal axiom of choice. If $\mathcal{K}_{\rm fin}$ is a class of finite structures, the cardinalities of the structures in each connected component of $\mathcal{K}_{\rm fin}$ have a finite upper bound if and only if ${\rm Sh}(\mathcal{K}^{\rm op}_{\rm fin},J_{\rm at})$ satisfies the internal axiom of (countable) choice. Furthermore, via the topological Galois representation, we establish a correspondence between the criteria for the axiom of choice for atomic sheaf toposes and those for permutation models in set theory.

arXiv abstract · PDF

Order Topology and Mathematical Foundations · primary corpus · published 2026-09-18T03:37:44Z
Xiaoquan Xu
arXiv categories: math.LO

We study Scott products and sobriety of countable meet-continuous domains, meaning meet-continuous dcpos without any additional continuity or least-element assumption. Using the complete-lattice test-family theorem of Xu and Ji, we prove finite-product equality for those domains that are $L$-dcpos, and for the weaker class whose principal ideals have suprema of all nonempty subsets. For an arbitrary family of nonempty countable meet-continuous $L$-dcpos, we prove that the Scott topology on the order product equals the product of the factor Scott topologies if and only if only finitely many factors lack a least element. We also establish sobriety under bounded completeness and under additional common-upper-bound conditions. Assuming square-product equality, sobriety is characterized by Scott closedness of common-upper-bound sections associated with irreducible Scott-closed sets, with an equivalent sequential formulation in the countable case. Two extraction lemmas extend to meet-semilattice dcpos. The finite-product and sobriety questions for general countable meet-continuous domains remain unresolved here.

arXiv abstract · PDF

Order Topology and Mathematical Foundations · primary corpus · published 2026-09-19T05:59:56Z
Yong Cheng
arXiv categories: math.LO, math.HO

G\"odelian incompleteness yields arithmetical sentences $A$ such that $PA+A$ and $PA+\neg A$ are both consistent. Are such extensions equally legitimate? I propose graded epistemic arithmetical non-pluralism: justification for choosing between them varies with the set-theoretic strength of $A$. I defend $PA+Con(PA)$ and show Koellner's non-pluralism for first-order arithmetic is inadequate given Friedman's concrete incompleteness. Resolving the selection problem for such sentences turns on justifying large cardinals. Defending graded non-pluralism thus engages G\"odel's programme and the justification of very large cardinals.

arXiv abstract · PDF

Category Theory and Homological Algebra · primary corpus · published 2026-09-14T08:44:52Z
Nazaret Trejo-Arroyo
arXiv categories: math.FA, math.CT

Inspired by Grothendieck's foundational work, we establish that the sequence of functors $(Ext^n_{pBan}(E,-))_{n \ge 0}$ on the category of $p$-Banach spaces ($0 < p < 1$) forms a universal $\delta$-functor. To this end, for any pair of $p$-Banach spaces $E$ and $X$, we construct a $p$-Banach space $\mathcal N_E^X$ that renders each functor $Ext^n_{pBan}(E,-)$ effaceable. Furthermore, we show that this space serves as a relative injective object for $E$ and $X$, enabling the construction of relative injective presentations and proving that the functors $Ext^n_{pBan}(E,-)$ are the right derived functors of $\mathcal{L}(E,-)$. We will also examine the situation in the category of quasi-Banach spaces.

arXiv abstract · PDF

Category Theory and Homological Algebra · primary corpus · published 2026-09-14T13:05:05Z
Nohra Hage
arXiv categories: math.CO, math.CT

We study stylic monoids from the viewpoint of higher-dimensional rewriting. A coherent presentation records not only the defining relations of a monoid, but also the relations among them. Using the $N$-tableau model, we construct a finite coherent presentation for every stylic monoid of finite rank. We start from the known finite convergent row presentation. By adjoining one generating confluence for each critical branching, Squier's coherence theorem yields a finite coherent extension. We then simplify the resulted coherent presentation by two successive homotopical reductions adapted to the row combinatorics of $N$-tableaux. Finally, coherent Tietze transformations and a further homotopical reduction transfer the construction from the auxiliary row generators to the standard letter generators. This gives an effectively computable finite homotopy basis for the standard letter presentation. The construction is illustrated in detail in rank $2$.

arXiv abstract · PDF

Category Theory and Homological Algebra · primary corpus · published 2026-09-14T14:17:45Z
Luca Reggio
arXiv categories: math.RA, math.CT

The problem of determining whether a category is balanced (i.e., every morphism that is both an epimorphism and a monomorphism is an isomorphism) has been widely investigated, especially in algebra. For complete categories with an extremal projective generator, we characterise the property of being balanced, and the stronger property that every monomorphism is regular, in terms of implicit operations. These characterisations apply, for example, to any quasiequational class of algebras, possibly with a proper class of function symbols and unbounded arities, that admits free algebras.

arXiv abstract · PDF

Category Theory and Homological Algebra · primary corpus · published 2026-09-14T14:36:46Z
Junpeng Ren, Xianhui Fu
arXiv categories: math.CT, math.RA

Let $(\mathscr{C},\mathbb{E},\mathfrak{s})$ be a weakly idempotent complete extriangulated category. We generalize Cole's Theorem to construct a mixed admissible model structure $\mathcal{M}_m$ from two compatible admissible model structures relative to proper classes $\xi_1\subseteq\xi_2$ of $\mathscr{C}$. We then explicitly characterize the cofibrant objects of $\mathcal{M}_m$. Finally, we apply these results to exact and triangulated categories, recovering and extending recent work on mixed model structures.

arXiv abstract · PDF

Category Theory and Homological Algebra · primary corpus · published 2026-09-14T17:08:37Z
Gabriel Ciobanu
arXiv categories: cs.LO, math.CT, math.LO

Finite support indicates that the dependence is limited, but not how each finite context controls what can be observed. For a data symmetry G \leq Sym(A) and a finitely supported G-set X, we study the finite-dependence profile X^S = {x : Fix_G(S) fixes x}, indexed by finite contexts S \subseteq A. For relations on A^n this yields Boolean algebras B^{(n)}_{G,S} = Inv_n(Fix_G(S)), forming the invariance hierarchy. The hierarchy separates several nominal principles. Its meet law is the relation-algebra form of the Bojanczyk-Klin-Lasota least-support criterion, while level injectivity is fungibility. The independent join law governs composition across unions of contexts; it holds for locally oligomorphic automorphism groups of ultrahomogeneous structures in purely relational languages of arity at most two, but can fail for unary observations over ternary data. Freshness remains valid sort by sort, and its unrestricted some/any form characterizes full equality symmetry among closed groups. With least supports, orbit-finiteness implies finite context levels and a uniform support bound; under local oligomorphicity the converse also holds. Pointwise closure does not change the profile, and standard atomic-site presentations show that suitable ultrahomogeneous structures with the same age have equivalent action topoi, even though their material FSS universes may retain different external cardinal data. Contextual orientability gives a complementary pointed invariant whose threshold is the least support size of choice from unordered pairs. For countable omega-categorical structures with degenerate algebraic closure, the meet law is equivalent to weak elimination of imaginaries.

arXiv abstract · PDF

Category Theory and Homological Algebra · primary corpus · published 2026-09-14T17:23:32Z
Victor Bloch, Tobias Fritz
arXiv categories: math.PR, math.CT

We show that the product measure is the only natural way to assign to each pair of probability measures on measurable spaces a probability measure on their product. Here, naturality is meant in the sense of category theory and amounts to the condition that the assignment commutes with pushforward along measurable maps. In the standard Borel setting, we also prove an analogous result for relative product measures over a fixed base probability space.

arXiv abstract · PDF

Category Theory and Homological Algebra · primary corpus · published 2026-09-15T14:56:14Z
Fernando Abell\'an
arXiv categories: math.AT, math.CT

In this work, we develop a fibrational approach to freely adjoining adjoints in an $(\infty,2)$-category. We construct the universal bifibration obtained from a cocartesian fibration of $(\infty,2)$-categories by adjoining cartesian lifts over a chosen class of $1$-morphisms in the base. We then use this construction to provide an explicit model for freely adjoining adjoints, together with a zig-zag formula for the resulting mapping $(\infty,1)$-categories. As applications, we give a model-independent proof of the universal property of the walking adjunction, providing an alternative proof of a theorem of Riehl--Verity, and establish the universal characterization of the simplex $2$-category conjectured by Dyckerhoff--Kapranov--Schechtman--Soibelman.

arXiv abstract · PDF

Category Theory and Homological Algebra · primary corpus · published 2026-09-15T21:16:52Z
Jean-David Jacques, Felix Medwed, Fabrizio Zanello
arXiv categories: math.FA, math.CT

We provide a universal characterisation of the Banach spaces of equivalence classes of $L^p$ Bochner integrable functions, under equality almost everywhere, as initial objects in appropriate categories of bifunctors, for all $p \in [1,\infty)$. As a by-product of our construction, we also obtain a unique characterisation of the Bochner integral.

arXiv abstract · PDF

Category Theory and Homological Algebra · primary corpus · published 2026-09-16T13:07:53Z
Chencheng Zhang
arXiv categories: math.CT

This paper studies (co)products and additive structures under Gabriel--Zisman localization $Q:\mathcal A\longrightarrow\mathcal A[S^{-1}]$. Examples show that localization may destroy existing (co)products or fail to preserve (co)products that remain, even when $Q$ is additive. For a set-indexed family $(\mathcal A_i,S_i)_{i\in I}$, necessary and sufficient conditions are given for the canonical functor $\big(\prod_{i\in I}\mathcal A_i\big)\big[\big(\prod_{i\in I}S_i\big)^{-1}\big]\longrightarrow\prod_{i\in I}\mathcal A_i[S_i^{-1}]$ to be full or faithful. These criteria yield compatibility with $I$-indexed (co)products for localizations admitting a calculus of fractions or arising from model categories, provided the relevant (co)products exist and the designated classes of morphisms are closed under them.

arXiv abstract · PDF

Category Theory and Homological Algebra · primary corpus · published 2026-09-17T04:39:49Z
Yuji Okitani
arXiv categories: math.AG, math.AT, math.CT, math.SG

Perverse schobers are a categorification of perverse sheaves, originally proposed by Kapranov and Schechtman. The purpose of this paper is to initiate a microlocal study of perverse schobers. We first categorify $\operatorname{Perv}(\mathbb{C},R)/\operatorname{Loc}(\mathbb{C})$, the category of perverse sheaves on a complex line with singular points at $R$, modulo local systems. We use this to propose a general definition for microlocal perverse schobers supported on the open conormal to a germ of a hypersurface, and we conjecture that this is invariant under Radon transform. Here we make the key observation that while the analogous quotient of perverse schobers $\mathsf{2Perv}(\mathbb{C},R)/\mathsf{2Loc}(\mathbb{C})$ is a reasonable categorification, the resulting theory fails to be invariant under Radon transform. In fact, our proposed categorification can be recovered by correcting an instance of this failure in a universal manner. We prove Radon invariance when our hypersurface is the curve $y^m=x^n$ in $\mathbb{C}^2_{x,y}$. Along the way, we explain how our theory relates to Fourier transforms of perverse schobers, periodic SODs, and spherical monads.

arXiv abstract · PDF

Category Theory and Homological Algebra · primary corpus · published 2026-09-17T15:06:51Z
Thorger Gei{\ss}, Phil P\"utzst\"uck, Maxime Ramzi
arXiv categories: math.CT, math.AT, math.GN, math.LO

We give a short proof that $\kappa$-cocompact objects in a presentable category are subterminal. As our main result, we extend this to the setting of presentable $\infty$-categories. A consequence is that an $\infty$-category $\mathcal{C}$ such that both $\mathcal{C}$ and $\mathcal{C}^\mathsf{op}$ are presentable is a small complete lattice, extending a classical theorem of Gabriel-Ulmer. Along the way, we prove a nilpotence result for phantom maps in general pointed presentable $\infty$-categories. Additionally, we show that a strengthening of our main result is equivalent to the existence of a proper class of measurable cardinals.

arXiv abstract · PDF

Category Theory and Homological Algebra · primary corpus · published 2026-09-17T17:16:01Z
Tobias Barthel, Drew Heard
arXiv categories: math.CT, math.AC, math.AT, math.RT

We construct commutative rings whose derived categories have non-spatial frames of smashing ideals, thereby answering in the negative questions of Balchin--Stevenson and Aoki.

arXiv abstract · PDF

Category Theory and Homological Algebra · primary corpus · published 2026-09-18T20:08:34Z
Fahimeh Bayeh, Peng Fu, Peter Selinger
arXiv categories: math.CT, cs.LO

The category Nom of nominal sets was proposed by Pitts and Gabbay as a setting for the semantics of abstract syntax with variable bindings. It is well-known that Nom is a topos, also known as the Schanuel topos, and in particular it follows that Nom is locally closed, i.e., every slice category Nom/X is cartesian-closed. In this paper, we show that Nom has a much stronger property: every monoidal (closed) structure on Nom induces a monoidal (closed) structure on all slice categories Nom/X. One monoidal closed structure of particular interest on Nom is the separated product A * B, whose right adjoint A -* B is called the separated function space. In particular, it follows that Nom is locally separatedly closed.

arXiv abstract · PDF

Category Theory and Homological Algebra · primary corpus · published 2026-09-19T10:16:15Z
Francesco Vaccarino
arXiv categories: math.ST, math.CT, math.PR, stat.TH

We show that a statistical model in the sense of McCullagh, in the form given by Br{\o}ns, is a natural transformation between two functors from the category of designs to the Kleisli category Stoch of the Giry monad, provided that its components are measurable in the parameter. The condition is empty for finite models. A design-indexed quantity is a family of morphisms of Stoch defined on the parameter objects, called meaningful if it is natural. We prove that Tjur's criterion, imposed on parameter functions indexed by finite samples with multiplicities, forces the indexing by the support and then coincides with naturality over the insertions. For finite designs we show that a quantity can be corrected to a natural one within a given class of corrections if and only if a class vanishes in the first cohomology group of a Baues-Wirsching complex relative to that class, while its image in the absolute group is always zero. In the one-way layout, marginal dispersion is not meaningful, and within-group dispersion is the unique correction that leaves the merged design unchanged. A prior is a family of states on the parameter objects, called coherent over a class of design morphisms if it is natural over that class. We show that coherence at a merge confines the prior to the image of the corresponding parameter map, that coherence over the insertions is Kolmogorov consistency, and that coherence over the injections adds the exchangeability assumed by the categorical de Finetti theorem. In the finite one-way scheme, the coherent priors form polytopes of known dimension. The analogue of Jeffreys' general rule is not coherent, while the analogue for location-scale families is. Finally, we show that ridge regression is the Bayesian inversion of the Gaussian linear model with respect to a Gaussian prior, which is coherent over the insertions and never over the injections.

arXiv abstract · PDF

Category Theory and Homological Algebra · primary corpus · published 2026-09-19T12:45:40Z
Zhongyuan Wang, Haicheng Zhang, Tiwei Zhao
arXiv categories: math.RT, math.CT, math.RA

Let $(A,T,B)$ be a splitting tilting triple. We provide a construction of $\tau_2$-tilting $B$-modules from $\tau$-tilting $A$-modules. On the other hand, if $A$ is hereditary, by considering the mutation of a certain two-term silting complex of $A$ and its image under the derived equivalence $\mathbf{R}{\rm Hom}_A(T,-):D^b(A)\to D^b(B)$, we get a three-term silting complex ${\bf W}$ of $B$. Under an explicit non-vanishing condition on the cones of morphisms between the two summands, we prove that ${\rm H}^0\boldsymbol{W}$ is a basic $2$-tilting $B$-module and that it coincides with the module obtained from the first construction. As an application, we generalize the construction of Peng from tilting modules to $\tau$-tilting modules. We also determine the endomorphism algebra of the constructed module as an explicit triangular matrix algebra, which is derived equivalent to $A$ and $B$ whenever the constructed module is $2$-tilting, and give a full semi-orthogonal decomposition of $K^b(\operatorname{proj}A)$.

arXiv abstract · PDF

Algebra Quantum Theory and Representations · primary corpus · published 2026-09-14T17:59:36Z
Tzu-Chen Huang
arXiv categories: math.QA, hep-th, math.CT, math.OA

We construct a complex spherical fusion category with cyclic Haagerup-Izumi fusion rules for every odd n >= 3, and deduce pseudo-unitary existence. The proof has four parts: explicit real coefficients and their quadratic identities; a contour calculation for a range of cubic Fourier coefficients; algebraic completion of all cubics; and categorical reconstruction. Matrix inversion supplies reflection, and an extension of the dimension-field automorphism supplies the positive-dimensional category.

arXiv abstract · PDF

Algebra Quantum Theory and Representations · primary corpus · published 2026-09-15T17:08:02Z
Johannes Flake, Jonathan Gruber, Thorsten Heidersdorf
arXiv categories: math.CT, math.RT

We show that the universal rigid monoidal category on one object has an abelian envelope. Since it was proven by Coulembier-Etingof-Ostrik-Pauwels (2023) that this category cannot have an abelian envelope with the quotient property, this disproves the conjecture in [op.cit.] saying that every abelian envelope has the quotient property. Monoidal Ringel duality (Flake-Gruber arxiv:2512.19558) yields a candidate envelope as a lower finite highest weight category. Our proof that this is an abelian envelope relies on Coulembier-Etingof's (2024) continuants to show the required universal property. AI was used to find these results.

arXiv abstract · PDF

Algebra Quantum Theory and Representations · primary corpus · published 2026-09-17T05:09:43Z
Greyson Wesley
arXiv categories: math.QA, math-ph, math.CT, math.MP, math.OA

We introduce the notion of a unitary disk-like $n$-category, which is a disk-like $n$-category equipped with a reflection structure and a sphere trace inducing positive-definite pairings. Since a finite unitary disk-like $n$-category is defined to be the local field data of a fully extended $(n+1)$D unitary TQFT, we propose a complete finite unitary disk-like $n$-category as the definition of a finite $(n+1)$-Hilbert space for all $n$. For $n=1$ and $n=2$ we verify this proposal, proving that complete finite unitary disk-like 1- and 2-categories are isometrically equivalent to finite 2- and 3-Hilbert spaces respectively, and that these equivalences are functorial. For $n=1$ we recover a unitary refinement of Schommer-Pries' classification of oriented $(1+1)$D TQFTs in terms of $\mathrm{H}^*$-Morita equivalence classes of $\mathrm{H}^*$-algebras, and for $n=2$ we categorify this to classify oriented $(2+1)$D unitary TQFTs by $\mathrm{H}^*$-Morita equivalence classes of $\mathrm{H}^*$-multifusion categories. Along the way, we investigate fully incomplete 3-Hilbert spaces, prove a strictification result for pivotal dagger 2-categories, and define functors and higher transformations between disk-like $n$-categories.

arXiv abstract · PDF

Algebra Quantum Theory and Representations · primary corpus · published 2026-09-17T10:54:10Z
Ming Ding, Fan Xu, Panyue Zhou
arXiv categories: math.RT, math.CT

We prove a multiplication formula for the Wang-Wei-Zhang cluster character on a Hom-finite $2$-Calabi--Yau Frobenius extriangulated category $\mathcal C$ with a cluster-tilting object under the assumption that its stable category has constructible cones with respect to the induced cluster-tilting object. This formula generalizes those obtained by Wang-Wei-Zhang for $\mathcal C$ in the one-dimensional case and by Keller-Plamondon-Qin for (stably) $2$-Calabi-Yau Frobenius or triangulated categories. As a consequence, we express the frozen term in an Auslander-Reiten mesh with the character of a minimal cosyzygy middle term. For acyclic quivers with principal coefficients, we compute these frozen multiplicities in Higgs categories and obtain explicit principal coefficient mesh relations.

arXiv abstract · PDF

Algebra Quantum Theory and Representations · primary corpus · published 2026-09-17T14:53:59Z
Xuexing Lu
arXiv categories: math.PR, cs.IT, math.CT, math.IT, math.ST, stat.TH

We construct a symmetric operad $\mathfrak{C}$ on the class of all multivariate copulas, with operadic composition given by Sklar substitution. This places the hierarchical combination of dependence structures into an algebraic framework. Restricting to absolutely continuous copulas whose densities lie in $L\log L$, we prove that copula entropy is additive under composition, making it an additive character on suitable finite-entropy suboperads. We exhibit explicit closed suboperads (bounded, $L^{p}$, boundary-growth) and show by counterexample that componentwise $L\log L$ does not imply closure under composition.

arXiv abstract · PDF

Algebra Quantum Theory and Representations · primary corpus · published 2026-09-17T17:17:47Z
Gregory Faurot, Charlton Li, David Penneys, Emeline Sherman
arXiv categories: math.OA, math-ph, math.CT, math.MP, math.QA

The article arXiv:2410.21454 constructed a braided $\mathrm{W^*}$-tensor category of superselection sectors associated to a net of von Neumann algebras on a suitably geometric poset using localized and transportable endomorphisms. In this article, we construct an equivalent tensor product and braiding using the Connes fusion tensor product without localizing, using ideas from arXiv:1812.04470 for conformal nets. As an application, we prove that the category of superselection sectors associated to the 2D braided quantum spin system constructed from a unitary braided fusion category $\mathcal{B}$ in arXiv:2506.19969 is equivalent to $\mathsf{Hilb}(\mathcal{B})^{\rm op}$, the opposite of the unitary ind-completion of $\mathcal{B}$, as a braided $\mathrm{W^*}$-tensor category.

arXiv abstract · PDF

Algebra Quantum Theory and Representations · primary corpus · published 2026-09-17T20:13:54Z
Kate Ponto, Travis Wheeler
arXiv categories: math.AT, math.CT

Group representations very comfortably admit a higher categorical generalization. This includes induction and restriction for 2-representations that very directly parallel classical definitions. An appropriate character theory for 2-representations has been more opaque. In this paper we draw from a range of motivations to provide an intuitive character theory for 2-representations. It is built from the bicategorical trace developed to describe topological fixed point theory. We use the secondary traces of Ben-Zvi and Nadler which connect to Riemann-Roch and Lefschetz-type theorems in the context of differential graded categories and Fourier-Mukai transforms. Additional sources of motivation include Lipmans' work on Grothendieck duality and, crucially, the Bartlett and Ganter--Kapranov approaches to characters. (The second of these was in turn motivated by Hopkins, Kuhn and Ravenel's work on equivariant Morava $E$-theories.) Our characters are compatible with restriction and induction and, in cases that are sufficiently finite, admit a secondary character.

arXiv abstract · PDF

Algebra Quantum Theory and Representations · primary corpus · published 2026-09-18T11:34:27Z
Han Dai, Vyacheslav Futorny, Huimin Gao
arXiv categories: math.RT, math.CT

We develop a categorical framework for Lie-Rinehart monoids and their weak modules in a symmetric monoidal category. Using crossed homomorphisms, we construct a natural action of the monoidal category of modules over a Lie monoid on the category of weak Lie-Rinehart modules, thereby obtaining categorical versions of the Shen-Larsson functors. We further characterize the conditions under which the category of weak modules admits a monoidal structure and identify the corresponding condition for the associated functors to be strict monoidal. A dual theory for Lie- Rinehart comonoids and weak comodules is developed using cocrossed homomorphisms. Combining the module and comodule constructions, we obtain a bimodule category structure on the category of weak modules. Finally, we specialize the general framework to the symmetric monoidal category of super vector spaces, recovering Lie-Rinehart superalgebras and their associated Shen-Larsson-type constructions.

arXiv abstract · PDF

Algebra Quantum Theory and Representations · primary corpus · published 2026-09-20T09:29:09Z
Tatsuya Goto
arXiv categories: math.LO

We study Borel-Tukey morphisms between almost-homogeneity relations. For finite $r,s\ge1$ and $m,n\ge2$, we give the complete one-stage classification: $\mathbf{Hom}^r_m\to_{\mathrm{BT}}\mathbf{Hom}^s_n$ holds exactly when $r>s$, or when $r=s$ and $m\ge n$. Our main result is that binary triple homogeneity requires exactly three sequential binary pair stages: $\mathbf{Hom}^2_2;\mathbf{Hom}^2_2;\mathbf{Hom}^2_2\longrightarrow_{\mathrm{BT}}\mathbf{Hom}^3_2$ and $\mathbf{Hom}^2_2;\mathbf{Hom}^2_2\not\longrightarrow_{\mathrm{BT}}\mathbf{Hom}^3_2$. We also construct Borel morphisms $\mathbf{Hom}^2_2;\mathbf{Hom}^2_3\longrightarrow_{\mathrm{BT}}\mathbf{Hom}^3_2$ and $\mathbf{Hom}^2_2;\mathbf{Hom}^2_2\longrightarrow_{\mathrm{BT}}\mathbf{Hom}^2_k$ for every finite positive $k$.

arXiv abstract · PDF

Algebra Quantum Theory and Representations · primary corpus · published 2026-09-20T11:35:14Z
Lothar Sebastian Krapp, Remo Nitschke
arXiv categories: cs.FL, cs.CL, math.LO, math.PR

We reconsider the theory of probabilistic formal languages generated by n-gram models and by probabilistic context-free grammars (PCFGs). The expected hierarchy of probabilistic grammars is established by proving that every probabilistic language generated by an n-gram model is also generated by some PCFG, while some probabilistic languages generated by PCFGs cannot be generated by any $n$-gram model. We introduce the notion of fully connected PCFGs, namely PCFGs in Chomsky normal form where every production rule only involving non-terminals has non-zero probability. Our main result shows that any probabilistic language generated by an $n$-gram model differs from any probabilistic language generated by a fully connected PCFG. Therefore, the class of probabilistic languages generated by $n$-gram models is not a subset of the class generated by fully connected PCFGs.

arXiv abstract · PDF

Software Assurance and Intelligent Agents · cs.SE candidate · published 2026-09-14T11:31:06Z
Artem Trofimov, Boris Novikov
arXiv categories: cs.AI, cs.DB, cs.DC, cs.SE

AI agents increasingly execute long-running workflows that externalize effects through independently supplied tools. Under retries, speculative execution, concurrency, and partial failures, the resulting external state may be inconsistent with the workflow's intended resolution: required effects may be missing or duplicated, aborted effects may survive, and committed effects may depend on provisional state that is later withdrawn. Advanced transaction models address related failures, but assume that lower-level operations expose the semantics they depend on: whether an effect occurred, whether it can be compensated, staged, or safely reordered. Shared agent-tool interfaces usually do not. We contribute an effect-history model that separates events in the external world from the runtime's observations of them, and a catalog of eight recurring external-effect anomalies. From the catalog we derive the boundary capabilities required to exclude each anomaly in general, and four points where black-box tool invocation alone cannot provide a general guarantee. We then ask how much of this is expressible in a widely used shared tool interface, measuring the use of the standard annotation vocabulary across 98,291 tools exposed by registered Model Context Protocol (MCP) servers. The fields are widely emitted but provide only coarse call-level hints, and none of the required capabilities is fully expressible. These results motivate reusable transactional contracts at the tool boundary.

arXiv abstract · PDF

Software Assurance and Intelligent Agents · primary corpus · published 2026-09-14T17:49:09Z
Tuyen Van Kieu, Khanh Ngoc Do, Khanh Van To
arXiv categories: cs.LO

Home-care allocation must balance continuity of care, caregiver overtime, and caregiver-service compatibility. The published formulation of the Home-Care Optimal Resource Allocation Problem (HCORAP) uses a weighted policy (Weighted) to combine these outcomes, allowing compatibility gains to offset poorer continuity or additional overtime. We introduce LEX-COS, a lexicographic objective for HCORAP that first minimizes continuity violations, then overtime, and finally maximizes compatibility. We give an exact MaxSAT implementation and construct HCORAP-LC, a reproducible 48-instance synthetic evaluation suite with limited caregiver capacity. Compared with Weighted, LEX-COS reduces both continuity violations and overtime in 42 of 48 instances, without increasing either measure in any instance, while yielding lower compatibility. In 36 instances, LEX-COS achieves better continuity and lower overtime than every Weighted-optimal allocation. On the separate 48-instance Original benchmark, Gurobi and CPLEX, two leading commercial MIP solvers, resolve every instance under both policies and are substantially faster than EvalMaxSAT. EvalMaxSAT also resolves the full benchmark under LEX-COS. Within EvalMaxSAT, replacing sorting networks with Totalizer improves runtime under Weighted, with no clear gain under LEX-COS. These results characterize the effects of giving continuity and overtime explicit priority in home-care allocation.

arXiv abstract · PDF

Software Assurance and Intelligent Agents · cs.SE candidate · published 2026-09-14T17:53:49Z
Fares Trad, Simin Chen, Hung Viet Pham, Gias Uddin, Baishakhi Ray
arXiv categories: cs.CR, cs.SE

Software agents with Large Language Models (LLMs) are designed for Automated Program Repair (APR) tasks, raising the possibility that, in the near future, APR agents will fix bugs automatically without much human intervention. Can we trust an APR agent to produce both functionally correct and secure code in such situations? What if attackers target production APR agents with adversarial issues that seem benign but may influence the agents to produce correct but insecure code? In this paper, we took a first step towards answering these questions by conducting an empirical study. First, we created SWEADV, a benchmark of 750 adversarial issue descriptions constructed from 150 repair tasks in SWE-bench Verified. For each repair task, we created five adversarial issue descriptions, one for each attack type: command execution, deserialization, path traversal, denial of service, and weak hashing. Second, we evaluated mini_swe APR agents from three LLM backends on SWEADV: GPT-5-Mini, MiniMax-M2.5, and DeepSeek-R. We found that on average, adversarial issue descriptions can induce malicious behaviors with successful repair in 51.7% of cases. Third, we investigated whether typical detection mechanisms are sufficient to prevent such malicious patches from being accepted. Pre-repair detection with LLM-as-judge on the adversarial issue descriptions resulted in an average detection accuracy of only 62.3%. Post-repair detection on adversarial APR patches using static analysis tools and LLM-as-judge achieved average detection accuracies of only 39.4% and 55.4%, respectively. We conclude that autonomous APR agents cannot be trusted yet in production deployment, given their susceptibility to adversarial attacks.

arXiv abstract · PDF

Software Assurance and Intelligent Agents · cs.SE candidate · published 2026-09-14T19:42:03Z
Wuyang Dai, Song Wang
arXiv categories: cs.SE

AI coding agents increasingly rely on execution harnesses to interact with repositories and external tools. However, task success does not guarantee reliable execution. Agents may still modify unrelated files, rewrite tests, issue unsafe commands, or ignore failed validations, motivating behavioral guardrails for reliable execution. We present AgentGuard, an instruction-level guardrail framework that learns conditional execution constraints from anomalous trajectories of coding agents. Rather than relying on manually specified safety rules, AgentGuard automatically extracts recurring execution failure patterns, generalizes them into instruction-level behavioral constraints, and organizes them as a lightweight guardrail skill that dynamically activates only the rules relevant to the current instruction. This design enables behavioral guidance while minimizing unnecessary restrictions on normal execution. We evaluate AgentGuard using 642 documented failure traces collected from real coding-agent executions across 382 repository tasks. Guardrails are learned from 461 traces covering 282 tasks and evaluated on a disjoint set of 100 tasks. Using Claude Code with Claude Haiku 4.5 as the underlying coding agent, we compare the baseline agent with the same agent augmented by AgentGuard. Experimental results show that AgentGuard reduces the Abnormal Execution Rate from 69.0% to 26.7% and increases the Successful Task Completion Rate from 21.7% to 35.0%. These results demonstrate that execution guardrails learned from historical failures can substantially improve the reliability of AI coding agents while highlighting the remaining challenge of balancing safety and task completion.

arXiv abstract · PDF

Software Assurance and Intelligent Agents · primary corpus · published 2026-09-14T20:06:46Z
Anjan Goswami
arXiv categories: cs.SE, cs.AI, cs.PL

When a coding agent returns to existing software, it inherits evidence from earlier engineering work: tests, type checks, proofs, static analyses, and traces. Reloading all of it is wasteful, but dropping a piece the change depends on can leave a required property unsupported. Given the properties a change must preserve, its obligations, we ask which least-cost subset of the available evidence re-establishes them, and we call such a subset a task-conditioned assurance envelope. Evidence and the rules that combine it form a typed inference graph; an obligation is met when forward chaining from the selected evidence reaches it, and we validate every selection by that closure rather than by trusting the optimizer. The software-derived graphs in our evaluation come from preserved outcomes of prior AI coding-agent runs; we freeze those artifacts and ask which accumulated evidence should be restored for a later task. Small graphs from Rust, IronBlocks, and Pong outcomes show that the minimum envelope depends on the task, that none may exist when current evidence cannot re-establish a required property, that some properties need several pieces of evidence together, and that expanding the requirements adds evidence rather than replacing it. A prespecified synthetic benchmark of 249 instances characterizes computation: a baseline that discards the 'several pieces together' structure necessarily fails to re-derive them; every completed exact cross-check agreed with the CP-SAT optimizer; and median solve time stayed below 20 ms at 500-evidence graphs, except that graphs with many alternative derivations per target timed out at far smaller sizes, so structure, not raw size, drives difficulty. The contribution is a bounded application of established optimization to selecting assurance context for a software change; discovering the obligations and downstream agent benefit remain open.

arXiv abstract · PDF

Software Assurance and Intelligent Agents · cs.SE candidate · published 2026-09-14T20:20:54Z
Jun He, Deying Yu
arXiv categories: cs.DC, cs.AI, cs.SE

In agentic distributed systems, an agent may be authorized to mutate external infrastructure while lacking evidence that the mutation is ready to execute. Cognitive Admission Control (CAC) makes this evidence requirement explicit. A policy maps a typed action and its modeled risk to assurance obligations specifying predicates, evidence classes, scope, freshness, and witness-set constraints. A deterministic evaluator distinguishes satisfied, violated, and unresolved obligations; unresolved conditions produce targeted evidence-acquisition requests. Successful admission produces a certificate binding the action, its witness manifest, and dispatch-time guards. We formalize the admission calculus and the assumptions connecting it to mediated execution. The guarantees are policy-relative: physical safety additionally requires sound evidence, an adequate environment model, and preservation of relevant conditions through the effect. A TypeScript prototype is evaluated in 2,730 controlled local trials with independent effect observation and matched fault schedules. Across 390 CAC trials, 120 effects complete without modeled harm and no harmful effects occur. A live-policy baseline achieves the same completion count but admits the constructed correlated-witness failure. Mechanism ablations isolate guard, evidence-class, structural-cut, and remediation behavior. A further 9,000 measurements exercise the complete local dispatch path with persistent replay protection. These results establish tested implementation behaviors and local costs, not production failure rates or comparisons of language-model capability.

arXiv abstract · PDF

Software Assurance and Intelligent Agents · cs.SE candidate · published 2026-09-15T11:01:51Z
Yixuan Liu, Yin Wu, Yi Li
arXiv categories: cs.SE, cs.CR

The Open Network (TON), with a peak market capitalization exceeding $20 billion and over 175 million activated on-chain addresses, relies on the TVM (TON Virtual Machine) to execute smart contracts. TVM uses first-class continuations with savelists to manage control flow and register state across continuation invocations. Since savelist-captured registers allow data to flow across continuation boundaries without passing through the operand stack, bytecode-level analyses cannot construct complete data flow tracking without explicitly modeling savelist semantics. We present TasmScan, the first bytecode-level static analysis framework for TVM that enables cross-continuation data flow reasoning without requiring source code. TasmScan models savelist semantics via forward register analysis with a formal over-approximation guarantee for exact-resolved save sites and locally tracked register definitions, then lifts bytecode into TASIR, a typed intermediate representation, and performs path-sensitive taint analysis with context-aware sources to detect defects. We evaluate TasmScan on 2,921 contracts from the TON verifier registry and a labeled benchmark of 208 contracts with human-confirmed ground truth. On the full corpus, TasmScan resolves 294,546 dynamic continuation targets with 100% precision; ablation confirms that savelist propagation is essential for resolving indirect register calls that depend on cross-continuation register passing. On the benchmark, TasmScan detects 95.3% of defects across five classes with 96.8% precision. A 366-pair stratified sample from the full corpus estimates 85.8% overall precision. TasmScan offers a 17x median speedup over the state-of-the-art symbolic-execution baseline, and in the path-analysis comparison completes 100% of analyses with zero crashes or timeouts.

arXiv abstract · PDF

Software Assurance and Intelligent Agents · primary corpus · published 2026-09-15T12:40:27Z
Lilian Killich, Marko Schmellenkamp, Fabian Vehlken, Thomas Zeume
arXiv categories: cs.CY, cs.AI, cs.LO

Modelling with mathematical formalisms like logical formulas, mathematical equations, or regular expressions is an important yet challenging task for students of computer science and other STEM disciplines. Identifying common mistakes occurring in this context is an important step towards helping struggling students by providing targeted high-quality feedback, e.g. in interactive learning systems. We present a tool-supported workflow that allows to (1) identify candidates for common mistakes that explain many student mistakes in large educational data sets, (2) cluster candidates according to similarities, and (3) visualize resulting clusters for instructors and CS education researchers. The visualization is designed to help researchers to identify common modelling mistakes. The candidates for common mistakes are represented by bug fixing transformations that translate incorrect formalizations into correct formalizations; they are generated by an LLM and validated algorithmically. We show that this approach works well by reproducing common mistakes in propositional logic modelling that were identified by hand in the literature; showing that, unlike other algorithmic approaches, the LLM-based approach is suitable for very large sets of data; and applying it to multiple other formalisms to showcase it generalizes beyond propositional logic.

arXiv abstract · PDF

Software Assurance and Intelligent Agents · cs.SE candidate · published 2026-09-16T08:37:43Z
Jisoo Kim, Taeyoon Kwack, Jinwoo Jang, Woo Kyung Kim, Honguk Woo
arXiv categories: cs.SE, cs.AI

Large Language Models (LLMs) are increasingly adopted for compliance and legal reasoning tasks, yet their outputs often lack explicit grounding in legal logic and evidence. We present Code-as-Auditor, an LLM-based framework that extends the model's reasoning capability toward structured and evidence-grounded compliance assessment. The framework translates regulatory information into (1) formalized checklists and executable decision trees, encoding regulations and conditions as interpretable code structures. During inference, each checklist item is (2) dynamically expanded into factual and counterfactual questions, guiding the model to reason over case-specific evidence and potential violations. This process establishes a reasoning pipeline that proceeds from evidence identification, through rule application, to final decision-making, while a self-verification loop improves the logical consistency of the generated code and the traceability of outcomes. Experiments on privacy and data protection scenarios demonstrate that Code-as-Auditor delivers more accurate and evidence-backed evaluations, enabling automated compliance regulation checking grounded in explicit regulatory criteria.

arXiv abstract · PDF

Software Assurance and Intelligent Agents · primary corpus · published 2026-09-16T16:00:34Z
Julian Alfredo Mendez, Timotheus Kampik
arXiv categories: cs.CY, cs.AI, cs.LO, cs.MA, cs.PL

This paper presents the AR fairness metamodel, a framework designed to represent, analyze, and compare different fairness scenarios. The metamodel considers key elements, such as agents, resources, and their attributes, and enables the systematic definition and comparison of various fairness measures. We provide examples involving both discrete and continuous measures, including equality, equity, group fairness, individual fairness, the Gini index, the Theil index, Jain's fairness index, and a detailed fairness measure for Australia's Child Care Subsidy. We also explore relationships among group fairness, individual fairness, and envy-freeness, supported by formal proofs. At the conceptual modeling level, our approach builds on the Tiles framework, which offers modular components that can be connected to capture diverse fairness definitions. The goal is to make AR-based fairness definitions practical and adaptable across contexts, providing a clear way to define, compare, and evaluate them. An implementation of the Tiles framework is available as an open-source tool, and can support fairness modeling and evaluation across a wide range of applications.

arXiv abstract · PDF

Software Assurance and Intelligent Agents · cs.SE candidate · published 2026-09-16T20:15:36Z
Albert Wu, Nicholas Roberts, Tzu-Heng Huang, Haoran Lin, Gil Friedman, Sungjun Cho, Gabriel Orlanski, Frederic Sala
arXiv categories: cs.AI, cs.CR, cs.SE

LLM coding agents now generate complex programs at a scale that makes thorough human review increasingly difficult, raising the risk of safety and security failures. Common approaches, including fuzz testing, static analysis, and LLM-as-a-Verifier, can detect many failures but struggle to cover all possible edge cases. Formal verification addresses this by providing machine-checkable guarantees over specified properties, but traditionally demands substantial manual specification and proof engineering. We introduce a unified multi-agent framework, MAGS, that generates executable programs with formal safety guarantees, using Dafny as a verification-aware intermediate representation where safety properties can be mechanically checked. MAGS formalizes and freezes human-audited APIs and safety requirements, translates generated code into Dafny, repairs violations using verifier feedback, and compiles verified programs back into executable code. We evaluate MAGS on 100 CUDA kernels, 100 terminal scripts, and 20 robotic-arm tasks. Across all 220 examples, it achieves a 100% success rate in producing programs with non-trivial safety guarantees against frozen specifications. Independent safety and functional evaluations further show strong performance across all three domains, while revealing failures when the auto-formalized semantics do not fully capture the target behavior.

arXiv abstract · PDF

Software Assurance and Intelligent Agents · primary corpus · published 2026-09-17T02:26:27Z
Kartik Chandra, Jonathan Ragan-Kelley, Joshua B. Tenenbaum, Rebecca Saxe
arXiv categories: cs.PL

What kind of thing is a ``theory of mind''? We propose to formalize theories of mind as domain-specialized programming languages, which can be used to reason about the mental states of other agents. Our proposal builds on the longstanding idea that thinking is akin to programming in an internal ``language of thought.'' But rather than positing a single general-purpose language for all of thought, we posit a collection of domain-specific languages of thought, whose respective syntaxes and semantices encode the theories of various domains. We make this idea concrete in the domain of intuitive psychology using a real-world programming language called memo, which is specialized for theory-of-mind reasoning via domain-specialized syntactic constructs like ``knows,'' ``wants,'' and ``thinks.'' In our view, using one's theory-of-mind to think about a social situation is analogous to using memo to write a program that models that situation. Through a series of worked examples, we show how formally representing a theory of mind as a memo-like programming language can lend insight into a variety of theoretical issues in theory-of-mind research: (1) how a single, fixed intuitive theory can be used to reason about social situations with unbounded structural variation; (2) how a modular, domain-specialized, and informationally-encapsulated system for social cognition might interface with external world knowledge, as well as other cognitive systems like intuitive physics; and (3) how different theories of mind, such as those of children and adults, differ, what exactly is gained as theories grow over the course of development, and how that growth might occur.

arXiv abstract · PDF

Software Assurance and Intelligent Agents · primary corpus · published 2026-09-17T10:39:50Z
Arnab Ray, Aalok Thakkar
arXiv categories: cs.PL

Software in production encounters inputs shaped by how it is used in practice. We study distribution-aware reliability estimation: given a program, its operational input distribution, and a condition of interest, determine how often that condition holds and certify the result with a guaranteed error bound. Symbolic and statistical methods offer two ways to answer this question. Symbolic methods reason about entire regions of the input space and can certify rates exactly, but often struggle with complex arithmetic or loops. Statistical methods instead sample inputs and apply concentration bounds. They are broadly applicable, but can require many samples when failures are rare. We bring these approaches together in a framework that includes both as special cases. Each estimator has three components: a mass estimator, a per-leaf confidence bound, and a symbolic closure rule. We prove that any instantiation satisfying three invariants returns an interval containing the true rate with confidence 1-delta, regardless of when it stops. The certified error has two parts: a statistical term, reduced by sampling, and a structural term, reduced by symbolic closure. Pure sampling and pure symbolic execution each reduce only one of these terms. Alternative choices of the components also allow the framework to support rare-event variance-reduction methods.

arXiv abstract · PDF

Software Assurance and Intelligent Agents · primary corpus · published 2026-09-18T03:52:46Z
Genliang Zhu, Chu Wang
arXiv categories: cs.PL, cs.AI, cs.CR

Long-running AI agents outlive initiating processes through credentials, delegated tasks, queues, callbacks, reservations, and provider-side operations. Cancellation, process exit, and credential revocation neither close every pre-cut carrier nor distinguish independently authorized shared work. We define root-scoped authorization quiescence: for each manifested sink, a certificate accounts for every cut-relevant acceptance under the retired root-epoch atom that precedes its local fence and excludes protected acceptance under that atom after the fence, while permitting exact rebind to a current, independently sufficient support. The root-scoped quiescence protocol linearizes a root cut, fences old-root expansion and protected sinks, represents alternative and conjunctive authority as antichains of minimal sufficient root sets, and composes provider-frontier certificates into a cutset over registered old-root paths. Exact channel-token accounting reconciles transfers; missing or conflicting evidence remains indeterminate. Under stated assumptions, we prove post-cut issuer non-expansion, support-sound projection, compositional soundness under exact channel conservation, independent-support preservation, merge-order independence, and crash/replay stability. A provider-free late-effect test suite matches 17/17 registered outcomes. Two cancellation-only and one cut-only execution accept the same class of already scheduled late effect; two cut-plus-fence executions, one restart, and one stale-process execution reject it. A separately implemented checker verifies 17/17 traces and rejects 44/44 consistently rehashed semantic regressions. The certificate establishes root-relative authorization quiescence within its bound manifest and configuration, not global idleness, rollback, or business completion.

arXiv abstract · PDF

Software Assurance and Intelligent Agents · primary corpus · published 2026-09-19T22:41:50Z
Nikolaos Kekatos, Theodoros Nestoridis, Charalampos Bratsas, Charalampos Dimoulas, Georgios Konstantinidis, Georgios Malogiannis, Michael Sirivianos, Andreas Veglis
arXiv categories: cs.CL, cs.CY, cs.LO

An automated fact-checking system returns a label: the claim is true, or it is false. In many such systems the verdict remains the primary output. What is generally missing is a record of which document settled the question, of what would have had to be different for the verdict to change, or of whether the same claim, reworded, would have been judged the same way. We call the missing piece a warrant: a separate statement of what was guaranteed and on what grounds. Formal methods produce evidence of this kind, and regulation is beginning to ask for it, since the Digital Services Act and the AI Act both call for auditable evidence about how systems behave. Surveys of automated fact-checking are usually organised by pipeline stage, and treat logic as one technique among many. We organise the field by what is being formalised instead, which gives five levels: the claim, the reasoning, the system doing the checking, the ecosystem the claim spreads through, and the regulatory obligation. Sorting 121 works into those levels, two patterns stand out. Most of the relevant formal machinery already exists, but it was built for other domains and has rarely been applied here, and the gap is widest for verifying the checking system itself. Several stages of the routine professional fact-checkers follow also have no stated correctness criterion, and two of them, writing a claim in checkable form and correcting a verdict already published, are not formally specified in any work we coded. We close with open problems, each with a suggested first step.

arXiv abstract · PDF