arXiv weekly literature review

Proof assistants and mechanized formalization · primary corpus · published 2026-08-17T09:52:54Z
Timon Böhler, Simon Daniel, David Richter, Pascal Weisenburger, Mira Mezini
arXiv categories: cs.PL

Choreographic programming is a programming model for developing distributed applications where an entire communication protocol is written as a single program, which a compiler then projects to one process per participant. Choreographic programming abstracts over low-level network communication primitives such as sockets, and provides a high degree of safety guarantees with deadlock freedom ensured by construction. Mechanizing choreographies necessarily deals with both operations specific to distributed programming and standard (local) operations that also occur in non-distributed programs, as well as the typical issues of binding and substitution. We aim to sidestep the latter issues, thereby obtaining a more concise mechanization that focuses on the essential distributed aspects of choreographies. To this end, we use a method recently proposed by Thiemann to elegantly model deadlock-free processes in a dependently typed language: Using state transformers to represent the computations performed by each process. We bring the state transformer model to choreographies, allowing us to reduce the usual mechanization effort around binding and substitution, and to abstract over the details of the "local" aspects of the language. We mechanize in Lean a choreographic language that supports point-to-point communication, broadcasting, recursive procedures, and local stateful methods, allowing each participant to be assigned a different set of methods. We prove soundness and completeness of endpoint projection, establish deadlock freedom for the projected processes, prove confluence, and verify a Hoare logic for choreographies.

arXiv abstract · PDF

Proof assistants and mechanized formalization · primary corpus · published 2026-08-18T10:54:15Z
Satpreet Makhija
arXiv categories: cs.AI, cs.PL

The $\operatorname{do}$-operator is described graphically by deleting arrows into its targets and functionally by replacing their mechanisms with constants. To call these operations equivalent is not yet a mathematical statement: one returns a graph and remembers only the targets, whereas the other returns mechanisms and also remembers the imposed values. We make a dependency-level comparison precise for deterministic acyclic structural causal models with finitely many endogenous variables. If $\operatorname{Graph}(F)$ extracts the dependencies of a mechanism family $F$, our main theorem is $\operatorname{Graph}(F^ι)=\operatorname{Surg}(\operatorname{Graph}(F),T_ι)$. Thus replacing target mechanisms removes exactly the dependencies removed by graph surgery. For a model $M=(G,F)$ whose graph may contain unused arrows, we characterize when the same equality holds with $G$ in place of $\operatorname{Graph}(F)$; it holds for every intervention exactly when $G$ records the dependencies of $F$ exactly. We then define the intervened model, characterize its run, show how sequential interventions combine, and prove that an outcome depends only on interventions at its actual dependency ancestors. All principal results are machine-checked in an accompanying Lean 4 development.

arXiv abstract · PDF

Proof assistants and mechanized formalization · primary corpus · published 2026-08-18T15:13:26Z
Ibrahim Mian, Shayaan Siddique
arXiv categories: cs.LO, math.NT

Erdős problem 647 asks whether any $n > 24$ satisfies $\max_{m<n}(m + τ(m)) \le n + 2$, where $τ$ is the divisor-count function. Computational searches have excluded solutions up to $10^{12}$ by direct sieve and up to roughly $9.17 \times 10^{18}$ within a modular reduction whose Lean component relies on native_decide; those computations sit outside any proof kernel. We give the first exclusion checked end to end by one: no solution exists with $24 < n \le 10^9$, proved in Lean 4 with axiom closure exactly {propext, Classical.choice, Quot.sound} -- no sorry, no native_decide, no problem-specific axiom. The proof replays a chain of 6,685,922 factorization witnesses whose excluded intervals concatenate across $(24, 10^9]$; it needs no primality facts beyond primes below 1024, and it is the finite, fully proved form of a domination-interval argument whose asymptotic step was the identified gap in a withdrawn January 2026 claim on this problem. The generation pipeline is cross-checked by two further independent implementations, the compiled development replays through the standalone lean4checker, and two from-source verification legs -- Lean toolchains compiled from source by gcc and by clang, mathlib rebuilt with no cache -- reproduce the committed certificates byte for byte, with olean digests identical across three builds on two architectures. Our range is three to ten orders of magnitude below the computational frontiers we cite; the contribution is the trust base, not the range.

arXiv abstract · PDF

Proof assistants and mechanized formalization · primary corpus · published 2026-08-19T02:20:59Z
Dmitry V. Alexandrov
arXiv categories: cs.LO, cs.AI, cs.CC, cs.PL

We present the first mechanised formalisation of Romanov's Triplet Logic (TLS) in the Rocq proof assistant. TLS is a triplet-based combinatorial framework for reasoning about compatible paths through layered triplet structures, called Compact Triplets Structures (CTS), and their intersection via Romanov's Effective Procedure, which we refer to as Simple Vertex Intersection (SVI). Originally motivated by Boolean satisfiability, TLS constitutes a self-contained mathematical theory whose formal properties had not been previously established. We formalise the core of TLS in Rocq, including Compact Triplets Formulas (CTF), CTS, hyperstructures, clearing, and SVI. For the well-formed sliding-window fragment we verify a clause-by-clause CNF-to-CTF translation, the clearing procedure, and aligned intersection, and we prove explicit polynomial-time bounds for the filter stages. Our main contribution is a precise correctness boundary: the existence of a joint satisfying set implies non-emptiness of SVI, but the converse does not hold in general; for aligned structures we recover a complete bi-implication, extended to systems of structures. We also formalise soundness of grouped-window translation and exhibit a formal counterexample to its completeness. We introduce VFR, an extracted OCaml prototype that provides a verified decision procedure for the sliding-window fragment and a sound one-sided filter for general 3-CNF, with a Python runtime and reproducible Docker packaging. Benchmarks on random and structured instances confirm the predicted behaviour, and the complete toolchain is available as a curated Zenodo artifact. The Rocq development comprises more than 23,000 lines of code across seventeen files, with 427 proved lemmas and theorems and zero admitted goals.

arXiv abstract · PDF

Proof assistants and mechanized formalization · primary corpus · published 2026-08-20T02:39:40Z
Shane Caldwell
arXiv categories: cs.LO, cs.AI, cs.CL

Formal proofs in Lean 4 that pass the kernel's type checker can nonetheless vary widely in quality. We introduce ProofJudge, an agentic LLM-as-judge system that scores formal proof quality along five dimensions beyond correctness: library leverage, automation fit, structural clarity, statement quality, and Mathlib conventions. We evaluate ProofJudge on a novel dataset of 218 declarations drawn from distinct Mathlib PRs. The judge agent is grounded by tool access to the commit the PR is applied to, enabling it to query the library state when scoring. A judge is considered aligned with human preferences when it rates the version of the PR Mathlib accepted above the initial version that was sent back for revision. All six judge models evaluated recover the reviewers' preference well above chance, from 80.8% to 63.5%, and two open-weight judges reach roughly 70% at a tenth of the best judge's cost. We release the judge harness, evaluation dataset, and evaluation traces as open-source artifacts to support further research.

arXiv abstract · PDF

Formalized mathematics and autoformalization · primary corpus · published 2026-08-17T05:48:42Z
Bryan Ford
arXiv categories: math.LO, cs.LO, cs.PL

By Tarski's undefinability theorem, no consistent classical formal system that includes arithmetic can define its own truth predicate. Reflective Grounded Arithmetic (RGA) is a powerful arithmetic whose universal quantifier is grounded in its own reflected proof search, and whose paracompleteness circumvents Tarski's theorem. This paper presents a machine-checked Isabelle/HOL development that defines a truth predicate for RGA's full language, quantifiers included, as an internal term of RGA itself. This term is compiled from a primitive-recursive decider for its operational semantics, and proven adequate in both directions. Around this predicate the development closes a square of metatheorems: for every formula RGA proves, RGA derives the formula's internal truth; every grounded-true formula is internally provable; internal truth implies internal provability; and the consistency of RGA follows. The two directions run on disjoint internal machines---a certified decider and a certified proof-checker, both RGA terms. Reaching these results involved substantial ordinary reasoning carried out within RGA: coded syntax and substitution, compiled primitive-recursive functions with symbolic unfolding laws, internal strong induction, and a verified proof-checker for the system written in the system's own formal language. The development thus demonstrates along the way that RGA is a workable formal system supporting nontrivial mathematical reasoning.

arXiv abstract · PDF

Formalized mathematics and autoformalization · primary corpus · published 2026-08-18T14:54:50Z
Bryan Ford
arXiv categories: math.LO, cs.LO, cs.PL

Grounded arithmetic is a family of formal systems for reasoning about computation in which a statement may be asserted only when a terminating computation backs it; the logics are paracomplete - for a sentence whose backing computation never settles, neither the sentence nor its negation is derivable, so paradoxes like the Liar are harmless rather than explosive. The reflective member of the family, RGA, can quantify over its own computations, but cannot certify that its own unbounded searches have definite yes-or-no answers. This paper studies what happens when that openness is closed by exactly one rule - ATI, the $ω$-grounded universal: if every numeric instance of a universal sentence is certified decided, the universal is certified decided. The resulting system, OGA, shares RGA's syntax and rules symbol-for-symbol otherwise, and every consequence is developed as a machine-checked theorem. Decidedness certificates become abundant - every totality question about a computable function is certified to have an answer, whether or not anyone can produce it - and this is exactly the provable separation between the two systems. OGA is complete for its own semantics; certified-but-unresolved sentences receive values built from the system's own open questions. Provability remains recursively enumerable, with a primitive-recursive certificate checker, while $ω$-truth deliberately is not. Within that asymmetry, incompleteness takes a new form. The Gödel sentence is classified, unconditionally, as a genuine fiction: neither provable nor refutable, yet valued, and carrying a computable pedigree recording exactly what adopting it as an axiom commits one to. The adoption is itself a theorem suite: extending OGA by any finite stock of true fictions is consistent, and independently certified adoptions can never collide.

arXiv abstract · PDF

Program verification, analysis, and software security · cs.SE candidate · published 2026-08-17T07:09:09Z
Mikhail Surikov
arXiv categories: cs.CR, cs.AI, cs.SE

AI-assisted development tools generate vulnerable code at significant rates, yet few automated mechanisms exist to detect, enrich, fix, and verify security issues at development velocity, particularly ones that ground remediation in real-world threat context. This paper presents an automated security evaluation pipeline that generates Python code from LLMSecEval prompts, scans for vulnerabilities using CodeQL and Bandit in parallel with an independent Code Validator LLM, enriches the Code Validator findings with MITRE ATT&CK techniques, CWE Observed Examples, and Python best practice guidelines, generates fixes via the Code Generation LLM, and re-scans with CodeQL and Bandit to verify outcomes. Two pipeline configurations were evaluated: Pipeline 1 (P1), using enriched Code Validator findings only, and Pipeline 2 (P2), where it additionally receives the initial CodeQL and Bandit findings. Both configurations were run across four Claude models: Opus 4.8, Sonnet 4.6, Sonnet 5, and Haiku 4.5, producing 80 runs against 26 LLMSecEval prompts covering 9 CWE categories. P1 reduced static analyzer findings across all four models, ranging from -9% (Opus 4.8) to -54% (Sonnet 5). P2 deepened these reductions further, ranging from -29% (Opus 4.8) to -69% (Haiku 4.5), with P2 outperforming P1 for every model. Verdict consistency averaged approximately 81% modal agreement across all configurations, with P2 marginally more stable than P1. Remediation introduced new vulnerabilities in 15-22% of cases: roughly 70% involved a single new finding, and P2 reduced churn for three of four models, with Sonnet 5 as the sole exception. Notably, the best Code Generation LLM (Opus 4.8) was not the best pipeline performer, as Sonnet 4.6 produced the lowest residual findings and highest pass rate after P2 remediation, suggesting that pipeline effectiveness and first-draft security are distinct properties.

arXiv abstract · PDF

Program verification, analysis, and software security · cs.SE candidate · published 2026-08-17T08:16:31Z
Omur Sahin, Andrea Arcuri
arXiv categories: cs.SE

Context: REST APIs are widely used in industry. These APIs use HTTP for their communications. Failures in following the specifications of HTTP can lead to confusing and hard to use APIs, with possibly serious software faults with dire consequences. Objectives: Define novel automated techniques to automatically find HTTP semantics-level faults in existing REST APIs. Methods: We extended the state-of-the-art fuzzer EvoMaster with 9 new oracles to detect HTTP semanticslevel faults. Once the standard fuzzing process is finished generating N test cases, a new phase is executed in which these N tests are used as a starting point to create new scenarios (i.e., new sequences of HTTP calls) aimed at validating specific HTTP properties defined in these 9 oracles. Results: Experiments on 9 artificial APIs with inject faults show that our novel techniques can successfully detect all of them. Further experiments on 36 APIs from the WFD corpus show that our novel techniques can automatically find 166 existing faults in these real-world APIs. Conclusion: REST APIs use HTTP, and, as such, they need to follow its semantics to avoid misleading their clients and introducing subtle software faults. The novel techniques presented in this paper are shown to be effective at automatically finding several of this type of faults.

arXiv abstract · PDF

Program verification, analysis, and software security · primary corpus · published 2026-08-17T19:19:19Z
Youwei Zhong, Ben Merbaum, Timos Antonopoulos, Ning Luo, Charalampos Papamanthou, Katerina Sotiraki, Ruzica Piskac
arXiv categories: cs.LG, cs.CR, cs.LO

With the growing deployment of machine learning models, formal guarantees of the robustness and fairness of these models have become increasingly important in safety-critical and legal-compliance settings. However, model parameters are often commercial secrets that cannot be disclosed to auditors or end users. To this end, we present PANDA, a scalable system that uses zero-knowledge proofs (ZKPs) to prove the robustness and fairness properties of a model without revealing its private parameters. PANDA is built on top of CROWN, an efficient robustness certification framework that is used in many state-of-the-art formal verification tools for neural networks. The core contribution of PANDA is a novel algorithm for proving linear relaxation bounds for non-linear activation layers, yielding simple, lightweight proofs. Remarkably, our system can generate proofs of local robustness for neural networks with more than 2.9M parameters in 5 minutes, and can verify them in 10 seconds. Prior ZKP-based robustness system rely on exponential-time algorithms that cannot scale to nontrivial networks. In contrast, PANDA scales polynomially in the number of neurons in a network, allowing us to support neural networks 4 orders of magnitude larger than previous approaches with significantly reduced prover overhead.

arXiv abstract · PDF

Program verification, analysis, and software security · primary corpus · published 2026-08-18T13:03:22Z
Seokhun Jeong, Gyeongmin Dan, Sukyoung Ryu, Sungjae Hwang
arXiv categories: cs.SE, cs.CR, cs.PL

Ethereum's consensus safety relies on independent consensus client implementations agreeing on every state transition. When they diverge due to implementation errors, the network can fork, finality can stall, and severe attacks are possible. To prevent such consensus divergences, Ethereum provides a Python reference implementation (consensus-spec), which acts as a specification, and a hand-crafted official test suite (spectests). However, as an executable implementation, Ethereum's specification defines validity implicitly through runtime behavior. As a result, it lacks a systematic way to ensure that all validity conditions are thoroughly evaluated. We present SpecTrum, a framework that addresses this problem in three stages. First, we introduce Consensus-SpecTec, a mechanized specification of the Ethereum consensus algorithm, which makes validity conditions explicit as if-premises. Second, we define premise coverage, a metric that measures which if-premises are evaluated to true and false across spectests. Third, we develop a specification-based test generator that extracts constraints on premises not evaluated to false by spectests and generates inputs to evaluate them. Applying SpecTrum to five major Ethereum consensus clients, we identify 27 cross-client divergence cases, 22 of which cannot be found without the premises inserted in our mechanization. All 27 cases reproduce across fork versions, and extending the mechanized specification to a new fork takes modest effort proportional to the specification difference.

arXiv abstract · PDF

Program verification, analysis, and software security · primary corpus · published 2026-08-18T21:24:57Z
Dinghong Zhong, Alexander Bai, Mikail Khan, Guannan Wei
arXiv categories: cs.PL

Concolic execution is a variant of symbolic execution that runs a program simultaneously with concrete and symbolic inputs. It records the symbolic constraints encountered along a concrete execution path, then solves those constraints to generate inputs that explore new paths. Existing concolic engines generally follow one of two implementation strategies: Interpreter-based systems are comparatively simple to build but incur substantial interpretation overhead, while instrumentation-based systems avoid this overhead but typically re-execute the program from the beginning for each new input. In this paper, we develop a new approach that achieves the best of both worlds. Starting from the concrete semantics of the target language, we first develop a definitional concolic interpreter and stage it to compile away interpretation overhead while retaining the simplicity of an interpretation-based implementation. By expressing the staged interpreter in continuation-passing style, we can capture execution snapshots at branch points and resume from them when exploring alternative paths, avoiding repeated execution from the program entry. Because snapshot-reuse can itself incur overhead, we further develop a heuristic that favors snapshot-reuse only when it is expected to be beneficial. We instantiate this approach for WebAssembly and implement it in a new concolic-execution compiler GenWasym. Across 184 benchmarks, GenWasym with staging alone achieves a $29.4\times$ average speedup over the interpreter-based WASP; heuristic snapshot-reuse further increases the speedup to $44.9\times$.

arXiv abstract · PDF

Program verification, analysis, and software security · primary corpus · published 2026-08-19T14:40:05Z
Emma Ahrens, Samuel Rode, Philipp Schröer, Joost-Pieter Katoen
arXiv categories: cs.PL

Weighted programs extend guarded commands with trace weights drawn from a semiring, or more generally a monoid-module. Varying this algebra gives one programmatic syntax for a variety of quantitative and symbolic models. Weakest-preweighting semantics provides a compositional basis for reasoning about those programs. We present a deductive verification framework based on a weighted assertion language and an intermediate verification language. Its weight domains are ordered structures with implication and coimplication, which let verification conditions express lower- and upper-bound obligations internally. We prove sound translations of core commands and reusable encodings for various proof rules applying to procedure calls and loops. To facilitate automation, we prove soundness of a quantifier elimination procedure for our assertion language. A prototype in the Caesar verifier checks case studies for probabilistic queueing costs, recursive database provenance with cyclic dependencies, clearance bounds for networks of arbitrary size, and formal-language reasoning about lock-freedom of a compare-and-swap counter.

arXiv abstract · PDF

Program verification, analysis, and software security · primary corpus · published 2026-08-20T02:28:27Z
Jiawen Liu, Weihao Qu, Marco Gaboardi, Deepak Garg, Jonathan Ullman
arXiv categories: cs.PL

Data analyses are usually designed to identify some property of the population from which the data are drawn, generalizing beyond the specific data sample. For this reason, data analyses are often designed to produce a low generalization error, so that the result of an analysis on sample data does not differ too much from the result one would achieve over the entire population. An adaptive data analysis can be seen as a process composed of multiple queries interrogating some data, where the choice of which query to run next may rely on the results of previous queries. The generalization error of each individual query can be controlled using well-established statistical techniques. However, when queries are arbitrarily composed, errors can propagate through the chain of queries and lead to high generalization error. To address this issue, several techniques guarantee bounds not only on single queries but also on composed analyses. The choice of technique often depends on the chain of queries that an adaptive data analysis can generate. In this work, we consider adaptive data analyses implemented as while-like programs and design a program analysis to help identify which technique to use to control their generalization errors. More specifically, we formalize the intuitive notion of adaptivity as a quantitative property of programs. Based on this definition, we design a program analysis for soundly approximating this quantity. The analysis represents the data analysis as a weighted dependency graph, where weights upper-bound how often variables can be reached, and uses a path-search strategy to upper-bound adaptivity. We implement our program analysis and show that it can analyze several concrete data analyses with different adaptivity structures.

arXiv abstract · PDF

Program verification, analysis, and software security · primary corpus · published 2026-08-20T06:07:56Z
Peter Sewell, Jean Pichon-Pharabod
arXiv categories: cs.PL, cs.AI, cs.SE

Computing has been an astonishing success - but the accumulated technical debt exposes us all to huge costs in business and societal risk. For 75 years, we've built systems to prose specifications with test-and-debug development. That works well enough for industry to thrive, but it's an expensive and ineffective feedback loop, and leaves everyone relying on shaky foundations. Now, AI-enabled engineering is amplifying the success by reducing coding costs, but also amplifies the risks, by rapidly increasing technical debt, and by automating detection of the vulnerabilities therein. How can we do better? Research has long pursued mathematical proof of correctness, which, unlike testing, can cover all cases. This too has advanced massively, but it remains hard to apply, both technically and because of a deep-seated cultural disconnect. Instead, we argue for a pragmatic approach to flexible combinations of testing, *specification*, and proof, that provides more effective feedback loops for both AI and human development. Most simply, one can incrementally co-develop executable-as-test-oracle partial specifications alongside conventional prose descriptions, code, and tests. This clarifies design and makes testing much more discriminating. Developers can and should do it today. Or, even better, one can use specifications that support the full gamut of testing, property-based testing, symbolic execution, and proof. This enables a range of intertwined feedback loops, again both for AI and humans, from cheap testing to more expensive proof. However, making it really practical needs *semantics infrastructure*: specifications and tooling for the main programming languages and other abstractions, which we now more-or-less know how to build, but which is not yet in place. We call the community to arms to create and deploy it - to enable a future built on firmer ground.

arXiv abstract · PDF

Programming-language semantics, types, and calculi · primary corpus · published 2026-08-20T07:26:46Z
Owen Lynch, Sam Staton
arXiv categories: cs.PL, cs.LO

In this paper we introduce Hippogriff, a language with a module system that unifies syntax between the core level and the module level. Hippogriff's type theory is dependent, with modularity features enabled via a universe of small types, but Hippogriff still supports general recursion without making typechecking nonterminating. This paper contains two halves. In the first half, we describe Hippogriff and its implementation. In the second half, we build categorical semantics for our use of dependent types that justify the use of general recursion at the value level. Specifically, we use an extension of the second-order generalized algebraic theory framework to include a synthetic phase distinction, and this allows us to make a mathematical connection between dependent type theories and split-context type theories (like System F). Included as supplements are a Haskell implementation of Hippogriff and an appendix describing the full type theory of Hippogriff using a second-order generalized algebraic theory with phase distinction.

arXiv abstract · PDF

Programming-language semantics, types, and calculi · primary corpus · published 2026-08-21T02:22:38Z
Gavin Gray, Shriram Krishnamurthi, Will Crichton
arXiv categories: cs.PL

Many modern programming languages include some form of asynchronous programming. In particular, a growing number now have what we call straight-line asynchrony: attempts to provide asynchronous functions that look similar to synchronous functions, thereby enabling asynchrony without introducing complex control. These languages often share construct names like "async" and "await," which suggests that they have deep semantic similarities. Yet, a close examination reveals that these languages are quite different along several dimensions, often subtly. These differences have real semantic consequences: similar-looking programs can exhibit divergent behavior, confusing developers and language designers alike. This paper therefore presents a design space exploration of straight-line asynchrony. We dissect several existing languages, and show how no two of them agree as a whole on design decisions that affect the presence and ordering of execution. We articulate a design space with nine dimensions covering the full lifecycle of an asynchronous computation, covering questions such as: What precise guarantees does a language give upon calling an asynchronous function? What happens at the end of a task's life? How can a task handle being cancelled? We explore these questions through concrete examples, informal design discussion, and a formal semantics. Our ultimate goal is to help programmers, language designers, and language theorists all better understand the emerging landscape of straight-line asynchrony.

arXiv abstract · PDF

Programming-language semantics, types, and calculi · primary corpus · published 2026-08-21T16:26:20Z
Orpheas van Rooij, Ohad Kammar, Sam Lindley, Cristina Matache
arXiv categories: cs.PL

Full ground local state (FGLS) refers to dynamically allocated mutable state that allows storing ground values and references. It is a key ingredient in many imperative algorithms as it enables (cyclic) data structures. In this work, we treat full ground local state as a computational effect, focusing on one particular denotational model: Kammar et al.'s possible worlds monad on sets indexed over sets of locations. We resolve an outstanding question regarding this FGLS monad: is it finitary? We show that the FGLS monad is not finitary by showing the existence of non-finitary computations in the monad. We then introduce a finitary submonad of Kammar et al.'s monad, give it a concrete description and show that it provides an adequate semantics for FGLS. The submonad we construct paves the way to understanding FGLS in the future via an equational axiomatization suitable for program reasoning.

arXiv abstract · PDF

Compilers, code generation, and programming tools · primary corpus · published 2026-08-18T18:11:56Z
Timothy J. R. Stokes, Nick Brown, Thomas A. Flynn, Maurice Jamieson, Tobias Weinzierl
arXiv categories: cs.MS, cs.PL, gr-qc, math.NA

We introduce a bilingual domain-specific language (DSL) for modelling compute kernels within a generic solver for hyperbolic partial differential equations (PDEs). Users express PDE terms, i.e.~the underlying physics, in a familiar native language such as C or C++, while the numerical scheme is specified in a Python-embedded DSL, DSLHyPE. DSLHyPE's compiler lowers the Python description to MLIR and introduces a translation pass that integrates it with native code likewise mapped to MLIR. Our approach keeps the numerical representation and the physics implementation separate for as long as possible, while delegating optimization to the compiler through existing MLIR optimization passes. This separation of concerns benefits researchers developing numerical schemes on top of existing PDE implementations or with applications involving nonlinear systems whose PDE terms must solve PDEs themselves. We demonstrate the feasibility of the approach using a gravitational-wave solver and a matter-evolution solver on x86 processors and H200 GPUs.

arXiv abstract · PDF

Compilers, code generation, and programming tools · primary corpus · published 2026-08-18T21:29:13Z
Prajwal S. Venkateshmurthy
arXiv categories: cs.SE, cs.PL

There is no shared framework for selecting among document compilation engines (pdfLaTeX, XeLaTeX, LuaLaTeX, Tectonic, Typst, and pandoc PDF backends). We present Engine-Transfer-Bench (ETB): 1,784 open documents, four tasks covering reliability, latency, text consistency, and failures, a pinned harness, and host-tagged multi-OS results. On GitHub Actions (N=4,211 compiles per host across macOS, Ubuntu, and Windows), Tectonic success is stable within 0.9 percentage points (96.3-97.2%), whereas classic TeX Live-style engines vary by 12-20 percentage points according to distribution policy (Ubuntu apt, MiKTeX auto-install, or macOS BasicTeX). On 702 portable LaTeX documents, the tested engines succeed at 100%, making latency the primary selection factor; failures concentrate in 107 engine-specific templates. Within ETB, failures are architectural, involving fonts, layout, and assets, rather than missing packages on a provisioned host. A 50-pair validation of the S_pdf text-consistency metric achieves 94% precision for real content divergence. We release ETB, ETB-Porta, a recommender and portability gate, and a public cross-OS harness as shared infrastructure.

arXiv abstract · PDF

Compilers, code generation, and programming tools · primary corpus · published 2026-08-20T10:56:34Z
Jacob Nielsen, Danial Namazifard, Lukas Galke Poech, Peter Schneider-Kamp
arXiv categories: cs.AI, cs.PL

The entire ecosystem of open-source language models effectively relies on a single platform. What if this platform was forced to shut down tomorrow? Implementing and maintaining efficient model definitions and translating them between different training and inference regimes is a resource-heavy task that severely limits model efficiency and portability, hindering both scaling and deployment. Here, we present Axon, a strongly typed domain-specific language with Haskell-like syntax, that enables a write-once, run everywhere paradigm for LLM architectures. By basing collaboration on a language specification rather than a specific framework's vision, Axon fosters open cooperation and empowers researchers to implement highly specialized architectures without giving up optimization infrastructure or accepting deployment lock-in. Axon allows for concise, auditable specifications that can be automatically compiled to standalone implementations for leading frameworks: PyTorch, PyTorch with Triton, JAX, MLX and vLLM. In 467 inference benchmarking experiments on models ranging from 135M to 32B parameters, we demonstrate median speedups of 7% on PyTorch, 12% on PyTorch with Triton, 91% on JAX, and 107% on MLX, compared to the reference implementations from Transformers. When deployed as native vLLM architectures with PagedAttention and KV-cache, Axon models achieve a 58% median speedup over Transformers implementations.

arXiv abstract · PDF

Compilers, code generation, and programming tools · primary corpus · published 2026-08-20T15:02:11Z
Nikil V. Shyamsunder
arXiv categories: cs.PL, cs.PF

Modern optimizing compilers rely on heuristic search algorithms for NP-hard optimization problems, which can result in poor generated-code performance and long or unpredictable compile times. These are considered bugs by users, but verified compilers rarely reason beyond semantic preservation. We propose verifying performance and compile time properties of compiler passes. As a proof-of-concept, we formulate inline expansion using a cost model estimating instruction-cache performance. We mechanize this in Rocq, prove semantic preservation of the inlining transformation, and verify the algorithm's monotone improvement, convergence-time bound, and performance bounds for intermediate and final solutions.

arXiv abstract · PDF

Compilers, code generation, and programming tools · primary corpus · published 2026-08-20T21:49:07Z
Ronald M. Caplan, Miko M. Stulajter, Jon A. Linker, Jeff Larkin, Nikolaos Tselepidis, Harald Servat, Shiquan Su, Giacomo Capodaglio, Johanna Potyka
arXiv categories: cs.PL, astro-ph.IM, astro-ph.SR, cs.CE, cs.DC

There continues to be growing interest in using standard language constructs for parallel and accelerated HPC computing, avoiding the need for (sometimes vendor-specific) external APIs. For Fortran applications, language features such as 'do concurrent' loops open the door for compilers to implement multi-threaded, GPU-accelerated, and even distributed multi-node code with only the standard language. Here, we explore the current status of using 'do concurrent' for GPU-accelerated Fortran applications across three major GPU vendors (NVIDIA, AMD, and Intel). Using a production application, we test their current capabilities, showing where the standard language alone can be used, and where augmenting the code with a directive-based API (e.g., OpenMP) is still desirable or required. Multi-GPU tests are performed with GPU-aware MPI libraries. We find that the three GPU vendors can now GPU-accelerate pure Fortran (zero directives), but that manual data movement directives can help with performance and compatibility. The results show that there is rapid advancement towards making GPU-accelerated scientific HPC code performance portable using the Fortran standard language.

arXiv abstract · PDF

Compilers, code generation, and programming tools · primary corpus · published 2026-08-20T22:56:42Z
Jingyu Qiu, Rongcui Dong, Sreepathi Pai
arXiv categories: cs.PL

Current basic block profiling techniques obtain the count of executions of each basic block in a program using dynamic instrumentation. These profiling counters create runtime overheads and also require the execution of the program, which, for large input sizes, can take substantial time. We propose symbolic program profiling that generates symbolic formulae for a basic block's count with inputs as the independent variables. Our technique is limited in applicability to a certain class of programs, namely machine learning (ML) kernels. We implement our technique in the LLVM compiler and evaluate it on 78 ML operators from 50 different ML models. These operators are generated by TVM, a machine learning compiler. Our symbolic profiles deliver exactly the same results as dynamic instrumentation for 73 out of 78 kernels with a median speedup of 15093x.

arXiv abstract · PDF

Compilers, code generation, and programming tools · primary corpus · published 2026-08-21T06:41:04Z
Ruihang Fan, Jiajun Jiang, Xinpeng Wang, Jiateng Fu, Fengjie Li, Jiasi Shen
arXiv categories: cs.SE, cs.PL

Automated code translation is increasingly important for software evolution, yet the relative strengths and limitations of learning-based and large language model (LLM)-based techniques remain insufficiently understood. To address this gap, we conduct a large-scale empirical study comparing representative code translation techniques across methodological paradigms and translation granularities. We evaluate learning-based methods, LLM-based methods, and general-purpose LLMs on multilingual method-level and class-level benchmarks involving multiple programming languages. Our analysis considers executable correctness, code similarity, translation direction, translation granularity, and failure patterns. The results show that LLMs and LLM-based methods generally outperform learning-based methods in method-level correctness, although similarity metrics alone do not reliably reflect functional correctness. Translation direction substantially affects performance, particularly when translating between languages with different type-system characteristics. Class-level translation remains considerably more difficult than method-level translation because it requires preserving global semantics, interfaces, member relationships, and cross-method dependencies. Our error analysis further shows that static semantic errors and logical errors are the primary challenges in existing code translation systems. These findings provide empirical evidence and practical guidance for developing more robust, type-aware, structure-aware, and context-aware code translation techniques.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · cs.SE candidate · published 2026-08-17T02:27:10Z
Li Li, Han Hu, Tianjian Zhang, Xin Peng, Fangzhu Mao, Qingyu Zhang, Xiaoheng Xie, Zhongmin Tang, Zhihao Lin, Haolin Ruan, Miaomiao Dong, Liuchuan Zhu, Yue Li, Chi Chen, Wenkang Zhong, Mingfei Zhang, Yang Yu, Bo Sun, Chaorui Zhang, Weixi Zhang, Wei Han, Bo Bai, Kui Liu, Gang Fan, Siru Liu, Jiaqian Zhou, Jiali Sun, Yunbiao Dong, Wenhao Zhong, Yunhong Xu
arXiv categories: cs.SE

We present OPENHARMONY BENCH, an app-level coding benchmark for evaluating LLM-based coding agents on OpenHarmony ArkTS applications. Unlike function-level benchmarks, it evaluates complete app-level changes: each task requires an agent to modify a buildable ArkTS project so that a requested behavior works end to end, involving UI state, data persistence, build configuration, and platform APIs. The benchmark installs and drives the delivered application on a device to check whether the behavior is observable. It covers three input sources: natural-language feature requests (new-feature), structured scenario specifications (spec-driven), and bug descriptions (bug-fix). The benchmark contains 153 top-level tasks and 242 Feature points (F-points), where an F-point is one executable behavior check. The snapshot includes 32 new-feature tasks, 50 spec-driven tasks with 139 F-points, and 71 bug-fix tasks. The main leaderboard is scored over top-level tasks rather than independently weighted F-points. We describe the benchmark construction, statistics, and build-and-test evaluation pipeline, and evaluate DevEco Code with eight LLMs across three independent full-suite runs per configuration. Three findings emerge. First, newer generations complete more tasks than their predecessors within evaluated model-family pairs. Second, buildability is close to saturated while behavioral correctness is not: mean Final Build Success Rate is 94.77% to 100.00%, whereas mean Task Completion is 48.36% to 58.39%. Third, spec-driven tasks have the lowest Task Completion under all-checks task scoring, with no configuration exceeding 35%. The code, data, tasks, reference solutions, tests, evaluation scripts, and leaderboard are released through the official OPENHARMONY BENCH website at https://bench.matrix.openharmony.cn/.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · cs.SE candidate · published 2026-08-17T11:07:07Z
Yintong Huo, Rangeet Pan, Abhik Roychoudhury
arXiv categories: cs.SE, cs.AI

LLM-based agents are rapidly moving from research prototypes into the core business processes of organizations, but these agents pose deployment risks to security, compliance, and functionality. In this article, we argue that risk-free deployment must be grounded in the agent's trajectory: the recorded sequence of reasoning steps, tool invocations, and environmental observations. Trajectories are available for any agent, and many failures are visible only in the trajectory. To make agents deployable and sustainable, we advocate agent testing and debugging as a systematic research direction for detecting and mitigating these risks. This article begins with the challenges of testing agents, including the oracle problem, non-determinism, trajectory validation, and the absence of adequacy metrics. We then turn to debugging agents, from automated failure attribution to repair and self-evolution. We distill these directions into a practical deployment-readiness checklist covering the full deployment lifecycle. Finally, we identify open problems, i.e., formal adequacy metrics, root-cause attribution over long-horizon trajectories, and the reliability of self-evolving agents, that the community must address to enable trustworthy agent deployment.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · primary corpus · published 2026-08-17T14:19:14Z
Tassio Sirqueira, Jessica Faciroli
arXiv categories: cs.SE, cs.PL

The growing adoption of Large Language Models (LLMs) in Software Engineering has reinforced the expectation that coding activities can be largely automated. However, this perception may represent yet another historical search for a solution capable of eliminating the inherent challenges of software development. This article discusses the transition from a code-centered paradigm to Specification-Driven Development. We argue that artificial intelligence reduces some of the effort associated with writing source code, but it does not eliminate the complexity of developing professional software systems. Instead, it shifts this complexity toward domain understanding, requirements elicitation, specification development, validation, maintenance, and software evolution. Building on this perspective, we discuss the renewed centrality of Requirements Engineering, considering its implications for productivity and software quality, as well as risks associated with automation bias, ambiguity propagation, Specification Overfitting, and the accumulation of Specification Debt. Finally, we propose the Specification Paradox: the more capable artificial intelligence systems become at automatically generating software, the greater the dependence on correct, complete, verifiable, and explainable human-produced specifications. We conclude that the future of Software Engineering will depend not only on machines' ability to generate code, but also on humans' ability to correctly specify, evaluate, and evolve what is intended to be built.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · cs.SE candidate · published 2026-08-17T14:30:41Z
Bardia Mohammadi, Lars Klein, Aman Chadha, Akhil Arora, Laurent Bindschaedler
arXiv categories: cs.SE, cs.AI, cs.LG

Repository-scale coding requires an agent to keep tests, imports, configuration, and migration rules consistent within a bounded context window. We model this as reconstructing a coupled-fact graph: at each edit, a required fact comes from recent context or parametric memory, and the facts covered by neither form coherence debt. We supply and withhold each channel and inject faults across seven models and five harnesses. As expected, no model completes a task on an unseen API with both channels empty, and putting the facts in the prompt restores success. When a rename defeats what models memorized about a real library, all seven fail in the same place, passing and missing the same tests. Availability decides the outcome and distance does not: withholding a fact costs exactly the work it supports, and a supplied fact works as well far from the edit as next to it. Harnesses pay unequal prices for it: configurations that all pass every test differ more than tenfold in tokens consumed because they rebuild the same content at different rates, and spending more recovers nothing when facts are withheld. A missing fact produces wrong work rather than absent work: an agent asked to act acts, fabricating the file or guessing the value, so instruments built on reads look for a hole already filled. How often it says it is blocked instead is a property of the model, from every trial to none. Availability does not settle every edit: where standard and code disagree, agents follow the standard even when it prescribes the worse code, so a stale convention file costs more than no file. Because parametric memory substitutes for reading, on SWE-bench, where models likely know the repositories, reads no longer predict success. Harnesses should keep the facts an edit depends on available when the agent writes, and check that availability against what the agent produces rather than what it reads.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · cs.SE candidate · published 2026-08-17T15:52:04Z
Hongyue Yu, Kefan Li, Jiakun Li, Hongzheng Chai, Yuan Yuan, Rui He, Junyi Wei
arXiv categories: cs.SE, cs.AI

Large Language Models (LLMs) have achieved remarkable progress in code generation, yet ensuring correctness in complex, repository-level tasks remains challenging. Existing approaches often use generated tests as static post-hoc validators, which limits their ability to guide implementation and may introduce misleading feedback when the tests themselves are incomplete or incorrect. In this paper, we introduce TDD-Agent, which operationalizes the test-driven development paradigm for code generation. TDD-Agent first prompts the model to generate executable tests, encouraging it to clarify expected behaviors before implementation, and then performs iterative dual-track refinement over both the generated code and tests using execution feedback. We first isolate the effect of test-first reasoning through a prompt variant TDD-prompt on LiveCodeBench, where it consistently improves upon reasoning-based prompting baselines. Building on this finding, we evaluate the full TDD-Agent framework on RepoEval, a repository-level benchmark, and show that it consistently outperforms retrieval-based and agent-based baselines. Additional analyses show that iterative refinement improves not only code correctness but also the effectiveness of the generated tests, yielding higher pass rates, coverage, and mutation scores, suggesting that tests can serve as evolving reasoning artifacts rather than fixed validators. Our source code is available at https://anonymous.4open.science/r/TDD-Agent-Framework-6370/.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · cs.SE candidate · published 2026-08-17T16:57:38Z
Giuseppe Destefanis, Tomaso Aste
arXiv categories: cs.AI, cs.SE

We study how teams of AI coding agents coordinate while solving programming tasks. Current evaluations usually report whether the agents complete the task and how much the run costs, leaving the coordination inside the team largely unmeasured. We introduce an instrument to measure this coordination. Each run is represented as a temporal network in which agents and files are nodes, and messages, file writes, and file reads are timestamped directed edges with an associated cost. We apply this instrument to 1902 runs, each evaluated with a fixed test suite, across configurations that vary the team size, the team structure, and the file policy. The resulting networks show how coordination changes as teams grow and as the work changes. Direct messaging initially increases close to quadratically with the number of agents, with much of this growth coming from an early round of introductions. As the teams grow further, this increase levels off in the largest teams we study, where agents increasingly communicate through broadcast messages. The task also shapes the network that emerges. Work built around a shared specification produces dense, highly connected teams, while pipeline tasks produce sparse networks organised around local interfaces. Shared files can replace repeated 1-to-1 communication, cutting output tokens by about 42% at eight agents on message-heavy work, while adding overhead when files already carry the coordination. Naming one agent as coordinator creates no communication hub and provides no reliable improvement in success. We also observe an unprompted tendency for agents to seek out hidden grading material. We repeat the key experimental conditions in a sealed environment, replacing the hidden material with marked placeholder files. Across 244 additional runs, agents still reach for it in four fifths of runs, while the coordinator and file-channel findings reproduce.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · cs.SE candidate · published 2026-08-17T18:11:55Z
Yuanchen Gao, Yifang Tian, Yiran Li, Charles Zhang, Hans-Arno Jacobsen
arXiv categories: cs.SE

Microservice failures are often diagnosed from operational telemetry. However, automated program repair systems usually start from issue reports, localized code context, or failing tests. This mismatch leaves a gap between telemetry-based diagnosis and patch generation. We present ORCA, an observability-grounded APR pipeline for microservice incidents. ORCA first distills the differences in paired failure and reference telemetry into a fault signature, then uses the signature to identify candidate code and deployment-configuration locations. Repair graph agents and an Exploration agent generate unified-diff patch candidates from these locations. ORCA evaluates generated patches with a Telemetry-Grounded Patch Verifier that separates patch validity, syntactic and semantic correctness, test-oracle integrity, and telemetry replay. On a 575-case benchmark, ORCA outperforms all evaluated baselines in terms of cost-effectiveness. Results show that operational telemetry can be transformed from diagnostic evidence into actionable repair context: paired telemetry supports repair-oriented localization, while repair graph agents convert localized code and configuration evidence into constrained patch-generation context for the LLM. Telemetry-grounded verification then exposes repair outcomes that issue- or test-only evaluation would miss.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · primary corpus · published 2026-08-17T20:27:45Z
Bryan Lima Cavalcante, Thiago Alves Rocha
arXiv categories: cs.LG, cs.AI, cs.LO

Graph Neural Networks (GNNs) have achieved remarkable performance in node classification tasks, motivating growing interest in methods capable of explaining their predictions. Recent logic-based approaches, such as LogicXGNN, derive global logical rules for Graph Neural Networks (GNNs) from collections of explanatory subgraphs. While informative, these subgraphs may contain redundant structural information that is specific to individual nodes, potentially limiting the generality of the extracted rules. In this work, we propose a logic-based framework for node classification in Simple Graph Convolution (SGC) networks that uses minimal abductive explanations as an intermediate representation for rule extraction. For each node, we compute a minimal set of node-feature pairs sufficient to preserve the predicted class. These explanations are then used to train decision trees from which global logical rules are extracted. Experiments on benchmark datasets show that the proposed framework produces compact global rules while maintaining high fidelity to the original SGC model.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · cs.SE candidate · published 2026-08-17T22:36:12Z
Michele Tufano, James McClure, José Cambronero, Runxiang Cheng, Sherry Y. Shi, Renyao Wei, Dorothy Chen, Franjo Ivančić, Livio Dalloro, Pat Rondon
arXiv categories: cs.SE

LLM-based agents are increasingly used for coding tasks, where they have outperformed many classical approaches and scaled to repository-level tasks, such as test generation. However, when directly prompted to generate tests, these agents can fail to reason about the code and its underlying contracts, thereby missing edge cases and behavioral boundaries that affect test quality. To address this limitation, we propose Spec-Driven Test Generation, where we instruct an agent to first reason about -- and explicitly document -- code pre-conditions, post-conditions, and undefined behaviors. This intermediate semi-formal specification acts as a cognitive scaffold to guide subsequent test generation. Our evaluation on production bugs from Google shows that the spec-driven agent can deliver a 9.8 percentage points ($p = 0.0352$) improvement in bug detection rate and a 2.5 percentage point ($p = 0.0034$) improvement in branch coverage, compared to a traditional test generation agent baseline. Using LLM-as-a-Judge, we further show that test suites generated by the spec-driven agent are superior to the baseline and human-authored tests in 77.8% and 56.7% of the cases, respectively, and demonstrated improvements on following best practices, readability, and edge-case coverage.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · cs.SE candidate · published 2026-08-17T23:17:04Z
Charlie Jyu, Shuyang Liu, Reyhaneh Jabbarvand
arXiv categories: cs.SE, cs.AI

We present Graphectory Viewer, a web-based tool for interactive, process-centric analysis of software-agent trajectories. Building on the Graphectory representation introduced in our previous work, Graphectory Viewer transforms heterogeneous raw trajectories into phase-aware graphs that connect low-level execution details with higher-level behavioral structures. The tool supports trajectories from multiple agent frameworks and provides interactive graph construction; node-level inspection of thoughts, actions, and observations; search and filtering over large trajectory collections; and Sankey-style summaries of problem-solving phase transitions. These capabilities enable researchers and practitioners to inspect individual executions, identify recurring behavioral patterns, compare successful and failed runs, and analyze large trajectory corpora beyond final task outcomes. To support reproducibility and further research, we release Graphectory Viewer as an open-source artifact together with documentation, precomputed graphs, and the large-scale trajectory corpus.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · primary corpus · published 2026-08-18T06:26:45Z
Yuanbang Liu, Chenxi Ruan, Yihan Hou, Qiong Luo, Wei Zeng
arXiv categories: cs.CV, cs.PL

Chart editing requires inferring and modifying visualization code from a reference chart image based on an editing instruction, challenging fine-grained visual reasoning, instruction following, and executable code synthesis capabilities of MLLMs. Large reasoning models (LRMs) with extended Chain-of-Thought (CoT) reasoning are suitable for tackling such complex multimodal tasks. However, our preliminary study reveals an ``inverted-U'' relationship between reasoning length and chart-editing performance: Excessive reasoning often leads to ``overthinking,'' where models drift toward hallucinated visual details or get stuck in redundant reasoning loops. To address the gap, we introduce REChart, a two-stage training framework that provides process-level supervision over intermediate reasoning steps, improving both editing fidelity and reasoning efficiency. First, we synthesize 200k high-quality reasoning trajectories for supervised fine-tuning from a large image-instruction-code pool, using a role-specialized agentic Reason-Score-Refine workflow that iteratively refine the chart code toward higher quality. Second, we optimize the model via reinforcement learning with two complementary rewards: a \emph{fidelity} reward evaluating code correctness, visual fidelity, and structural consistency, and an \emph{efficiency} reward that assigns each rollout a random thinking budget, truncates the reasoning process, and credits the final reasoning segment according to its contribution to the output. On the ChartEdit and ChartMIMIC benchmarks, our model achieves state-of-the-art chart-editing performance among open-source models of comparable scale, while mitigating overthinking and reducing average reasoning token usage by 79.0\% under a maximum thinking budget of 16,384 tokens compared with the base model.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · primary corpus · published 2026-08-19T06:19:20Z
Kou Shi, Zun Wang, Qisheng Su, Shiting Huang, Ziao Zhang, Zhen Fang, Qingnan Ren, Jin Liu, Yu Zeng, Yiming Zhao, Lin Chen, Zehui Chen, Feng Zhao
arXiv categories: cs.AI, cs.PL

Training terminal agents requires scalable executable supervision, yet synthesizing high-quality terminal tasks remains challenging. Each task couples an instruction, an initialized environment, a reference solution, and an executable verifier; if these artifacts are generated from inconsistent assumptions, the resulting task may be unsolvable or incorrectly evaluated. Meanwhile, multi-stage synthesis can discard the goals, dependencies, state transitions, and procedural constraints encoded in the original sources. We present FACET (Fine-grained Agentic Construction of Executable Tasks), a framework that addresses both information preservation and cross-artifact consistency. FACET reconstructs related agent skills into coherent, information-rich scenarios, then realizes and repairs the execution environment before generating the final task artifacts. The resulting container state serves as shared grounding for the instruction, solution, and verifier, while execution-based validation and targeted repair correct artifact-specific failures without unnecessarily regenerating valid components. FACET produces complex terminal tasks with dense executable checks, and successful trajectories collected from these tasks provide effective, data-efficient supervision. Fine-tuning models across multiple scales consistently improves performance on Terminal-Bench 2.1, while analyses of alternative generation schemes support the importance of environment-grounded construction for task validity and solution-verifier alignment. These results establish source-intent preservation and shared executable-state grounding as key principles for scalable terminal-task synthesis.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · primary corpus · published 2026-08-19T22:17:31Z
Oleg Grynets, Dmytro Kostetskyi, Vasyl Lyashkevych
arXiv categories: cs.SE, cs.AI, cs.CL, cs.LO

This work introduces a formal semantic-block model for specifications and an execution-judged benchmark for evaluating specification quality independently of model capability. A specification is represented as a structure comprising semantic blocks, dependency relations, block-owned rules, decision points, and explicitly open questions, subject to four machine-checkable well-formedness conditions: acyclicity, single ownership, constraint domination, and totality or ambiguity-stop. Determinacy is defined model-theoretically as agreement among all conforming implementations and is estimated empirically through convergence across independent implementers. The model is instantiated on an Oracle-to-PostgreSQL migration specification containing 18 blocks and 19 dependency edges. Computational validation shows that the five-layer decomposition reduces mean per-task context by approximately 71% through dependency closures, covers 85.5% of the study-defined Oracle construct taxonomy with all identified gaps triaged, is not Pareto-dominated by the tested alternative partitions, and is recovered at the 99.9th percentile from citation-derived edges not used to define the original structure. The benchmark keeps the implementer panel fixed, includes a mandatory no-specification control arm, and uses PostgreSQL 16 and a live Oracle instance as deterministic execution judges. Six designed studies, including three pre-registered manipulations and three diagnostic analyses, further examine specification effects. Repeated runs on a 25-unit subsample reveal an empirical variability floor with a median arm-delta spread of 14.4 percentage points. The results support determinacy as a formal concept but not as a standalone empirical quality metric for the evaluated contemporary LLM implementers.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · primary corpus · published 2026-08-20T09:38:48Z
Pablo Ramirez Amador
arXiv categories: cs.AI, cs.PL

Spec Driven Development SDD has consolidated the idea that the specification rather than the code should be the primary artefact governing AI assisted work. Tools such as GitHub Spec Kit, and proposals such as Constitutional SDD, have formalised this principle in the software domain, while the executable data-contracts literature has extended it to schema and quality enforcement at run time. Nevertheless, the treatment of the specification delta OpenSpec's core idea that every change should produce a reviewable increment of requirements as the unit of change in data platforms remains empirically unexplored, even though many data-platform changes are contractual (new datasets, service-level agreements, metric semantics, access policies) rather than purely code changes. This work formalises the spec-delta concept, proposes a taxonomy of data platform changes according to their suitability for incremental specification, and defines a controlled experiment comparing a spec-delta-driven workflow against a conventional code pull-request workflow without a delta. The response variables are discovery to deployment time, the density of defects reaching the Silver and Gold lakehouse layers, cross-tool metric divergence, and reviewer cognitive load measured with NASA TLX. The paper explicitly reserves a demonstration-and-laboratory section for instantiation on a real lakehouse environment. The contribution is not a tool but reproducible evidence and an applicability guide that helps to avoid the up front over specification antipattern.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · primary corpus · published 2026-08-21T02:49:34Z
Piyush Jha, Jake Rudolph, Victoria Knapp-Pérez, Max Fieg, Aishik Ghosh, Vijay Ganesh
arXiv categories: cs.AI, cs.LG, cs.LO, hep-ph

Many scientific discovery problems require searching combinatorial hypothesis spaces under complex domain constraints. Reinforcement learning (RL) offers a promising approach, but existing methods rely on scalar rewards that provide limited information about why candidate solutions fail, leading agents to repeatedly explore invalid regions. We introduce Certification-Driven Reinforcement Learning (CDRL), a framework that leverages structured feedback from symbolic reasoning tools. When a candidate violates domain constraints, these tools produce certificates identifying the actions responsible for failure. CDRL converts these certificates into reusable constraints that eliminate classes of invalid solutions and guide exploration toward valid regions. We evaluate CDRL on neutrino flavor model discovery in theoretical particle physics, where the hypothesis space exceeds $10^{26}$ possible models, and compare it with the state-of-the-art RL approach previously used for this task. Across three theory spaces, CDRL achieves up to 1.95$\times$ higher valid model rates and up to 6.33$\times$ higher neutrino model rates while evaluating up to 4$\times$ fewer candidates. We further extract 40 interpretable rules from search trajectories using a post-hoc decision-tree framework and show that reusing them as soft constraints yields gains of up to 2$\times$ in valid model rates and 3$\times$ in neutrino model discovery across all three theory spaces. These results suggest that CDRL uncovers reusable structure in combinatorial search spaces and provides a general framework for scientific model discovery.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · primary corpus · published 2026-08-21T15:21:40Z
Oleg Grynets, Oleksii Ilchuk, Dariia Zatulna, Vasyl Lyashkevych
arXiv categories: cs.SE, cs.AI, cs.LO

This paper investigates cross-agent specification portability using Oracle-to-PostgreSQL migration as a controlled software transformation task. The study combines two experimental stages. First, a specification-first migration pipeline was evaluated on 1,006 PL/SQL files, of which 623 were successfully regenerated and 380 generated scripts executed successfully in PostgreSQL 16. Second, cross-agent experiments were conducted on a dataset of 1,802 Oracle scripts with corresponding PostgreSQL implementations using Amazon Kiro, Google Gemini, and GitHub Copilot, with Claude Code and Cursor included in the initial single-agent evaluation. Native and foreign specifications were assessed using Token F1, exact match, SQL syntax validity, AST exact match, AST mean similarity, and immediate runnability. The results show that specification size alone does not predict implementation quality and that cross-agent transfer can produce substantial agent-dependent degradation. The strongest replicated case occurred when Gemini directly consumed a Kiro-origin specification, producing a Token F1 of 0.035, SQL syntax validity of 2.33%, and AST mean similarity of 0.015. Rewriting substantially improved Gemini in the tested configuration, compression did not provide a universal benefit, and retrieval-augmented ingestion was the only common strategy represented on the per-agent Pareto frontiers of both Gemini and Copilot. The findings suggest that specifications in heterogeneous SDD workflows should not automatically be treated as agent-neutral artifacts and motivate explicit consideration of specification portability, agent-specific interpretation, and retrieval-based access in multi-agent software engineering.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · primary corpus · published 2026-08-21T17:59:16Z
Jason Hickey
arXiv categories: cs.SE, cs.AI, cs.AR, cs.LO

For sixty years, machine verification has been a major cost overhead, affordable only for exceptional artifacts. Here we report that generative AI inverts this relationship: at AI speed, machine verification is not only economical but essential to productivity --- it is the incorruptible referee that lets one person safely direct autonomous machine work at scale. In five weeks, one researcher on consumer AI subscriptions directed a small fleet of AI agents from application code, through a verified compiler and executive, to a RISC-V processor taped out on a community silicon shuttle; no proof passed through human review, and no RTL was written by a human. The working discipline --- the Salt method --- rests on a proof kernel no hallucinated proof can pass: mathematical claims travel between agents as kernel-checked artifacts, and human attention is reserved for statements, designs, and rulings. Verification is stated link by link, from the Lean 4 kernel to SAT-checked equivalence at the silicon boundary. We publish the complete accounting: theorem provenance, a pre-registered token meter, floor-bounded human time, and an error ledger whose catch numbering runs to #256 --- a monotone counter over the mathematics campaign's append-only flags ledger, maintained 2026-07-07 to 2026-07-20 (one number, #79, was never assigned; later catches are recorded un-numbered) --- against zero incorrect proofs reaching the record.

arXiv abstract · PDF

Automated reasoning, constraints, and proof search · primary corpus · published 2026-08-19T04:03:04Z
Pham Quang Minh, Dao Xuan Nghia, To Van Khanh
arXiv categories: cs.LO, cs.DM, math.CO

The two-dimensional bandwidth minimization problem (2DBMP) seeks an injective embedding of a guest graph into a square grid that minimizes the maximum Manhattan distance over its edges. Heuristic methods can provide strong upper bounds, but these bounds do not by themselves certify optimality. We present an efficient exact SAT-based approach for 2DBMP that incrementally searches for the minimum feasible bandwidth and certifies optimality through satisfiability and unsatisfiability results. On the standard $\lceil\sqrt n\rceil \times \lceil\sqrt n\rceil$ host grid, under a 3600 s time limit, the proposed SAT approach certifies optimal bandwidths for 41 of 43 Regular instances and 42 of 93 Harwell--Boeing instances, achieving substantially broader optimality certification within the 3600 s time limit than a previous exact approach evaluated with a 72-hour time limit. In addition, it certifies three bandwidth values that improve all previously published comparison values considered in this study and establishes all three as optimal. We further evaluate the approach on alternative host geometries, namely $2\times\lceil n/2\rceil$ and $n\times n$ grids, to assess its effectiveness beyond the standard host. Overall, the results demonstrate that the proposed SAT approach provides an effective exact method for the small- and medium-sized benchmark instances considered in this study, with fewer than 400 vertices, while heuristic methods remain important for larger and more challenging instances.

arXiv abstract · PDF

Automated reasoning, constraints, and proof search · primary corpus · published 2026-08-20T06:19:57Z
Teppei Saito, Nao Hirokawa
arXiv categories: cs.LO

We present a simple criterion for combining reduction pairs lexicographically. The criterion is applicable to arbitrary classes of reduction pairs, such as the polynomial interpretation, the matrix interpretation, and the Knuth-Bendix order. In addition, we investigate a variant of the matrix interpretation where the lexicographic order is employed instead of the usual component-wise order. Effectiveness is demonstrated by experiments and examples, including Touzet's Hydra Battle.

arXiv abstract · PDF

Temporal, probabilistic, and quantitative reasoning · primary corpus · published 2026-08-17T04:33:06Z
Katherine Wu, Jules Jacobs, Kevin Batz, Alexandra Silva
arXiv categories: cs.PL

We study exact discretization as a semantics-preserving transformation for recursive, higher-order probabilistic programs with continuous distributions. We target programs where continuous values are compared against finitely many constants, so exact inference reduces to a discrete problem. Our central technical contribution is a non-local, type-directed analysis that infers where continuous values can be partitioned into finitely many observationally relevant regions, then rewrites sampling and comparison behavior over those regions. We call this transformation Slice. Because this construction is global and type-directed, correctness requires reasoning beyond the local syntax: we formalize the transformation and prove soundness for boolean queries using a coupling-style logical relations argument over operational semantics. As an application, transformed programs can be executed by discrete engines such as Dice, Roulette, and Storm. Our empirical evaluation shows two complementary strengths of Slice when paired with discrete backends: it enables exact inference for challenging continuous programs that lie beyond the reach of previous exact systems, and, on benchmarks where direct comparison is possible, it is competitive with state-of-the-art exact inference systems for continuous programs.

arXiv abstract · PDF

Temporal, probabilistic, and quantitative reasoning · primary corpus · published 2026-08-17T12:39:12Z
Daniel Hausmann, Marcin Jurdzinski, Nir Piterman
arXiv categories: cs.GT, cs.LO

Nearly a decade ago, Calude et al. showed that parity games can be solved in quasi-polynomial time. This result is now understood in terms of universal trees. By reduction to parity games, the quasi-polymonial result can benefit all omega-regular games. However, beyond such reductions, and with the exception of Rabin games, our understanding of the role of universal trees in direct solutions is still quite limited. In this work, we refute the common view that universal trees are relevant only for games that admit memoryless winning strategies. We contribute a full understanding of how universal trees interact with Zielonka trees for the solution of Streett and Emerson-Lei games. As a consequence, we show that winning regions and strategies in Streett games with $n$ vertices, $m$ edges, and $k$ pairs can be computed in time $O(mk\log(k)k!|U(n,k)|)$, where $U(n,k)$ is a universal tree for $n$ leaves and depth $k$. This improves upon the best previously known complexity result for Streett games, which relied on reduction to parity games and their quasi-polynomial solution. Furthermore, we show that winning regions and strategies for Emerson-Lei games with $n$ vertices, $m$ edges, and $c$ colors can be computed in time $O(mc\log(c)c!|U(n,c/2)|)$, again improving over reductions to parity games. Notably, our approach yields memory-optimal strategies, in contrast to those obtained via reductions to parity games. Finally, we show how universal trees can be used to bound the recursion tree of the Zielonka-McNaughton algorithm for Emerson-Lei games. This leads to a symbolic algorithm that replaces the factor $n^c$ in the time complexity of existing symbolic approaches with $|U(n,c)|$.

arXiv abstract · PDF

Temporal, probabilistic, and quantitative reasoning · primary corpus · published 2026-08-17T19:46:38Z
Konstantinos Kogkalidis
arXiv categories: cs.LG, cs.LO, cs.PL, eess.SY

Linear temporal logic is a modal extension of propositional logic that allows one to state how a system should behave over time. Its canonical domain is the booleans, but discretely-valued judgements are of little use in steering softly-valued systems (neural policies, adaptive controllers, sequence models, etc). In such cases, the goal formula's (dis)satisfaction becomes a training signal, and differentiability becomes a prime concern. Candidate differentiable semantics abound, but navigating them is tricky. Implementations, where available, are shallow embeddings, demanding an upfront commitment to a single semantic algebra and its (usually implicit) conduct. The paper casts the reader as a functional programmer asked to come to terms with this predicament, and refusing. Out of that refusal comes an evaluation engine that is algebra-generic and amenable to differentiation, together with an executable specification of the algebras it can accept. Various algebras are implemented and audited for their behavior, both forward and backward. Each algebra turns out to be a choice of which direction to disappoint, and how. Everything described (and more) is part of the PyTorch library telos, to be found at https://github.com/konstantinosKokos/telos.

arXiv abstract · PDF

Temporal, probabilistic, and quantitative reasoning · primary corpus · published 2026-08-18T09:59:50Z
Davide Ancona, Angelo Ferrando, Viviana Mascardi
arXiv categories: cs.FL, cs.LO

Runtime Verification (RV) techniques are typically defined under the assumption of complete observability of system executions. In many realistic settings, however, monitors must operate under partial observability, where events may be lost, delayed, or unobservable. This raises fundamental questions about how to interpret specifications, verdicts, and uncertainty during monitoring. In this paper, we propose a new syntax and semantics for Probabilistic Trace Expressions (PTEs), a formal framework that integrates probabilistic reasoning into the operational semantics of Trace Expressions. Trace Expressions (TE) are a highly expressive specification formalism for runtime verification that we started to develop 15 years ago. Rather than attaching probabilities to syntactic transitions, as we did in the original formulation of PTEs dating back 2022, probabilities are now associated with the set of event types enabled in each semantic state, ensuring semantic consistency beyond finite-state models, and high modularity of the PTE specification. The PTE framework supports principled reasoning about missing events (gaps), distinguishes between observational and generative probabilistic interpretations -- which represents a more refined semantics w.r.t. the original PTE formulation of 2022 -- and subsumes classical probabilistic models such as Hidden Markov Models. We discuss how PTEs enable belief-based monitoring under uncertainty, illustrate their use in one representative Mars Rover scenario, and reflect on the conceptual implications for runtime verification in partially observable environments.

arXiv abstract · PDF

Temporal, probabilistic, and quantitative reasoning · primary corpus · published 2026-08-18T15:50:01Z
Kasper Engelen, Sebastian Junges, Guillermo A. Pérez, Marnix Suilen
arXiv categories: cs.AI, cs.LO

Robust Markov decision processes optimize one policy against a set of plausible transition functions. This can be conservative when the unknown dynamics are fixed and become partially identifiable after deployment. We study adaptive policy portfolios: finite sets of memoryless randomized policies synthesized offline and paired with a lightweight online selector. Robust regret is a natural measure of portfolio quality: for each plausible environment, it measures the loss of the best portfolio member relative to the policy that would have been optimal had that environment been known. Related regret objectives were studied by Ghavamzadeh et al. (2016) with an emphasis on approximations and relaxations for safe policy improvement. We give a complexity-theoretic account of portfolio certification and synthesis. Certifying a given portfolio is $\forall\mathbb{R}$-complete already for deterministic portfolios in acyclic (s,a)-rectangular RMDPs. Synthesizing a portfolio of unary-bounded size is $\exists\forall\mathbb{R}$-complete for general rational polytopes, even with fixed discount and acyclic dynamics. The single-policy case is already hard, both combinatorially and algebraically. Finally, we present an offline portfolio construction that is amenable to runtime specialization.

arXiv abstract · PDF

Temporal, probabilistic, and quantitative reasoning · primary corpus · published 2026-08-20T09:37:44Z
Astrid Horn Brorholt, Maris F. L. Galesloot, Nils Jansen, Kim Guldstrand Larsen, Christian Schilling
arXiv categories: cs.LG, cs.AI, cs.LO

Probabilistic shielding is a technique for safe reinforcement learning (RL). Typically, a static observer -- called the shield -- constrains the learning agent's actions to those for which acting safely remains feasible. Traditionally, the shield is computed from the transition probabilities of the underlying Markov decision process (MDP). Thus, this technique is not applicable when the MDP model is not given a priori, which, unfortunately, is the case in typical RL applications. In this paper, we study the problem of computing a shield in the setting where the transition graph of the MDP is known, but the transition probabilities are unknown. Our approach integrates probabilistic shielding with online model learning: as the RL agent explores the environment, we estimate the transition probabilities. From this estimate, we compute a shield. While the shield may be conservative initially, it adapts as the model estimate becomes more precise. Thus, the shield improves in tandem with the RL agent. This paradigm of adaptive probabilistic shielding raises a number of challenges, such as when to recompute the shield and how to balance between exploration and safety during learning. We empirically evaluate multiple variants of this paradigm across several environments.

arXiv abstract · PDF

Temporal, probabilistic, and quantitative reasoning · primary corpus · published 2026-08-20T20:35:07Z
Celina Shiyu Wang, Yiqi Zhao, Junjie Ye, Yue Wang, Jyotirmoy V. Deshmukh
arXiv categories: cs.RO, cs.LO, eess.SY

Vision-language-action (VLA) models can follow natural-language (NL) task instructions, but such instructions may not precisely specify safety-critical or spatiotemporal requirements on the resulting behavior. We introduce Logic-VLA, a formal-requirement-aware VLA that conditions on Signal Temporal Logic (STL) specifications supplied at inference time. Logic-VLA uses a syntax-graph-based STL encoder pre-trained to capture temporal logic semantics. Policy adaptation proceeds in two stages: STL-conditioned supervised fine-tuning on satisfying demonstrations is followed by trajectory-level preference optimization over matched satisfying-violating rollout pairs using a flow-matching surrogate for Identity Preference Optimization. This formulation improves formal requirement satisfaction while preserving the nominal NL task. We evaluate Logic-VLA in closed-loop quadcopter navigation simulation across randomized photorealistic environments and test generalization to STL formulas unseen during training. Across the evaluation benchmarks, Logic-VLA improves STL satisfaction rate over an STL-blind base policy by 24.8 to 40.7 percentage points (pp) while reducing nominal NL task success by at most 1.8 pp, showing that a single VLA can adapt its behavior to varying formal requirements without requiring a separate policy for each specification.

arXiv abstract · PDF

Temporal, probabilistic, and quantitative reasoning · primary corpus · published 2026-08-21T06:53:18Z
Dogan Ulus
arXiv categories: cs.LO

Runtime assurance for autonomous systems increasingly requires reasoning not only about observed executions but also about anticipated future behaviors. Traditional runtime verification, however, primarily evaluates the execution observed so far and does not directly account for predicted continuations. We propose a formal framework for runtime assurance that combines monitoring of the observed execution with analysis of multiple predicted continuations. To support this integration, we introduce Split Linear Temporal Logic (SplitLTL), a linear-time temporal logic that assigns complementary roles to past and future temporal specifications within a single specification. The past component uses the observed history to determine the assurance requirements applicable at the current point of execution, while the future component evaluates predicted continuations against those requirements. The framework therefore filters predicted continuations according to the requirements induced by the observed history, identifying admissible continuations that can support subsequent decision making. We formally define the syntax and semantics of SplitLTL and present an online monitoring architecture for evaluating observed executions together with predicted continuations.

arXiv abstract · PDF

Modal, intuitionistic, and proof-theoretic logic · primary corpus · published 2026-08-17T17:57:59Z
Philip Sink
arXiv categories: cs.LO, math.LO

This paper captures and extends some of the core results from the tech memo "A New Semantics for Belief Revision in Simplicial Complexes". As such, we set out to explore the implementation of action models in the setting of simplicial semantics for modal logic. Such an idea is not entirely new to the literature, showing up in both "A simplicial complex model for dynamic epistemic logic to study distributed task computability" and "Knowledge and Simplicial Complexes". However, we will explore action models in a more general setting. In particular, we will allow for action models for simplicial models for belief, as in "A Semantics for Belief in Simplicial Complexes". This will let us incorporate the notion of belief revision, as developed in "Simplicial Semantics for Belief Revision", into these action models. Moreover, we explicitly connect action models in the simplicial setting to distributed protocols as defined in the textbook "Distributed Computing Through Combinatorial Topology". We conclude with some speculation on how we might interpret distributed protocols with revision.

arXiv abstract · PDF

Modal, intuitionistic, and proof-theoretic logic · primary corpus · published 2026-08-17T20:35:12Z
Guram Bezhanishvili, Sebastian D. Melzer
arXiv categories: math.LO

Let $L$ be the frame of opens of a $T_0$-space $X$. We prove that if $X$ is sober and $T_1$, then the double negation nucleus on $L$ is Scott continuous iff $X$ is discrete. It follows that if, in addition, $X$ is compact then double negation is Scott continuous iff $X$ is finite. We show that both the sober and $T_1$ assumptions are essential, and generalize the above results to all boolean nuclei on $L$. A pointfree characterization of when $X$ is sober and $T_1$ is also given by proving that it is equivalent to Scott continuous nuclei on $L$ being closed.

arXiv abstract · PDF

Modal, intuitionistic, and proof-theoretic logic · primary corpus · published 2026-08-19T14:14:07Z
Aliel Minatti Andrade, Rogério Augusto dos Santos Fajardo
arXiv categories: math.LO, math.GN

On this article we provide a relation between two inherently different semantic structures for intuitionistic modal logic. We start by recalling the Heyting Algebras, then defining the language and the axioms for the iS4h intuitionistic calculus. We then proceed to analyse two structures discussed on [4] and their relation. Finally, we discuss about a structure defined on [3, Chapter 6], establishing properties in order for it to be sound with iS4h, and finally conclude that it is semantically equivalent to the other two structures defined by [4].

arXiv abstract · PDF

Modal, intuitionistic, and proof-theoretic logic · primary corpus · published 2026-08-20T16:23:27Z
Verónica Borja Macias, Marcelo E. Coniglio, Alejandro Hernández-Tello
arXiv categories: cs.LO

In this paper, we introduce the study of probability functions based on the 6-valued paradefinite (i.e., paraconsistent and paracomplete) logic LETK+. This logic is a powerful and versatile Logic of Evidence and Truth (LET) which is a conservative expansion of both classical logic and FDE. The framework introduced here allowed us to consider gaps, gluts, and reliability (or classicality) of the events, extending the detailed proposal for FDE-based probabilities presented by Klein, Majer, and Rafiee Rad. A distinctive feature of our proposal is the use of twist structure semantics, which gives rise to a natural interpretation of logical probabilities over LETK+ in terms of the three or six regions associated with each formula by a valuation in such models. The LETK+-probability functions are defined axiomatically and semantically, obtaining soundness and completeness results, as one would expect. Finally, conditional probabilities based on LETK+ are also studied. Specifically, both a semantic and a syntactic characterization of Jeffrey's update over LETK+-based probabilities is proposed, showing their equivalence.

arXiv abstract · PDF

Modal, intuitionistic, and proof-theoretic logic · primary corpus · published 2026-08-21T14:21:26Z
Simone Cuconato
arXiv categories: math.LO

Sequent-style tableaux are a refutation calculus in which each node of the refutation tree carries a finite block of formulae and the structural rules are absorbed into the data structure and the closure criterion. In their original, classical form they rest on an involutive De Morgan negation and on closure upon a complementary pair. We show that both may be dispensed with. Replacing unsigned formulae by signed ones, we obtain a block calculus $\mathbf{B}_{ti}$ for intuitionistic propositional logic in which the whole of intuitionism is carried by one rule, the rule decomposing $\mathsf{F}(A \to B)$, which deletes the $\mathsf{F}$-part of the context on passing to the child block. The rules so obtained are, up to the presentation, those of Fitting's signed tableaux; what is new is the block format, in which the structural rules are absorbed rather than admissible, and what follows from it. We identify the semantic reason for this rule and for the one other anomalous one: of the signed compounds of the language, exactly those governed by the implication fail to be locally decomposable, and the two failures are repaired, respectively, by retaining the principal formula and by purging the context. We prove that $\mathbf{B}_{ti}$ is the multiple-succedent sequent calculus $\mathbf{G}_{ti}$ read upside down, that $\mathbf{G}_{ti}$ admits the structural rules, and that $\mathbf{B}_{ti}$ is sound and complete for Kripke semantics, with the finite model property and a block-theoretic proof of the disjunction property.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-17T04:44:57Z
Yi Zhang
arXiv categories: math.LO

Shelah and Usvyatsov proposed the Generalized Gaifman Conjecture [SU25, Conjecture 1.1]. We give a negative answer.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-17T10:56:13Z
Martina Iannella, Vadim Weinstein
arXiv categories: math.LO, math.GT

We generalize the Stone space of ultrafilters on Boolean algebras and prove a generalization of Stone duality which is applicable to locally compact Polish spaces. Using this, we obtain complete invariants for simplicial complexes up to PL-homeomorphism and for non-compact $2$- and $3$-manifolds up to homeomorphism. We prove that the homeomorphism relation on non-compact $2$-manifolds without boundary, the homeomorphism relation on non-compact $3$-manifolds with or without boundary, the homeomorphism relation on open subsets of $\mathbb{R}^2$ and $\mathbb{R}^3$, and conjugacy of Cantor sets in $\mathbb{R}^3$ are classifiable by countable structures. Together with known lower bounds, this implies that these relations are Borel bireducible with isomorphism of countable graphs. We also show that PL-homeomorphism of Heine-Borel simplicial complexes and PL-homeomorphism of PL $n$-manifolds, for every $n$, are classifiable by countable structures.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-17T13:35:48Z
Nicolas Fröhlich, Matilda Häggblom, Åsa Hirvonen, Minna Hirvonen
arXiv categories: cs.LO, cs.DB

Functional dependencies are an important and well-studied class of database constraints that correspond to a notion expressed by dependence atoms in team logic. In practice, data often contain errors, so in some cases it might be useful to allow the database to have a small number of tuples that violate the desired dependency. Väänänen (2017) studied the axiomatisation of a notion of approximate dependence that specifies for each dependence atom how much of the database can be disregarded. We demonstrate that the interaction of approximate dependence atoms is more complicated than previously thought in the sense that there is a semantic consequence that is not captured by the inference rules introduced before. We show that Väänänen's axiomatisation is still complete in the restricted case of unary dependencies. We also consider the complexity of model checking for approximate dependence: it is NP-complete for disjunctions of two atoms and LOGSPACE-hard for individual atoms.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-17T15:12:16Z
Rishi Banerjee
arXiv categories: math.LO

Let $θ$ be a regular cardinal, $R$ a ring, and $M$ a left $R$-module. We prove that for every ordinal $α$ there is a set $I_α\subseteq M^{<θ}$ of size at most $\beth_α(|R|^{<θ})$ such that every parameter-free $L_{\infty,θ}$ formula of rank at most $α$ is equivalent in $M$ to an infinitary Boolean combination of cosets $\overline{a} + φ(M)$, where $\overline{a} \in I_α$ and $φ$ is an infinitary positive existential formula of rank at most $α$. The main ingredient in the proof is a combinatorial lemma which says that given $κ$ subgroups of an abelian group, there is a set of at most $2^κ$ points which tests whether any family in which each member is either empty or a coset of the corresponding subgroup covers the whole group. The proof proceeds by applying this lemma fiberwise to show that the relevant complete Boolean algebras of positive-existentially definable cosets are closed under projections.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-17T16:17:13Z
Michael Lange
arXiv categories: math.LO

We extend a construction of Marker and Steinhorn for producing countable non-archimedean real closed fields which have no non-trivial automorphisms. The original construction produces such a field of transcendence degree two over the field of real algebraic numbers. We show how to use the same method to produce examples of all finite transcendence degrees and of countably infinite transcendence degree over the real algebraic numbers, answering a question of Marker and Steinhorn.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-18T13:29:17Z
Vishwesh Tiwari
arXiv categories: math.LO

Constraint Satisfaction Problems (CSPs) provide a framework for expressing complex algorithmic decision problems. For finite-domain CSPs, the polymorphism clone provides a fundamental algebraic invariant governing the associated constraint language. A fundamental structural question in universal algebra is how to determine whether a given clone is finitely related. In this paper, we prove that a clone $\mathcal{C}$ on a finite domain $C$ is finitely related if and only if its action algebra $\widetilde{\mathcal{C}} = \mathcal{C} \curvearrowright \mathcal{C}^{(n)}$ on its $n$-ary part (for $n \ge |C|$) is finitely related. We then apply natural clone isomorphisms to demonstrate that a finite algebra is finitely related if and only if its free algebra of sufficient rank is finitely related.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-18T14:53:37Z
Haitao Ji, Fengshuo Xu, Dong Qiu
arXiv categories: math.LO

We answer Kourovka Notebook Problem~18.16 affirmatively in the pure language of ordered abelian groups, with parameters allowed. The piecewise-affine description of definable functions reduces the question to an algebraic rigidity theorem: an additive endomorphism of a torsion-free abelian group that is covered by finitely many rational-affine laws has one global rational slope. The parameter-free pure-language case is included, whereas the unrestricted expansion-language variant admits a simple counterexample.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-19T02:11:03Z
Forte Shinko, Felix Weilacher, Jing Yu
arXiv categories: math.LO, math.CO, math.DS, math.MG

A theorem of Dougherty--Jackson--Kechris states that any equivalence relation generated by a single Borel function is hypersmooth. A well-known open problem is whether this can be generalized to equivalence relations generated by countable families of pairwise commuting Borel functions. We give an affirmative answer in the case where the functions are bounded-to-one. This generalizes the theorem of Gao--Jackson on Borel actions of countable abelian groups.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-19T03:24:42Z
Jintao Luo
arXiv categories: math.LO, math.DS

We give a finite symbolic reformulation of the strong topological Rokhlin property in terms of globally realizable tuples. We prove that the strong topological Rokhlin property passes from a finite-index subgroup to a finitely generated overgroup. We also study the descriptive complexity of the class of countable groups having the strong topological Rokhlin property. In the standard compact space of countable groups, this class belongs to $\mathbfΠ^0_4$ and is $\mathbfΣ^0_2$-hard. We also isolate a barrier to Borel rank four: if the class is not $\mathbfΣ^0_3$, then there is a non-finitely-presented group with the strong topological Rokhlin property.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-19T07:57:59Z
Dragos Ghioca, David Marker, Charles Steinhorn
arXiv categories: math.LO, math.NT

Let $K$ be an algebraically closed field of characteristic 0 and transcendence degree at least 2. Let $C\subset K^2$ be an irreducible curve defined over $K$ but not defined over the algebraic closure of $\mathbb Q$. There is $(x ,y)$ a $K$-point of $C$ such that $x$ and $y$ are algebraically independent. Moreover, if $C_0$ and $C_1$ are two such curves and there is a finite-to-finite algebraic correspondence between them defined over $K$, then there are corresponding $K$-points $(x_0,y_0)\in C_0$ and $(x_1,y_1)\in C_1$ such that $x_0$ and $y_0$ are algebraically independent and $x_1$ and $y_1$ are algebraically independent. We use the latter result to construct non-Archimedean real closed fields of transcendence degree $κ$ with no non-trivial automorphisms for all $2\leκ\le \aleph_1$.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-19T14:33:50Z
Antonio Carbone
arXiv categories: math.AG, math.LO

Recently, we showed that continuous definable maps defined on compact definable sets can be uniformly approximated by continuous definable maps of class $\mathcal{C}^p$ without changing their image. The aim of this paper is to extend the previous result, this time taking into account the (strong) Whitney topology, to continuous locally definable maps defined on locally compact locally definable sets. The argument is an interplay between o-minimal and PL geometry and makes essential use of Pawłucki's desingularization techniques as well as our aforementioned result for the compact case.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-20T01:28:54Z
Tapani Hyttinen, Marcos Mazari-Armida, Gianluca Paolini
arXiv categories: math.LO, math.RA

Let $R$ be a ring. We organize the abstract elementary classes whose underlying class is the class of all $R$-modules and whose strong submodel relation lies between the submodule and direct summand relations into a lattice $\mathscr{L}_{R}$, ordered by reverse inclusion. We establish the basic lattice-theoretic properties of $\mathscr{L}_{R}$ and investigate its two natural sublattices, below and above purity. Below purity, we isolate relations defined by first-order pp-formulas for which amalgamation, tameness, and stability hold. Above purity, we introduce relations defined by infinitary pp-formulas and prove a broad stability result. Specializing to abelian groups, we show that the lattice $\mathscr{L}_{\mathbb{Z}}$ has the following properties: it has a strong submodel relation that is not positive syntactic, it contains an uncountable antichain and a strictly increasing proper-class-sized chain, and it has a broad region above purity where amalgamation fails.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-20T15:28:11Z
Tatsuya Gima
arXiv categories: cs.DS, cs.CC, cs.LO

We introduce $\mathsf{AmCMSO}$, an extension of counting monadic second-order logic ($\mathsf{CMSO}$) with predicates that refer to minimum- and maximum-value satisfying assignments. We establish fixed-parameter tractable model-checking meta-theorems for $\mathsf{AmCMSO}_1$ on graphs of bounded clique-width and for $\mathsf{AmCMSO}_2$ on graphs of bounded treewidth. These meta-theorems yield fixed-parameter tractable algorithms for several bilevel graph optimization problems, including interdiction and preassignment problems for solution uniquification, as well as algorithms for maximizing the diversity of optimal solutions without parameterizing by the optimum value. In contrast, allowing an optimality predicate to depend on an external set variable makes model checking hard for every level of the polynomial hierarchy, even on trees of fixed depth.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-21T10:21:20Z
Guangyin Ma, Shichang Song
arXiv categories: math.LO, math.CO

We show that the isomorphism relation for countable Steiner triple systems is Borel complete, that is, the isomorphism relation for arbitrary countable structures is Borel reducible to that for countable Steiner triple systems. To prove it, we construct a faithful Borel reduction from countable graphs to countable Steiner triple systems, that is, a Borel assignment $θ$ that associates every countable graph $G$ with a countable Steiner triple system $θ(G)$ so that $G\cong G'$ if and only if $θ(G)\congθ(G')$. Moreover, $θ$ preserves automorphisms which means that $\mathrm{Aut}(G)\cong\mathrm{Aut}(θ(G))$.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-21T13:25:10Z
Yuval Filmus, Johann A. Makowsky
arXiv categories: cs.LO

Courcelle's Theorem states that on graphs $G$ of tree-width at most $k$ with a given tree-decomposition of size $t(G)$, graph properties $\mathcal{P}$ definable in Monadic Second Order Logic can be checked in linear time in the size of $t(G)$. Inspired by L. Lovász' work using connection matrices instead of logic, we give a generalized version of Courcelle's theorem which replaces the definability hypothesis by a purely combinatorial hypothesis using a generalization of connection matrices. This paper clarifies the role of logic in such theorems and displays their purely combinatorial assumption.

arXiv abstract · PDF

Set theory, computability, and mathematical foundations · primary corpus · published 2026-08-17T15:08:28Z
Junhong Chen
arXiv categories: math.LO

We classify a broad family of weak first-order set theories, under ordinary parameter-free interpretability, by the first-order arithmetical theories with which they are mutually interpretable. This also determines their consistency strength. Set theories that correspond to the same arithmetical theory are often related by deductive extension. It is therefore enough to interpret a stronger set theory in the arithmetical theory and to recover the arithmetical theory in a weaker set theory; all intermediate cases then follow. The set theories under consideration fall roughly into three classes: theories with neither Power Set nor Infinity, theories with Power Set but without Infinity, and theories with Infinity but without Power Set. We conclude with a brief account of the higher levels that remain to be investigated.

arXiv abstract · PDF

Set theory, computability, and mathematical foundations · primary corpus · published 2026-08-18T09:07:31Z
Curial Gallart
arXiv categories: math.LO

Starting from a model of $\mathrm{ZFC}$, we force the simultaneous failure of the Very Weak Club Guessing and the $\mho$ principles at $S_κ^{κ^+}$, for any regular cardinal $κ$. Our results are obtained by means of a forcing iteration technique, due to Krueger, that incorporates models as side conditions. At $ω_1$, the failure of these principles is a well-known consequence of $\mathrm{PFA}$.

arXiv abstract · PDF

Set theory, computability, and mathematical foundations · primary corpus · published 2026-08-19T12:15:31Z
Christine Gaßner
arXiv categories: math.LO, cs.LO

Decisions and their consequences can be described and analyzed by means of decision trees. The decisions themselves depend on questions that, whenever possible, should be answered with yes or no. The original BSS machines over the real numbers are graphs with computation nodes and branching nodes for decisions. The evaluation of BSS machines and algebraic decision trees in computer-aided geometry which have been introduced for various types of numbers generally involves the evaluation of systems of literals of first-order logic. Flowchart-like representations and decision trees are also helpful for analyzing decisions made by BSS RAMs over first-order structures. All algorithms defined by machine-oriented programs of BSS RAMs can be illustrated using flowcharts, walks, and paths in program trees. The basic structures of these tools are graphs and their visual representations can help to characterize the behavior of individual BSS RAMs and other first-order machines. We offer a theoretical framework for linking various models. Here, we introduce program paths and transition systems for transforming partial configurations which are defined syntactically and can be extended and refined later. Finally, we define standard orders for program paths and present algorithms for enumerating finite program paths.

arXiv abstract · PDF

Set theory, computability, and mathematical foundations · primary corpus · published 2026-08-19T12:34:30Z
Graham Campbell
arXiv categories: cs.LO, cs.FL

Confluence guarantees that diverging rewrite choices can always be rejoined. For finite terminating string- and term-rewriting systems, confluence is decidable by critical-pair analysis, and in polynomial time for length-reducing strings. For finite terminating (hyper)graph transformation systems, in contrast, confluence is undecidable. We show that undecidability already appears for words on a circle, that is, strings up to rotation. Confluence of finite cycle-rewriting systems over the fixed alphabet $\{0,1\}$ is undecidable, indeed $Π^0_1$-complete, even when every rule has a nonempty right-hand side and strictly reduces length. Under this restriction termination is syntactically evident, and derivations from a nonempty length-$n$ cycle have fewer than $n$ steps. The same holds over every fixed alphabet with at least two letters, while the one-letter case is decidable. Rotation alone separates cyclic from string rewriting. The proof compiles a deterministic verifier into a weighted cycle system with one controlled branch, then into a binary length-reducing system via a run-length code whose cleanup rules send every reducible malformed cycle to one error normal form.

arXiv abstract · PDF

Set theory, computability, and mathematical foundations · primary corpus · published 2026-08-19T14:19:51Z
Yi Wang
arXiv categories: math.LO, math.CA

Erdős Problem 1154 asks whether every number in $[0,1]$ occurs as the Hausdorff dimension of a subring or subfield of $\mathbb{R}$. Motivated by this problem, Liang Yu asked whether the reals of an inner model can have Hausdorff dimension strictly between zero and one when their dimension is computed in an outer model. We prove a stronger result: if $\mathcal I \subseteq 2^ω$ is any Turing ideal, then $\dim_{\mathrm H} \mathcal I \in \{0,1\}$. Equivalently, the real-closed field whose reals have Turing degrees in $\mathcal I$ has Hausdorff dimension zero or one. The proof combines digit interleaving with the Furstenberg-set theorem of Orponen and Shmerkin.

arXiv abstract · PDF

Set theory, computability, and mathematical foundations · primary corpus · published 2026-08-19T14:30:56Z
Jonathan Schilhan
arXiv categories: math.LO

We introduce the universality property of a definable $σ$-ideal on a Polish space, which, on one hand, can serve as a benchmark for the properness of the associated idealized forcing of positive Borel sets ordered by inclusion, and, on the other hand, unifies many of the results that can be found in Zapletal's book. We show that under mild absoluteness assumptions, it implies properness, various dichotomy theorems, and closure under well-ordered unions in the Solovay model and under $\mathsf{AD}^+$, among other things. All major classes of proper idealized forcings studied in the book have this property. Further, we use this viewpoint to answer a question of Khomskii by showing that the naive idealized forcing for adding an eventually different real or a refining real is not proper below some condition. We also answer a question related to the definability of $σ$-ideals generated by Borel sets due to Kanovei, Sabok, and Zapletal.

arXiv abstract · PDF

Set theory, computability, and mathematical foundations · primary corpus · published 2026-08-21T02:02:00Z
Takuma Imamura
arXiv categories: cs.CR, math.LO

Mutual attestation among nodes with no central trusted operator requires each node to hold reference values (expected code measurements) for its peers. The naïve approach of mutually embedding these reference values in the nodes' code leads to an infinite regress. We call the problem of resolving this infinite regress the reference-value bootstrapping problem for mutual attestation. Existing solutions avoid this regress by relying on a trusted third party (TTP), externally supplied reference values, or architecture-specific measurement mechanisms. We instead express the bootstrapping problem as a system of mutual fixed-point equations and solve it by Kleene's second recursion theorem. The construction produces nodes that mutually reference one another's code and reconstruct every peer's exact source from built-in data alone. When a deployed source file is measured directly, as with a Python script, a node obtains the peer's reference value by applying the measurement function directly to the reconstructed source. When a built image is measured, as with AWS Nitro Enclaves, a node instead reproducibly rebuilds the peer's image from the reconstructed source and derives its reference measurement. For the first case, we develop PyReflect, a Python transpiler, and use it to implement a TPM mutual-attestation PoC. For the second, we develop NixReflect, a Nix transpiler, and use it in a PoC in which two Nitro Enclaves reproduce each other's reference PCRs from built-in data alone. Our solution is architecture-independent, requires neither a TTP nor externally supplied reference values, and works with existing attestation stacks unchanged.

arXiv abstract · PDF

Set theory, computability, and mathematical foundations · primary corpus · published 2026-08-21T09:01:43Z
Roman Feller, Peter Holy
arXiv categories: math.LO

We investigate compactness properties with respect to list colouring, a certain form of graph colouring, with infinitely many colours. We introduce a new hierarchy of compactness cardinals, that also includes some well-established large cardinal notions, and use it to show that various types of large cardinals, including weakly compact, strongly compact, and $δ$-strongly compact cardinals, can be characterized in terms of compactness for list colouring. We also obtain lower bounds on the size of our newly introduced compactness cardinals.

arXiv abstract · PDF

Higher categories, homotopy, and categorical topology · primary corpus · published 2026-08-18T01:37:57Z
Serban Matei Mihalache, Tomoro Mochida
arXiv categories: math-ph, math.AT, math.CO, math.CT

Polygon equations form a family of equations generalizing the pentagon equation. In this paper, we construct semi-simplicial sets of permitted colorings associated with set-theoretic solutions of polygon equations and use them to define the corresponding (co)homology groups. We investigate several properties of these groups and establish an equivalence of categories between set-theoretic solutions of polygon equations and higher Segal semi-simplicial sets satisfying certain conditions. As a special case, our result recovers the correspondence between bijective set-theoretic solutions of the pentagon equation and $2$-Segal semi-simplicial sets proved by Dyckerhoff--Kapranov.

arXiv abstract · PDF

Higher categories, homotopy, and categorical topology · primary corpus · published 2026-08-18T08:46:59Z
Georg Lehner
arXiv categories: math.AT, math.CT, math.GN, math.KT

We give a systematic account of the shape theory of $\infty$-topoi, viewing the shape of an $\infty$-topos as its generalized homotopy type. We establish the basic functorial properties of the shape, including preservation of colimits, descent, and homotopy invariance. We then prove that shape preserves cofiltered limits under compactness and perfectness hypotheses and establish Künneth-type formulas for products. Finally, we give conditions under which the shape of an $\infty$-topos determines its cohomology and homology.

arXiv abstract · PDF

Higher categories, homotopy, and categorical topology · primary corpus · published 2026-08-20T10:29:06Z
Kensuke Arakawa, Bastiaan Cnossen
arXiv categories: math.CT, math.AT

We give a short, conceptual account of Dwyer--Kan's hammock localization in the setting of $\infty$-categories. Starting from Mazel-Gee's formula for localization via the relative Rezk nerve, we show that its Segalification can be described explicitly as a Segal anima of zig-zags. We also compute its mapping animae and recover and generalize Dwyer--Kan's hammock formula. As an application, we show that, when a relative $\infty$-category supports fractions, the mapping animae of localization admit a simple description. This gives a unifying treatment for several formulas of this type in the existing literature.

arXiv abstract · PDF

Higher categories, homotopy, and categorical topology · primary corpus · published 2026-08-20T11:16:21Z
Shinobu Yokoyama
arXiv categories: math.AT, math.CO, math.CT

Let $\mathsf{P}$ be a finite graded poset and $Δ_a^{\mathsf{P}}$ the height-$a$ thickening of its diagonal. We study the \emph{window convolution} $C_a=q_{1\sharp}(k_{Δ_a^{\mathsf{P}}}\otimes^{\mathbf L}q_2^\ast(-))$ on $\mathrm{Shv}(\mathsf{P};k)$. An interleaving distance needs the left derived $\mathbb{L}C_a$ to compose as a flow, $\mathbb{L}C_a\mathbb{L}C_b\simeq\mathbb{L}C_{a+b}$; the total meet functor $Φ$ gives rise to the canonical comparison. Finality is sufficient, and necessary where the finality defect of $Φ$ is essential; where $Φ$ is total at a minimal apex with unit windows, it is the failure of a length-two interval to have a single interior element. The flow fails at every branching length-two interval, and with it on the face poset of every finite regular cell complex of dimension $\ge2$. It survives on tame posets, where $\mathrm{id}\Rightarrow\mathbb{L}C_a$ gives a canonical extended interleaving pseudometric on $\operatorname{D^{b}}(\mathrm{Shv}(\mathsf{P};k))$; in the saturation cases computed here it takes no finite value above the length of $\mathsf{P}$, and is finite if and only if the derived colimits agree.

arXiv abstract · PDF

Category theory and higher algebra · primary corpus · published 2026-08-17T16:25:26Z
Fatemeh Jowkar, Michael Winter
arXiv categories: math.CT, cs.DM

Arrow allegories provide a convenient abstract framework to work with lattice-valued relations, or more precisely, relations that use the elements of a given Heyting algebra as truth values. One characteristic of arrow allegories is that all relations of the given arrow allegory use the same Heyting algebra ${\mathcal H}$. In this paper we want to extend this approach to allegories where relations between different objects may use different lattices of truth values and even further to relations that use a different lattice of truth values for every pair in the relation. Therefore, we define three concrete allegories, $\mathrm{Rel}({\mathcal H})$, $\mathrm{Rel}^u({\mathcal H})$ and ${\mathcal H}{\rm-Rel}$, where the allegory listed later is a full suballegory of the previous ones. These three allegories capture the three different situations mentioned above. In particular, ${\mathcal H}{\rm-Rel}$ is the standard example of an arrow category. We investigate these allegories and provide suitable categorical definitions for these structures.

arXiv abstract · PDF

Category theory and higher algebra · primary corpus · published 2026-08-17T20:25:57Z
Ilia Pirashvili
arXiv categories: math.CT, math.AC

This paper is a continuation of arXiv:2606.17088, where I studied precartesian coextensions of commutative monoids by systems of abelian groups. In this paper, we generalise it to study coextensions by systems of commutative monoids. Among other things, we showcase that this version is able to simultaneously generalise Leech's version of coextensions and Redei's version, also called Schreier coextensions. We show that what going from systems of abelian groups to systems of commutative monoids costs us is quasi-inverses in $\mathsf{Pcoex}(M, \mathcal{L})$. Specifically, instead of a symmetric categorical group, they now only become symmetric monoidal groupoids. Moreover, though not explicitly stated in the body of the paper, another core difference is that for a monoid scheme $X$, regarded as a monoid functor, a precartesian coextension no longer need to be a monoid scheme. Thus, $\mathsf{Pcoex}(X, \mathcal{L})$ is, as stated, ineffective at studying monoid scheme coextensions. The rest of the theory goes through, but requires developing a new cohomological approach.

arXiv abstract · PDF

Category theory and higher algebra · primary corpus · published 2026-08-18T13:12:02Z
Chencheng Zhang
arXiv categories: math.RA, math.AC, math.LO

For a ring $R$, let $\mathcal{GP}(R)$, $\mathcal{GF}(R)$, and $\mathcal{PGF}(R)$ denote the classes of Gorenstein projective, Gorenstein flat, and projectively coresolved Gorenstein flat left $R$-modules, respectively. We isolate the local ultrafilter hypothesis $\textsf{LUH}$: the existence of a strongly compact cardinal implies $\textsf{LUH}$, while $\textsf{LUH}$ implies the existence of a measurable cardinal. Assuming $\textsf{LUH}$, we construct a left and right coherent ring $R$ and a strongly Gorenstein projective left $R$-module $G$ which is not Gorenstein flat; hence $\mathcal{PGF}(R)\subsetneq\mathcal{GP}(R)$.

arXiv abstract · PDF

Category theory and higher algebra · primary corpus · published 2026-08-18T22:21:53Z
Rory B. B. Lucyshyn-Wright
arXiv categories: math.CT

Working in the setting of enriched algebraic theories for a system of arities, we study several aspects of dual adjunctions between enriched algebraic categories, which we call algebraic dual adjunctions. Firstly, we generalize Freyd's theorem on contravariant algebra-valued right-adjoint functors to this setting. Secondly, we establish a biequivalence between a 2-category of algebraic dual adjunctions and a locally discrete 2-category of bifold algebras, in a sense defined in prior work of the author. Thirdly, we define special classes of algebraic dual adjunctions that we call (left- and right-)stable, in which certain free objects are reflexive, and we establish biequivalences between these and special classes of bifold algebras defined in terms of commutants in prior work of the author. Fourthly, we show that every algebra for an enriched algebraic theory canonically induces left- and right-stable algebraic dual adjunctions, and we establish a biequivalence between such algebras and left- (or right-)stable algebraic dual adjunctions, and also between saturated algebras and stable algebraic dual adjunctions. We also discuss examples of algebraic dual adjunctions, including dualization of internal modules, Pontryagin and Binz-Butzmann duality, dualization of internal affine spaces and convex spaces, dualization of semilattices, dualization of complete sup-lattices, and dualization of abelian groups with reference to a theorem of Ehrenfeucht and Łoś.

arXiv abstract · PDF

Category theory and higher algebra · primary corpus · published 2026-08-19T17:40:40Z
Kenichi Shimizu, Harshit Yadav
arXiv categories: math.QA, math.CT

Let $A$ be a commutative simple algebra in a braided finite tensor category $\mathcal{B}$. We identify the largest transparent subalgebra of $A$ as the algebra induced by a central lift of the free-module functor. This identification gives formulas for the Frobenius-Perron dimension and the Müger center of the category of local $A$-modules. These formulas give criteria for nondegeneracy, symmetry, and modularity, together with sharp bounds on $\mathrm{FPdim}_{\mathcal{B}}(A)$. We also realize the Müger center of $\mathcal{B}$ as a category of local modules over an adjoint algebra. Finally, we prove a relative-center factorization and deduce that taking the category of local modules preserves the relative Witt class.

arXiv abstract · PDF

Category theory and higher algebra · primary corpus · published 2026-08-20T09:31:35Z
Vanessa Miemietz
arXiv categories: math.RT, math.CT

In this survey article, we give an introduction to the relatively young subject of $2$-representation theory, which studies categorifications of important players in classical representation theory. In particular, we provide a streamlined exposition of the main results leading to the classification of simple $2$-representations for Soergel bimodules associated to finite Weyl groups in characteristic $0$, obtained in [M. Mackaay, V. Mazorchuk, V. Miemietz, D. Tubbenhauer and X. Zhang, Simple transitive $2$-representations of Soergel bimodules for finite Coxeter types. Proc. London Math. Soc. 126 (2023)].

arXiv abstract · PDF

Category theory and higher algebra · primary corpus · published 2026-08-20T17:46:54Z
Garrett Ervin, Eric Paul
arXiv categories: math.LO

We present a systematic development of the arithmetic of the class of linear orders under the ordered sum $(LO, +)$ and prove a number of new results. Our approach is based on a Euclidean algorithm for pairs of linear orders that almost additively commute. Among our results: (i.) We generalize and give unified proofs of the main classical theorems for $(LO, +)$, including Lindenbaum's division theorem for $(LO, +)$ and a representation theorem for additively commuting pairs of linear orders due to Aronszajn. (ii.) We solve the following problem, posed by Tarski in 1956: is it true that for every pair of linear orders $A, B$ and quadruple of natural numbers $n, m, k, l \geq 1$, if $nA + mB \cong kB + lA$ then $A + B \cong B + A$? Tarski and Chang showed the answer is yes for certain choices of the coefficients $n, m, k, l$. We show the answer is yes in general. (iii.) We prove the following characterization of the additively commuting pairs in $LO$: $A + B \cong B + A$ if and only if $ωA$ embeds initially in $ωB$ and $ω^* A$ embeds finally in $ω^* B$, or vice versa. We show this can be viewed as a correctly revised version of a refuted conjecture of Tarski. (iv.) We characterize the commutative semigroups $(S, \oplus)$ that can be represented in $(LO, +)$ and show in particular they are all naturally totally ordered commutative semigroups in the sense of Clifford.

arXiv abstract · PDF

Category theory and higher algebra · primary corpus · published 2026-08-20T18:00:24Z
Shlomo Gelaki, Victor Ostrik
arXiv categories: math.QA, math.CT

We provide some information about the Drinfeld center $\Z(\Ver_p)$ of the Verlinde category $\Ver_p$. We compute explicitly the Cartan matrix, bound quiver and cohomology of $\Z(\Ver_p^+)$, and prove that the category $\mathscr{Z}(\Ver_p^+)$ is wild for every $p\ge 7$. In the special case $p=5$, we show that $\Z(\Ver_5^+)$ has exactly $10$ non-isomorphic indecomposable objects, classify them and describe the Green ring of $\Z(\Ver_5^+)$, and compute the semisimplification of $\Z(\Ver_5^+)$.

arXiv abstract · PDF

Category theory and higher algebra · primary corpus · published 2026-08-20T23:33:51Z
Luis Gambarte, Iosif Petrakis
arXiv categories: math.CT, math.LO

The notion of a base of computability $\mathscr{C}$ in a category $\mathscr{C}$ was introduced as a tool to generate computability models, in the sense of Longley and Normann, from categories. In this paper we introduce the category $\mathsf{CatBaseComp}$ of categories with a base of computability, and we show that $\mathsf{CatBaseComp}$ has all pie limits. We prove that a Grothendieck fibration lifts a base of computability in the base category to a base of computability in the total category of the fibration, and conversely, a pullback-preserving Grothendieck fibration maps a base of computability in the total category to a base of computability in the base category of the fibration. Connecting $\mathsf{CatBaseComp}$ with the semantics of dependent type theory, we show that $\mathsf{CatBaseComp}$ is a type-category, or a (fam, $Σ$)-category with a terminal object. Moreover, we prove that CatBaseComp is a (2-fam, $Σ$)-category, a 2-categorical generalisation of a (fam, $Σ$)-category. Finally, we describe the canonical (2-dep, $Σ$)-structure of CatBaseComp, i.e., the canonical dependent arrows of CatBaseComp that are compatible with its (2-fam, $Σ$)-structure.

arXiv abstract · PDF

Categorical, quantum, and computational semantics · primary corpus · published 2026-08-19T08:33:21Z
Chengyu Zhou, Qingguo Li
arXiv categories: cs.LO

Mislove, Goubault and Varacca investigated how to define random variables in Domain theory to form monads over the category of bounded complete domains. They intended to model probabilistic programming languages with their random variables monads. In this paper, we focus on the random variables defined by Mislove from a topological perspective. We provide a topology for $\surd$-max continuous random variables on a $T_0$ space, we construct a new $T_0$ space, where $\surd$-max property is essential for the monad structures. We show that the spaces of normalized $\surd$-max simple random variables form a monad over the category of $T_0$ spaces and that the spaces of normalized $\surd$-max continuous random variables give a monad over the category of d-spaces. In addition, on a sober space, the space of normalized $\surd$-max continuous random variables is the sobrification of the space of normalized $\surd$-max simple random variables.

arXiv abstract · PDF

Categorical, quantum, and computational semantics · primary corpus · published 2026-08-19T18:39:27Z
Steven Rayan
arXiv categories: quant-ph, cond-mat.mes-hall, cs.IT, math-ph, math.CT

These notes develop four interconnected ways of reading a quantum circuit. A circuit for us begins as an operational composition of gates; then, it becomes a diagram whose local equalities may be used as calculations; next, it becomes a protected process once errors, syndromes, and logical degrees of freedom are separated; and finally, it becomes geometric when its connectivity, topology, and boundary data are treated as physical design parameters. The development begins at the level of bits and qubits before appealing to Deutsch's and Grover's algorithms as basic examples of quantum circuits. With the basics in hand, we interpret quantum circuits diagramatically, leading us to compact closed string diagrams and the ZX-calculus. After that, we consider how to correct quantum circuits by introducing the Knill--Laflamme condition, homological surface codes, and related concepts with a view towards thinking of these as operations on diagrams. The lectures eventually arrive at the properties of hyperbolic quantum codes and the prospect of physical superconducting circuits emulating the negatively-curved lattices needed to support those codes. These mathematical ideas and physical experiments, taken together, represent one way to impart a geometric layer onto quantum circuits. By the very end, we bring the ideas nearly full circle by assessing the extent to which these device physics experiments operationalize the basic ZX diagrams encountered much earlier in the story. While the later material reports on original research, and while the discussion becomes increasingly mathematical as the sections progress, no prior knowledge of quantum information, quantum computing, or quantum error correction is actually assumed.

arXiv abstract · PDF

Categorical, quantum, and computational semantics · primary corpus · published 2026-08-20T13:17:30Z
Pradyut Karmakar, Arthur J. Parzygnat
arXiv categories: math.OA, math.CT, quant-ph

Retrodiction is the act of inferring a cause from its effects, the most common example of which is Bayesian inference. Retrodiction can be defined by its structural process-theoretic properties, which are mathematically captured by category theory. This categorical definition of retrodiction has recently been shown to potentially isolate the Petz recovery map as a unique universal candidate for quantum Bayesian inference. This paper extends these results to the infinite-dimensional setting on von Neumann algebras. In the process, we provide a pedagogical review of the Petz recovery map in infinite dimensions and its relation to the more commonly used expression in the finite-dimensional setting. We formalize the open question as to whether these categorical axioms for retrodiction do in fact uniquely characterize the Petz recovery map. If such a characterization holds, this would show that Bayesian inversion and the Petz recovery map are structural necessities and not simply useful algorithms for classical and quantum inference.

arXiv abstract · PDF

Categorical, quantum, and computational semantics · primary corpus · published 2026-08-20T15:49:09Z
Samson Abramsky, Radha Jagadeesan
arXiv categories: quant-ph, cs.ET, cs.LO, cs.PL

Existing quantum programming languages confine higher order structure to a classical host while restricting the quantum layer to first order operations on qubits. This paper presents Granthi, a purely unitary higher-order quantum programming language built on three design commitments: quantum programs are first class values that may be passed, returned, and coherently composed; additive structure is tag-preserving routing rather than observational branching, so control may remain in superposition; and programmer-facing finite label types with named reversible operations provide domain-level control spaces without exposing tag management. Every well-typed term, including at function type, denotes a unitary on its boundary interface, and the compiler realizes exactly its wiring as a quantum circuit on the physical qubit layout (assuming correctness of the pytket backend). Granthi is implemented end-to-end: an OCaml DSL elaborates surface programs through a binder-free core IR to executable quantum circuits via pytket. The language directly supports the quantum switch, compiled to a static circuit, as well as interference on control-flow history and structured finite control, all within the purely unitary fragment.

arXiv abstract · PDF

Other logic and mathematical structures · primary corpus · published 2026-08-17T11:00:44Z
Agon Hajdari, Johannes Niederhauser
arXiv categories: cs.LO

We settle an open question related to Tarski's High School Algebra problem by showing that no 11-element algebra can satisfy the High School Identities while refuting Wilkie's identity. We encode the search as a SAT instance and independently verify the result. As a byproduct, we obtain a new 12-element countermodel that is not isomorphic to the previously known one.

arXiv abstract · PDF

Other logic and mathematical structures · primary corpus · published 2026-08-17T18:30:23Z
Simon Portegies Zwart
arXiv categories: physics.comp-ph, astro-ph.IM, cs.PL, nlin.CD

We present a systematic comparison between arbitrary precise arithmetic and integration, IEEE-754 compliant floating point arithmetic (fp16, bfp16, fp32, double precision fp64, and quadruple precision fp128), and two implementations of Posits (type III unum) for solving Newton's chaotic N-body problem. Each implementation is benchmarked with arbitrary precise calculations to objectively evaluate their performance in precision as well as speed. We rely on hardware and compiler implementations for fp64, and software implementations for arbitrary-precision arithmetic and Posits. Half precision arithmetic (fp16, bfp16, and Posits$<16,1>$) are insufficiently precise for solving Newton's equations of motion. Single precision (fp32, and Posits$<32,2>$) could be used for statistical ensemble calculations, but lead to relatively large errors in any individual strong encounter. All 64-bit implementations fp64 as well as Posits (Posits$<64,3>$) experience difficulty in our tests. One of the implementations of Posits (Universal) gives precision comparable to fp64 but is slow (by at least an orders of magnitude compared to fp64 after correcting for the more efficient hardware support for the latter). The other (CPPPosits) has a speed comparable to fp64 but has systematically larger errors (by about an order of magnitude compared to fp64 with excesses exceeding two orders of magnitude). As a consequence, this implementation leads to a systematic drift in the result space and has difficulty resolving close encounters. Posits and fp64 have difficulty when integrating a dynamical system in a moving reference frame; testing Galileo invariancy. In their current implementation, Posits do not seem to be the ideal alternative for fp64 when integrating chaotic or stiff ordinary differential equations, such as Newton's equations of motion.

arXiv abstract · PDF

Other logic and mathematical structures · primary corpus · published 2026-08-18T03:18:18Z
Juliane Trianon Fraga, Vinicius de Oliveira Rodrigues
arXiv categories: math.GR, math.GN, math.LO

We prove in ZFC that every torsion-free Abelian group of cardinality $\mathfrak c$ admits a Hausdorff countably compact group topology without nontrivial convergent sequences. In particular, this applies to the free Abelian group $\mathbb{Z}^{(\mathfrak c)}$, the Baer-Specker group $\mathbb{Z}^ω$ and $\mathbb{Q}^{(\mathfrak c)}$. For the topology constructed on $\mathbb{Z}^{(\mathfrak c)}$, the coordinatewise nonnegative cone is countably compact in the subspace topology. Consequently, there exists in ZFC a commutative Tychonoff countably compact topological semigroup which has two-sided cancellation but is not a group, giving a negative answer to Wallace's question. Combined with earlier results, the main theorem also yields in ZFC a Tychonoff countably compact topological semigroup containing a copy of the bicyclic semigroup and a functionally Hausdorff countably compact paratopological group that is not a topological group.

arXiv abstract · PDF

Other logic and mathematical structures · primary corpus · published 2026-08-19T08:04:26Z
Krishna Bhatia
arXiv categories: quant-ph, cs.LG, cs.LO

Tsetlin Machines (TMs) learn interpretable Boolean clauses using finite-state automata. We introduce the Quantum-Logic Tsetlin Machine (QL-TM), which replaces Boolean literals with quantum propositions represented by projectors while retaining classical include/exclude automata. Clauses are restricted to commuting measurement contexts and activate through the Born probability of their joint projector. We prove an exact reduction to ordinary Boolean TM clauses in diagonal computational-basis contexts and connect Pauli-projector clauses to stabilizer and syndrome semantics. Controlled experiments on Bell states, phase-flip syndromes, randomized 16-class stabilizer tasks, mixed literal pools, context-budget ablations, and finite-shot noise show that correct non-diagonal contexts recover physically meaningful clauses, while diagonal or wrong contexts lose the relevant phase/syndrome information. The context-budget results closely follow the predicted separability ladder 2^(b-k) as true stabilizer generators are removed. The contribution is a controlled bridge between Tsetlin clause learning and quantum logic, not a claim of quantum advantage.

arXiv abstract · PDF

Other logic and mathematical structures · primary corpus · published 2026-08-19T11:11:49Z
Marco B. Caminati
arXiv categories: cs.FL, cs.AI, cs.LO, math.LO

In the last years, a number of proofs of the fact that $O_2$ is a multiple context-free grammar (MCFG) were given. Such results can be exploited in the fields of both computational linguistics and of computational algebra. Here, we focus on a recent such proof spelled in terms of factorizations of string tuples, and give a new result with a stronger characterization of such factorizations than in existing theorems.

arXiv abstract · PDF

Other logic and mathematical structures · primary corpus · published 2026-08-19T19:29:18Z
Assaf Kfoury
arXiv categories: cs.LO

This document is the result of pulling together small parts of different lecture notes I have written over several decades for first-year graduate-level courses -- typically with the title Formal Methods -- which included many other topics of mathematical logic and theoretical computer science. After combining these materials, I updated the references and adjusted the text to account for progress accomplished in the intervening years. The sample of open problems in the last section is a small collection of special cases that are still unresolved up until the date of this writing.

arXiv abstract · PDF

Other logic and mathematical structures · primary corpus · published 2026-08-20T15:21:40Z
Konrad Wróbel
arXiv categories: math.DS, math.GR, math.LO

We prove that the orbit equivalence class of every free ergodic probability-measure-preserving (pmp) action of a free group contains a totally weak mixing action. Equivalently, every ergodic treeable pmp equivalence relation of cost $n\in\mathbf{N}\cup\{\infty\}$ is generated by a free totally weak mixing action of $\mathbf{F}_n$. This answers a question of Miller and Tserunyan. The proof goes by considering a Polish space of edge slidings along a fixed mixing transformation and proving that for every $w\not=e\in\mathbf{F}_n$ the set of edge slidings that produce an action with $w$ weakly mixing forms a comeager set.

arXiv abstract · PDF