arXiv weekly literature review

Proof assistants and mechanized formalization · primary corpus · published 2026-08-10T08:52:54Z
Arnaud Mayeux
arXiv categories: cs.LO, math.CT

Given a category $\calC$ and a center, that is a collection of pairs $(d_i, N_i)$ consisting of a morphism $d_i$ and a sieve $N_i$ over its codomain, the dilatation of $\calC$ is a new category $\calC'$ in which every $n \in N_i$ factors, uniquely and functorially, through $d_i$. This paper presents the theory of dilatations of categories through a full formalization of the construction and its main theorems in the Lean~4 proof assistant, on top of the Mathlib library. An appendix collects a systematic dictionary between the mathematical statements and the Lean declarations that formalize them.

arXiv abstract · PDF

Proof assistants and mechanized formalization · primary corpus · published 2026-08-13T16:43:44Z
Jim Woodcock, Gabriel Leite, Augusto Sampaio, Ran Wei
arXiv categories: cs.SE, cs.AI, cs.LO

We address the use of large language models (LLMs) to help discover Isabelle proofs. An Isabelle build establishes that the submitted theory is accepted, but not that an LLM changed only what the developer authorised. We present CAPRI, a contract-aware repair workflow in which Isabelle checks the proof and an independent checker enforces a machine-readable edit contract. Prompts, proposals, candidate repositories, diagnostics, verdicts, and hashes are retained for audit. We evaluate five workflows on twelve failed proofs from four developments, with three replicates per task and condition, giving 180 runs and 138 valid repairs. Of 144 terminal candidates accepted by Isabelle, six had modified protected text; all arose in iterative workflows that could edit a complete theory. A proof-body-only interface produced 29/36 valid repairs and no contract violations, compared with 31/36 for the corresponding full-theory workflow. One-shot repair produced 22/36, while a later prospectively frozen iterative workflow produced 32/36; these figures compare complete workflows rather than individual mechanisms. A separate post hoc OpenRouter campaign found no improvement in the designated Luna comparisons. A Sol configuration with matched demonstrations produced 33/36 repairs, compared with 29/36 in the frozen OpenAI Responses condition, but the difference was not statistically significant in a one-sided exact McNemar test ($p=0.0625$).

arXiv abstract · PDF

Formalized mathematics and autoformalization · primary corpus · published 2026-08-11T13:13:11Z
Tianjiao Nie, Ao Zhang, Yusen Tang, Damiano Testa, Shing-Tung Yau, Peng Li, Yuan Zhou
arXiv categories: cs.LO, math.GR

Large-scale formalization of advanced mathematics requires more than translating individual statements: it must reconstruct a coherent theory distributed across heterogeneous sources. This process raises four challenges: discovering implicit dependencies, correcting source defects, preserving semantic fidelity, and reconciling cross-source misalignments. We present FormaTheoria, an end-to-end, AI-assisted workflow that coordinates source acquisition, formalization, proof construction, recursive dependency discovery, independent review, and reconciliation, while preserving provenance and protecting approved declarations. A shared agent framework supports long-horizon execution through tool use, context compaction, review-gated termination, section-level source context, and dependency-aware batch parallelization. Applying FormaTheoria to major components of the Classification of Finite Simple Groups (CFSG), we construct a machine-checked Lean development extending through the Bender--Suzuki theorem and encompassing the Feit--Thompson Odd Order Theorem, Glauberman's $Z^*$ theorem, and the Brauer--Suzuki theorem. This development verifies an extensive body of deeply interdependent finite-group theory while providing a foundation for continuing the CFSG formalization. An empirical analysis of the code and recorded construction process supports the practical relevance of the identified challenges and illustrates the roles of the corresponding workflow components. Together, these results demonstrate how AI-assisted workflows can reconstruct mathematically significant formal theories from distributed literature by combining language-model agents with formal verification, structured review, and explicit dependency management.

arXiv abstract · PDF

Formalized mathematics and autoformalization · primary corpus · published 2026-08-11T13:36:52Z
Rob Cornish, Iacopo Ghinassi, Po-Hung Yeh, Shuqi Liu, Qiyuan Xu, Haoxuan Yin, Dominik Wagner, Wenda Li, Yee Whye Teh, Luke Ong
arXiv categories: cs.CL, cs.AI, cs.LO

Autoformalisation (AF) systems map natural language reasoning steps into formal statements in a proof assistant such as Lean. We consider how to assess the faithfulness of these systems. Existing approaches require expensive human-annotated ground truth, or rely on LLM judges or embedding models, which come with limited guarantees of accuracy. In addition, these methods typically only consider inputs that are known to be correct, and therefore do not assess whether the AF translates incorrect inputs faithfully. To address these limitations, we propose a new benchmark for AF faithfulness that is cheap to apply, sound under weak assumptions, and assesses both positive and negative examples. Our method is based on automatically generating perturbed reasoning steps that are designed to be invalid, and then measuring validity preservation on unperturbed steps and invalidity preservation on perturbed steps. We apply our method to eight AF systems across four mathematical datasets, and observe pervasive sycophancy: many AFs "silently correct" invalid inputs into provable statements. The most validity-preserving fine-tuned AFs are also the most sycophantic, suggesting a tension between validity and invalidity preservation in current AF systems.

arXiv abstract · PDF

Program verification, analysis, and software security · primary corpus · published 2026-08-10T03:47:38Z
Xiaotian Zhou, Kai Tu, Ali Ranjbar, Yilu Dong, Gang Tan, Syed Rafiul Hussain
arXiv categories: cs.CR, cs.PL

ASN.1 is a widely used interface description language, and UPER (Unaligned Packed Encoding Rules) is one of its key encoding rules, particularly popular in security-critical domains such as cellular networks and vehicle-to-everything (V2X) communication. To ensure the correctness and security of this foundational infrastructure, we present VUPER, a framework for generating verified ASN.1 UPER parsers. We first formalize the notion of a bit-precise parser and identify properties that prove round-trip consistency for parsers and serializers, while accounting for ASN.1 features such as backward/forward compatibility. We then implement and verify parser and serializer combinators for ASN.1 basic types and structures, while adhering to the UPER specification. We also develop a compiler that translates ASN.1 definitions into verified parsers. Finally, we develop a dynamic testing framework using the VUPER parser as a test oracle. To empirically evaluate our approach, we test 7 open-source and 4 commercial ASN.1 parsers using 5G and V2X communication protocols. VUPER uncovers 20 types of inconsistencies in popular parsers and demonstrates stricter compliance with ASN.1 UPER standards. Additionally, we demonstrate concrete attacks by exploiting these parser vulnerabilities.

arXiv abstract · PDF

Program verification, analysis, and software security · primary corpus · published 2026-08-10T04:53:10Z
Xin Xu, Siru Tao, Kaizhen Tan
arXiv categories: cs.CR, cs.LO, cs.PL

A disjunctive policy allows a value to depend on at most one of two secrets and never on both: an analyst may consult one client's file or the other's, a share of a split secret may be released but not its sibling. Such policies are not lattice-shaped, and Hunt and Sands introduced the quantale of information to give them a semantics, leaving the enforcement layer open. We build the flow-sensitive type system family that the quantale calls for, and show that the object which makes such families useful, the universal type object from which every member specialises, splits in two, with a consequence for enforcement. Over the free commutative quantale on the program variables the whole mechanism survives for every policy: monotone renaming, canonical derivations, principal typings, internal completeness. Over the free object with idempotent generators the certified bound is strictly more precise and still sound, because it records that two reads of one source honour one disjunct. The gap cannot be closed from inside the independent-attribute family: no mechanism of that shape whose labelling maps support monotone renaming certifies a bound more precise than the first, and for principal typings under generator-exact homomorphic specialisation the two coincide. Under the ethical-wall and secret-sharing labels the second read of a disjunctive source therefore drives every such certificate to no guarantee, and programs that satisfy the policy are rejected. The literal transcription of the lattice-era object is no escape either: it is a further quotient that loses branch disjunction. Precision is recovered by deferring specialisation to the judgement level, and the resulting read-out map is the least sound join-preserving one.

arXiv abstract · PDF

Program verification, analysis, and software security · cs.SE candidate · published 2026-08-10T06:47:39Z
Shenyuan Guan, Qiaodan Hou, Yanjun Chen, Xincheng Wen, Jia Feng, Keke Lian, Cuiyun Gao
arXiv categories: cs.SE, cs.CR

Static Application Security Testing (SAST) tools have become indispensable in modern secure software devel- opment. However, these tools often generate false-positive (FP) alerts, imposing substantial manual inspection costs and reducing the trust from developers. Existing FP reduction methods still face two primary challenges. First, the large differences among SAST tools and vulnerability categories make it difficult for these methods to learn recurring patterns in historical false positives. Moreover, the knowledge used by these methods are largely static and cannot be updated as newly validated cases accumulate. To address these challenges, we propose Memoir, a memory- driven framework for identifying false positives by transform- ing historical FP alerts into reusable semantic memories. It consists of two key modules. First, historical semantic memory construction converts historical FP alerts into structured semantic memories through LLM-guided annotation, pattern clustering, and memory synthesis to capture reusable behavioral patterns. Moreover, memory-driven identification and evolution retrieves relevant memories and performs semantic verification against taxonomy consistency and security invariants before making the final prediction. It then incorporates verified predictions back into the memory repository, allowing the knowledge base to evolve as new cases accumulate. We evaluate Memoir on CWE- Bench-Java to demonstrate its effectiveness in real-world security analysis. Specifically, Memoir achieves an F1-score of 99.43% with a Recall of 98.88% and perfect Precision, consistently outperforming other baselines. Furthermore, an industrial case study on production software systems from a top IT company shows that the learned memory base generalizes effectively across different SAST tools without retraining.

arXiv abstract · PDF

Program verification, analysis, and software security · primary corpus · published 2026-08-10T12:11:04Z
Jeffrey C. Ching, Danfeng Zhang
arXiv categories: cs.PL, cs.CR

Information flow analysis is the de facto method of assessing confidentiality and integrity issues. However, the widespread adoption of information flow analysis in real-world systems is still lacking, partly due to a fundamental gap between theory and practice: the dynamic nature of security concerns in real-world systems goes beyond the scope of existing techniques that assume a static policy (i.e., data secrecy does not change). Recognizing the fundamental gap, a substantial amount of research has studied various aspects of it (e.g., enabling declassification, endorsement, and invocation policies). A recent work takes a step further by formalizing a promising end-to-end policy called dynamic release that unifies prior formalizations by allowing information flow restrictions to downgrade and upgrade in arbitrary ways. However, how to soundly enforce the powerful dynamic release policy is still an open question. In this paper, we present the first type system that enforces dynamic release policy and formally prove its soundness. More specifically, we (1) formalize a core language that enables dynamic release policy, (2) develop a type system that checks dynamic release policy, (3) develop new proof techniques and formally prove that the type system enforces dynamic release policy, and (4) implement a prototype of the type system as an extension to the Rust language, along with case studies on conference reviewing system and Civitas.

arXiv abstract · PDF

Program verification, analysis, and software security · primary corpus · published 2026-08-10T21:37:47Z
Jordan Peper, Krish Kapadia, James Gast, Ethan Howes, Ivan Ruchkin
arXiv categories: eess.SY, cs.LO

Symbolic model checking is an effective approach for verifying semantically rich temporal-logic properties of cyber-physical systems, but it hinges on discretizing continuous-state dynamics into a finite-state abstraction. To transfer verification guarantees from the abstract model to the concrete CPS, the abstraction must conservatively approximate the concrete state space and behaviors. Hence, model-builders must maintain this soundness while balancing pessimism with tractability. However, they face several common pitfalls such as under-approximating the state space, under-approximating transitions, unsound pruning of "degenerate" behaviors, and improper specification lifting. This tutorial presents a pragmatic, conservative-by-construction workflow for building discrete abstractions of closed-loop dynamical systems. The workflow consists of four modular steps with interchangeable subroutines: (i) state-space partition and abstraction-function design, (ii) conservative transition construction via axis-aligned bounding boxes, polytopes, or sampling with PAC coverage certificates, (iii) mitigation of spurious transitions and self-loops using certified erasure and counterexample-guided abstraction refinement, and (iv) sound lifting of LTL specifications using may-must semantics. We demonstrate the end-to-end pipeline on three case studies and report how these design choices affect abstraction structure, runtime, and verification outcomes.

arXiv abstract · PDF

Program verification, analysis, and software security · cs.SE candidate · published 2026-08-10T22:06:14Z
Muhammad Ali Hassan Ahmad, Muhammad Hashim Ali, Muhammad Ali Amer, Muhammad Naiman Jalil, Muhammad Hassan, Affan Rauf
arXiv categories: cs.SE

A blockchain is a decentralized, secure ledger system that enables transparent and immutable record-keeping, essential for trust and security in digital transactions. Smart contracts are self-executing agreements encoded on a blockchain, enabling different parties to fulfill the terms of the agreement automatically. These contracts trigger corresponding actions when conditions are met, ensuring decentralized and transparent transactions. Writing reliable smart contracts is challenging due to the lack of standardization. To find security vulnerabilities, tools based on various approaches, including symbolic execution, are used. However, these tools often report a large number of false positives, raising concerns about their reliability. The time and effort spent investigating false positives diverts resources from addressing actual vulnerabilities. Therefore, such tools must also be evaluated according to the rate of false positives they exhibit. More importantly, the algorithms and heuristics used by the tools must be enhanced to distinguish between true vulnerabilities and false alarms. In this paper, we first demonstrate the prevalence of false positives in vulnerability reports generated by Mythril, a symbolic execution-based analysis tool for Ethereum smart contracts. We analyze the root causes of these inaccuracies and devise a rule-based approach based on the gained insight to reduce false positives. We implement our rules for the most impactful vulnerabilities in Mythril and assess the effectiveness of our approach. Our results show a significant reduction in false positives without compromising the detection of true vulnerabilities, thus enhancing the tool's reliability.

arXiv abstract · PDF

Program verification, analysis, and software security · primary corpus · published 2026-08-11T10:10:19Z
Siyu Chen, Chungha Sung, Xuyang Li, Jingbo Wang
arXiv categories: cs.SE, cs.PL

Probabilistic extensions of Datalog enable static analyses such as pointer analysis, data race detection, and side-channel analysis to rank alarms by likelihood, but this added expressiveness also introduces a new challenge absent from deterministic analyses: the final output may contain alarms that are individually plausible yet mutually inconsistent, because marginal probabilities do not guarantee joint satisfiability. As a result, developers may spend effort investigating combinations of alarms that can never co-occur in any possible world. We address this problem by formalizing such inconsistencies as minimal unsatisfiable subsets (MUSes) and introducing PPProbe, a conflict extractor specialized for probabilistic Datalog analyses. Rather than improving MUS enumeration in general, PPProbe exploits the structure of Datalog derivation graphs to guide the search toward likely conflicts and prune the search space through bottom-up UNSAT inference. We evaluate PPProbe on 70 benchmarks from power side-channel analysis, data race detection, semantic diffing, and Bayesian-network inference. The results show that PPProbe achieves 2.5 to 24 times higher throughput than state-of-the-art MUS enumerators, and that the conflicts it identifies yield a conservative estimate of false-positive reduction, filtering out an average of 47.7% of mutually inconsistent alarms.

arXiv abstract · PDF

Program verification, analysis, and software security · cs.SE candidate · published 2026-08-12T07:34:29Z
Bin Duan, Tarek Mahmud, Meiru Che, Yan Yan, Naipeng Dong, Dan Dongseong Kim, Guowei Yang
arXiv categories: cs.SE

Python libraries underpin deep learning, scientific computing, data analysis, and computer vision, making their reliability critical to downstream applications. Testing their APIs requires inputs that satisfy both per-parameter constraints and dependencies among parameters. Existing approaches either leave such constraints implicit in generated programs or rely on library-specific parsing rules. This paper introduces VistaFuzz, a document-guided fuzzing technique that uses a locally served open-sourced LLM to extract parameter specifications from API documents and generate inputs that satisfy both parameter constraints and inter-parameter dependencies. We evaluate VistaFuzz on 7,718 APIs across twelve Python libraries. Inter-parameter relationships occur in 40.1\% of tested APIs, and disabling their resolution reduces the valid generation rate on those APIs from above 95\% to 31.6\%--52.8\%. VistaFuzz reports 74 issues, of which 43 have been confirmed by developers and 29 have been fixed.

arXiv abstract · PDF

Program verification, analysis, and software security · primary corpus · published 2026-08-12T09:16:43Z
Samuel Frontull, Manuel Meitinger, Georg Moser
arXiv categories: cs.PL

Existing approaches to resource analysis of programs can be classified into two main paradigms: static analysis and dynamic analysis methods. The former allow for formal guarantees but are inherently incomplete; the latter are widely applicable but may miss rare but characteristic (worst-case) scenarios and thus lack soundness. Hybrid approaches attempt to combine the strengths of both paradigms, thereby enabling the analysis of programs that are either too complex for purely static techniques or where dynamic approaches suffer from combinatorial explosion. In this paper, we present a novel hybrid approach that systematically derives upper bounds for the worst-case resource consumption of functional programs. Our method combines dynamic symbolic execution to exhaustively explore all possible computation paths within a constrained input space with mixed-integer linear programming to derive empirically sound upper bounds. We have implemented the methodology in a prototype tool, dubbed CompAS, which we made available on Zenodo.

arXiv abstract · PDF

Program verification, analysis, and software security · primary corpus · published 2026-08-13T01:17:11Z
Logan Kenwright, Partha Roop, Sobhan Chatterjee, Nathan Allen
arXiv categories: cs.LO, cs.FL

Signal Temporal Logic (STL) is a popular formalism for the temporal safety properties of cyber-physical systems, most often used for runtime verification. In the synchronous family of languages, safety properties are instead expressed as synchronous observers, modules composed with a program for static verification, which are also runnable specifications suitable for runtime verification, though this use is rarely explored. We present a technique for compiling the synchronous fragment of STL (SSTL) into synchronous observers in the dataflow language Lustre. Unlike previous work, we allow arbitrary nesting of bounded SSTL properties via modular compilation, and admit a globally unbounded outer operator for online monitoring; the resulting observers serve both runtime verification and, as a by-product, static verification with the Kind2 model checker. We further contribute an interactive visualiser that renders a property's three-valued verdict over an editable trace, and evaluate on two case studies from the literature: a spring-mass system and a car-following cruise controller.

arXiv abstract · PDF

Program verification, analysis, and software security · primary corpus · published 2026-08-13T10:08:41Z
Michael Chesser, Paul Quirk, Douglas Cooke, Guy Farrelly, Surya Nepal, Damith C. Ranasinghe
arXiv categories: cs.CR, cs.PL

Processor specifications underpin critical security and program- analysis tools such as disassemblers, decompilers, and emulators, yet, their correctness is rarely examined. Errors in specifications distort program behaviour, obscure vulnerabilities, and enable analysis-evasion techniques. Validating processor specifications is a non-trivial task. Our study is a significant undertaking to enable, for the first time, the systematic validation of open-source SLEIGH language specifications, predominantly used by Ghidra. We design and implement a testing framework based on an automated oracle validation strategy by proxy. Our approach leverages the structure encoded in a specification itself to enumerate decodable instruction forms and generate targeted initial states. Then differentially test the successful decoding and emulation of those instructions by comparing emulators exercising the processor specification against hardware references. Applying InSPECtor across diverse, open-source specifications---x86-64, AArch64, ARM/Thumb, RISC-V, MSP430---embedding differences in specification styles, author preferences, and instruction set architecture designs, we uncovered over 38,920 discrepancies that led to 125 unique bugs with proposed fixes, identifying decoding and semantic defects as well as cross-vendor inconsistencies. We distill our findings into 8 concrete recommendations to drive future improvements. Our work underscores the importance of specification correctness and provides a practical tool to substantially improve the fidelity of SLEIGH processor specifications, strengthening the reliability of downstream security and analysis tools.

arXiv abstract · PDF

Program verification, analysis, and software security · cs.SE candidate · published 2026-08-13T12:58:36Z
Sofia Bobadilla, Humaira Afrin, Angela Novelli, Martin Monperrus
arXiv categories: cs.CR, cs.SE

Blockchains are among the most adversarial environments in computing. Billions are stolen by cybercriminals who exploit vulnerabilities. This is an open problem and no concept or technique has proven to really make a difference. In this paper, we claim that the classical notion of program invariant is perhaps the most powerful solution to the problem. We devise anoriginal experimental protocol to 1) study how invariants would have protected against past real-world attacks and 2) whether state-of-the-art automated tools can find them. The experimental toolchain is sophisticated. It is based on INVARIANTEVAL, a benchmark of 28 real Ethereum exploits, each paired with a human-authored invariant that blocks the attack. We validate every invariant with PONDEREPLAY, a replay framework that re-executes transactions in order to prove the correctness and soundness of smart contract invariants. We demonstrate that smart contract invariants block all the cybercriminal attacks in INVARIANTEVAL, fully validated by replaying 108,637 historical transactions. Our large-scale experiments clearly demonstrate that smart contract invariants protect against cybercriminals.

arXiv abstract · PDF

Program verification, analysis, and software security · primary corpus · published 2026-08-13T13:14:31Z
Bernd Finkbeiner, Martin Fränzle, Florian Kohn, Paul Kröger
arXiv categories: cs.PL

Stream-based monitoring is a runtime verification approach for cyber-physical systems that translates streams of input data, such as sensor readings, into streams of aggregate statistics and verdicts about the safety of the system. It is usually assumed that the values on the input streams represent fully accurate measurements of the physical world. In reality, however, physical sensors are prone to measurement noise and errors. These errors are further amplified by the processing and aggregation steps within the monitor. This paper introduces RLola, a robust extension of the stream-based specification language Lola. RLola incorporates the concept of slack variables, which symbolically represent measurement noise while avoiding the aliasing problem of interval arithmetic. We present algorithms for both online and offline monitoring of RLola specifications. Since monitoring RLola specifications may require unbounded memory in general, we identify a rich fragment of RLola that can be automatically translated into monitors with guaranteed constant memory usage for online monitoring. An online RLola monitor observes a live system and provides real-time feedback on the current status of specified assertions. A satisfiability-modulo-theories-based offline algorithm analyzes complete system traces and determines whether a hypothetical ground-truth trace exists that satisfies all assertions at all time points. The offline algorithm can therefore detect violations that the online algorithm may miss. We implement these algorithms in the existing RTLola framework and evaluate their precision and running time based on a comprehensive example.

arXiv abstract · PDF

Programming-language semantics, types, and calculi · primary corpus · published 2026-08-10T15:58:27Z
Louis Rustenholz, Alessio Mansutti, Pedro López-García, Félix Ridoux, Niki Vazou, Manuel V. Hermenegildo
arXiv categories: cs.PL, cs.LO

Least fixpoints are fundamental to program semantics, but they abstract away the recursive structure that generated them. We introduce operator semantics: a semantic intermediate representation between syntax and classical denotational semantics, which treats programs as operators. Abstract compilation is then understood as the act of abstracting such operators. We develop higher-order abstract domains for functions, operators, and programs themselves, in which composition is the key novel primitive, together with a categorical framework for constructing sound, precise, and modular abstract compilers. We instantiate this framework in the context of recurrence-based static cost analysis, developing solver-independent, optimal recurrence extraction techniques for recursive programs over algebraic data types, that support general function unknowns and catamorphic metrics, a broad class of size metrics beyond traditional approaches.

arXiv abstract · PDF

Programming-language semantics, types, and calculi · primary corpus · published 2026-08-11T09:26:24Z
Jake Masters, Nobuko Yoshida
arXiv categories: cs.LO, cs.PL

A precise (sound and complete) subtyping relation $\leq$ specifies that $T'$ is a subtype of $T$ if and only if a program of type $T'$ can always safely replace a program of type $T$ without compromising the safety of a larger program. This paper formulates and proves preciseness of subtyping for mixed choice multiparty session types with session delegation, creation, and interleaving. We prove soundness by developing the first general type system for a full mixed choice multiparty session $π$-calculus. To prove completeness, we introduce the three-party lock, which is a minimal and general form of liveness error for handling interleaved sessions, and we establish a new proof technique based on a construction of scheduler processes which enable exhaustive detection for all failures of the subtyping relation. We then extend the preciseness results to a family of mixed choice multiparty session types. Algorithms for checking (1) subtyping and (2) safety, deadlock-freedom, and liveness of typing contexts are fully implemented and optimised to run in quadratic time with respect to the size of the state space and typing context, and have been evaluated with (mixed choice) case studies from the literature.

arXiv abstract · PDF

Programming-language semantics, types, and calculi · primary corpus · published 2026-08-11T12:34:39Z
Molham Aref, Leonid Libkin, Wim Martens
arXiv categories: cs.DB, cs.PL

SQL is the database community's success story in terms of language design. The key reason for its success is its declarativeness: it gives rise to optimizability, reducing the programmer's burden significantly. However, given the evolving complexity of problems to solve with query languages, our community needs to re-think some of the fundamental early query language design decisions. Our experience in having worked on the design of Rel (a language for end-to-end relational programming) tells us that it is possible to design, implement, and successfully deploy a language based on fully normalized relations. Such relations avoid what Codd called corrupted relations and what we commonly refer to as bags, and the 'harmful' 'billion dollar mistake' that we know as nulls. In the SQL world, it is accepted that bags and nulls are tolerated as an unavoidable evil. We argue that the evil is completely avoidable: reasons offered for justifying bags and nulls evaporate at a closer examination. In addition to debunking them, we also describe opportunities offered by a null-free language with set semantics.

arXiv abstract · PDF

Programming-language semantics, types, and calculi · primary corpus · published 2026-08-11T16:17:48Z
Emma Tye
arXiv categories: cs.PL

In high-level functional languages, the compiler often gives users little control over the runtime representation of data types. Yet how we model data structures at the program level can be different to how we want to represent them at the binary level, for efficiency or legacy reasons. Hence being able to describe data layouts and their transformations for data types is a useful and necessary part of programming, but difficult to do correctly, efficiently and ergonomically. We present a model of finite algebraic data types as a commutative rig (a ring without additive inverses), where the rig-equalities are modelled by isomorphisms between data. Using this approach, we can also model embedding a data type into a larger type (e.g. bit-padding) as a partial isomorphism.

arXiv abstract · PDF

Compilers, code generation, and programming tools · primary corpus · published 2026-08-10T15:53:07Z
Nicklas Nidhögg
arXiv categories: cs.FL, cs.DC, cs.PL

A certified split point lets a parallel lexer cut unlexed input at a single byte with the serial token stream provably preserved, but several conventional token sets in the predecessor's controlled study certify no byte once string, comment, or whitespace-run forms are included (arXiv:2608.03473). We generalize from a byte to a bounded window: a byte string after which the position where the current token began is known, regardless of surrounding context. We certify the directly usable form of that recovery: the token covering the window's final byte begins at the reported origin. The certificate is conditional on occurrence and may be vacuous; every applicability figure counts only windows carrying an asserted completely tokenizable occurrence witness. We give a conservative model of a maximal-munch scanner's possible histories across a window, prove it sound, and decide reachability in that model exactly by exhausting a finite quotient of its reachable configurations, so every answer of the unbudgeted procedure is either a certified window with its origin or a proof that the model admits none. Within the stated flat, non-nullable, completely-tokenizable scope, model-positive answers are semantic certificates; negatives are relative to the conservative model, which deliberately refuses some windows a greedy scanner would allow. In a sample of 400 random token sets, 91 of the 95 non-nullable sets certifying no byte gain a witnessed window, with zero inconclusive searches, and every exact-empty row of the predecessor's study gains a witnessed window of two to four bytes. Rewind-stress rows exercised 1,079,392 executions that scanned through the window and contained at least one rewind, with zero disagreements against the shipped scanner. The analysis runs once after automaton construction, using only the compiled tables and no input.

arXiv abstract · PDF

Compilers, code generation, and programming tools · primary corpus · published 2026-08-10T22:50:27Z
Costain Nachuma, Minhaz F. Zibran
arXiv categories: cs.SE, cs.AI, cs.HC, cs.PL

Comprendia is an Eclipse plugin that integrates structural dependency visualization with LLM-powered code explanation on a shared interactive graph for Java program comprehension. The tool rests on four pillars: (1) a multi-edge-type dependency graph with live search and multiple layouts; (2) LLM explanations grounded in Graph-Aware Callee Pruning (GACP), an auditable strategy that selects relevant callees using the same graph the developer navigates; (3) a clone-detection overlay that highlights duplication and suggests extract-to-parent refactoring opportunities; and (4) a CVE risk overlay powered by OSV.dev. GACP uses graph distance, inheritance collapse, and edge-type weighting to produce prompts that are reproducible across LLM families and traceable to visible graph nodes. We demonstrate Comprendia on a Java project containing known clones and vulnerabilities, showing how the unified graph substrate supports comprehension while keeping the developer in control. Screencast: https://youtu.be/1wlh_RYehzA

arXiv abstract · PDF

Compilers, code generation, and programming tools · primary corpus · published 2026-08-13T20:35:02Z
Chungha Sung, Nikil V. Shyamsunder, Hanliang Zhang, Daniel Kroening, Joonwon Choi
arXiv categories: cs.PL, cs.DC

Multi-engine AI accelerators such as AWS Trainium comprise specialized compute engines that execute in parallel, and the compiler must synchronize the data dependencies between them. For straight-line code this is simple: each dependency reduces to waiting for a threshold count of instruction completions, which the compiler computes statically. Loops admit no such static threshold; a simple solution inserts all-engine barriers at iteration boundaries, resetting synchronization state so each loop body can be treated as straight-line, at the cost of parallelism. We present a barrier-free synchronization algorithm that instead enforces each dependency precisely across structured control flow with arbitrarily nested, dynamically bounded loops. The key idea is to compute dynamic thresholds at runtime from tracked loop iteration counts. We implemented it as a compiler backend pass at the AWS Neuron ISA level. On a suite of ML kernels, it reduces latency 10-45% relative to the barrier-based baseline, achieves a 3.3x speedup on a synchronization-bound microbenchmark, and often matches or exceeds hand-tuned manual allocation. Issuing a consumer too early violates its dependency, while issuing too late unnecessarily stalls execution. We formally characterize the minimum synchronization required for correctness and verify in the Lean proof assistant, via bisimulation, that our algorithm meets this criterion.

arXiv abstract · PDF

Compilers, code generation, and programming tools · primary corpus · published 2026-08-13T20:37:48Z
Manuel S. Drehwald, Marcelo Domínguez, Kevin Sala, Alán Aspuru-Guzik, Johannes Doerfert
arXiv categories: cs.PL

High-performance GPU programming has traditionally forced a compromise between execution efficiency and memory safety. While Rust guarantees compile-time memory safety for host CPUs via its strict ownership model, applying these constraints to massively parallel GPU execution environments has previously mandated either vendor-locked Domain-Specific Languages (DSLs) or escaping to explicit unsafe raw pointers. This paper presents a zero-overhead, multi-vendor GPU compilation framework built natively into the Rust compiler (rustc) and LLVM backends. We leverage Rust's rich type system, ownership system, and strict aliasing guarantees (noalias) to efficiently manage and optimize data transfers through LLVM's Offload infrastructure. We expose the technical challenges of cross-vendor ABI lowering mismatches between Host and Device targets and introduce a two-pass compilation pipeline capable of safely handling both manual and compiler-generated memory movements. Evaluating our framework on RAJAPerf demonstrates that our rustc-based solution can generate competitive LLVM IR for GPU kernels, achieving a solid kernel performance against native, hand-optimized CUDA and HIP C++ baselines.

arXiv abstract · PDF

Compilers, code generation, and programming tools · primary corpus · published 2026-08-14T16:52:25Z
Vinícius Silva, Kael Soares, Márcio Costa e Fernando Magno Quintão Pereira
arXiv categories: cs.PL

This work studies memory allocation for constant-bounded programs, whose execution length is syntactically limited for all inputs. Examples of such programs include verified kernel extensions, cryptographic routines, and fixed-shape machine-learning models. We show that constant boundedness enables a tight, polynomial-time approximation of optimal stack usage by viewing control flow as a tree and applying a tree-scan allocation strategy augmented with memory defragmentation. Our approach guarantees memory usage bounded by the maximum live memory plus, at most, the size of the largest buffer, and is optimal when in-place swapping is permitted. We deploy the proposed allocator in two scenarios. First, in an Elixir-to-eBPF compiler, as a spiller that optimizes stack space. Second, as a static heap allocator for bounded MLIR programs using the Structured Control-Flow dialect. Results demonstrate stack reductions exceeding 90% on real eBPF workloads and show that, even under aggressive code expansion, defragmentation is rarely required and memory usage remains a small fraction of that required by naive allocation strategies.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · primary corpus · published 2026-08-10T02:28:57Z
Ponkrit Kaewsawee, Chaklam Silpasuwanchai, Chutiporn Anutariya
arXiv categories: cs.AI, cs.CL, cs.DB, cs.LO

Institutional policies stay in natural language while the systems that check compliance demand machine-readable constraints. Bridging that gap is still done by hand. PolicyKG closes the loop. It is an LLM pipeline that reads a policy PDF, classifies each sentence as an obligation, permission, or prohibition, lifts the label into first-order deontic logic, and emits SHACL constraints. Four stages run on a LangGraph state machine with per-stage validators. The piece that matters most is the Corpus Adapter: a YAML vocabulary registry that grounds LLM predicates in a target ontology. Retargeting to a new domain means swapping the registry, not retraining a model. On the Asian Institute of Technology Policies and Procedures corpus (1,663 sentences, 443 rules), PolicyKG reaches 86.9% deontic classification accuracy (Cohen's kappa = .709). Three annotators independently re-label a 50-item sample and agree at Fleiss' kappa = .844. SHACL shape correctness on a 69-shape subset is F1 = .866. The FOL path handles 79.2% of rules; the rest go through a direct NL-to-SHACL fallback. We audited every one of the 443 rules for second- or higher-order constructs. An automated regex checklist flagged none, and a first-author pass on the 92 FOL-fallback cases confirmed the same. The exact upper 95% Clopper-Pearson bound on the true HOL rate is 0.67%. This is an audit finding for one corpus, not a proof of FOL sufficiency for institutional policy. Swapping the AIT registry for a GDPR registry raises exact property alignment from 1/15 to 11/15 (Fisher's exact p < .001; Cohen's h = 1.53). On the LexDeMod lease-contract benchmark (N = 200), Macro F1 drops to .370 because lease English uses "shall be entitled" for permission -- exactly the vocabulary mismatch registry swap is meant to fix. Repeated runs produce hash-identical SHACL outputs.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · cs.SE candidate · published 2026-08-10T03:22:04Z
Xin Zhou, Chun Yong Chong, Kisub Kim, Yun Peng, Rui Shu, Zihan Wu, Xu Han, Guowen Yuan, Zeyang Zhuang, Jounghoon Kim, Jeongjin Ju, Seongmin Ju, Taein Yoon, David Lo
arXiv categories: cs.SE, cs.AI

Large language model-powered coding agents are increasingly used to modify existing code repositories, for example, by adding features or fixing bugs. Yet existing repository-level benchmarks typically evaluate only whether the final patch passes tests. Satisfying a user request requires a long chain of interdependent reasoning and decisions: an agent must recover explicit and implicit requirements, formulate a repository-grounded implementation plan, and translate it into correct code. A pass/fail outcome cannot characterize how an unsuccessful trajectory diverges from the requirements and implementation process needed for a correct patch. To address this gap, we introduce SWE-RPG, a repository-level benchmark that combines executable patch evaluation with validated ground-truth references (GTs) for (1) Requirement Clarification and (2) Implementation Planning. These intermediate GTs support retrospective, GT-aligned diagnosis of complete coding-agent trajectories across clarification, planning, code generation, and artifact submission. SWE-RPG comprises 163 tasks from 31 Python and Java repositories, including 113 bug fixes and 50 feature additions. We evaluate 3 coding agents, including Claude Code, Codex, and OpenCode, with 6 large language model backends, including Claude-Sonnet-5 and GPT-5.6-Terra. Results show that the evaluated popular coding agents still struggle to implement user requests in existing repositories, achieving an average resolved rate of only 31.5% on SWE-RPG. Intermediate-GT diagnosis further identifies implicit requirement recovery as the main bottleneck, accounting for 24.5%--46.0% of agent runs. This result suggests implicit-requirement recovery as a key candidate direction for improving coding agents. The benchmark data and evaluation code are available at https://github.com/Xin-Zhou-smu/SWE-RPG-Bench.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · primary corpus · published 2026-08-10T08:33:18Z
Zenan Li, Ziran Yang, Peiyang Song, Zhaoyu Li, Kaiyu Yang
arXiv categories: cs.AI, cs.PL

Verified code generation asks a large language model (LLM) to generate both an executable program and a machine-checkable proof that the program meets a formal specification, promising software that is correct by construction. The de facto workflow decouples the two halves of the problem: first synthesize a program, then attempt to prove it correct. We observe that this sequential pipeline can be both ineffective and inefficient in practice. A program generated without anticipating its proof can be subtly incorrect or structurally difficult to verify, forcing the LLM into brittle repair loops that alternate between patching the code and patching the proof. Inspired by Dijkstra's view that a program and its correctness argument should be developed hand in hand, we propose $P^3$, an LLM-based agentic workflow that first derives a unified program-and-proof plan from the specification, then elaborates the implementation and proof scaffold under this shared plan. To evaluate verified code generation in realistic settings, we further introduce Lean4Commit0, a repository-derived, library-level benchmark built by extracting core APIs from real-world software repositories and translating their requirements, including relational specifications across APIs, into Lean tasks. Using four frontier LLM backends, we evaluate $P^3$ on Verina, AlgoVeri, and our Lean4Commit0 benchmark, where it achieves the highest solve rate in every benchmark--model setting. Compared with the stronger baseline, it improves solve rates by 4.6--11.2 percentage points and reduces per-task API cost by up to roughly 40\% and wall-clock time by up to roughly 37\% on the difficult subset of each benchmark. A targeted ablation further shows gains of 3.3--8.3 points over implementation-only planning, isolating the benefit of planning the program and proof jointly.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · cs.SE candidate · published 2026-08-10T15:37:09Z
Yunhao Liang, Chengguang Gan, Ruixuan Ying, Hanjun Wei, Zhe Cui, Shiwen Ni
arXiv categories: cs.SE

Large language models (LLMs) can generate functionally useful code that remains vulnerable, while security-focused interventions may break intended behavior. We investigate security tests as executable specifications both before generation and during iterative repair. We develop SecTDD, a controlled test-feedback scaffold that separates three factors: whether tests are shown upfront, whether failed executions trigger revision, and how failures are selected and represented. The evaluation uses behavior-partitioned visible and hidden tests and byte-identical initial candidates for repair comparisons. Across 2,705 trajectories, 31 task instances, three secure-code benchmarks, 16 CWE categories, and two model families, showing all visible tests upfront increases hidden functional-and-security joint success by 19.3 percentage points on average, but improves only seven of nine benchmark-model conditions and harms two. In shared-candidate comparisons, structured feedback repairs 80 initially unsuccessful candidates with no joint regressions; fixed raw feedback repairs 83 but causes three regressions. Structured and raw feedback are otherwise nearly indistinguishable head-to-head (six wins, six losses, and 453 ties). Candidates that pass all visible tests still fail hidden behavior families under every common regime. These results show that executable feedback can repair secure-code generation, but its benefits depend on the model, task, feedback entry point, and especially test coverage.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · cs.SE candidate · published 2026-08-11T20:01:08Z
Yueke Zhang, Zihan Fang, Kevin Leach, Yu Huang
arXiv categories: cs.SE

Code large language models (LLMs) can generate syntactically plausible programs that nevertheless violate hidden semantic constraints. Existing execution-feedback training methods identify whether a completed program fails, but provide limited supervision about how a correct solution should be organized. We introduce GraphAlignCoder, a training framework that transfers explicit correctness structure into code generation. GraphAlignCoder constructs an implementation graph that captures control and dependence among program regions. In parallel, a constrained Lean pipeline produces proof traces, from which we extract a formal proof-flow graph. The model first learns executable code together with graph-derived descriptions of why individual program regions are correct, and then consolidates this knowledge into code generation. GraphAlignCoder consistently outperforms the base model, code-only SFT, and CodeRL across all benchmarks. Compared with CodeRL, it increases the solved count from 38 to 50 on LiveCodeBench v6 and from 16 to 23 on BigCodeBench Hard, corresponding to relative gains of 31.6% and 43.8%, while also improving BigCodeBench Full from 359 to 363 tasks. The ablation study further shows that verification-graph injection produces the initial reasoning gain, while verification to code consolidation is essential for robust cross-benchmark transfer.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · cs.SE candidate · published 2026-08-11T22:14:57Z
Jeremy Spence, Nicholas Assaderaghi, Jinhao Zhu, Nikil Ravi, Raluca Ada Popa, Guannan Wei, Yangruibo Ding, Zhuo Zhang
arXiv categories: cs.CR, cs.AI, cs.SE

AI agents are rapidly improving in cybersecurity capabilities when the source code is available for analysis, yet much of the software most consequential to cybersecurity, including malware, firmware, and proprietary applications, is available only as binaries. Analyzing such software requires reverse engineering(RE): recovering program semantics before the analysis can be meaningfully performed. However, evaluating agentic RE poses a fundamental challenge: benchmark instances must be unseen as source code in the LLMs' training data to prevent models from taking shortcuts by recognizing them rather than really analyzing them, while also matching the scale and anti-analysis protections of real software. Unfortunately, however, existing benchmarks do not jointly satisfy these requirements. To this end, we introduce SRE-Bench, the first realistic, contamination-free RE benchmark. Built entirely from scratch by RE experts with over 5,000 hours, SRE-Bench comprises 19 private, real-world-scale programs averaging 16.9K lines of code. We further developed 44 in-house anti-analysis primitives, yielding 262 binary instances and 1572 deterministically graded tasks. Our evaluation across five frontier LLMs (GPT-5.6-sol,Claude-Opus-5,GPT-5.5,Grok-4.5, and GLM-5.2) shows that RE remains largely unsolved: the strongest model, GPT-5.6-sol, scores 61.4% per instance, and fully solves only 31.5% of the instances. Our analysis further reveals that agents behave differently from human engineers, where agents are relatively insensitive to compiler optimization and static linking. Controlled ablations also confirm that both contamination control and realistic scale are essential. These results indicate that strong source-code security capabilities do not yet transfer to binary analysis, highlighting RE as an important frontier for agentic cybersecurity and SRE-Bench as a rigorous testbed to measure progress.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · cs.SE candidate · published 2026-08-13T10:45:18Z
Fanpeng Yang, Xing Li, Shuling Wang, Jie An, Zeyu Sun, Shenghua Feng, Wenhan Wang, Weiyi Wang, Naijun Zhan, Fanjiang Xu
arXiv categories: cs.SE

Formal verification provides strong guarantees of software correctness, but its adoption is limited by the high cost of writing precise formal specifications. While recent large language models (LLMs) have shown strong capabilities in theorem proving and verified code generation, their true ability to generate program specifications remains unclear. Existing evaluations require either verifying implementation conformance or proving semantic equivalence between specifications, both of which are formidably difficult and may conflate proof difficulty with specification quality. To address this problem, we introduce Coins, a Rocq based evaluation framework that assesses specification quality by instantiating specifications under evaluation on trusted test cases and generating concrete proof obligations. This design aligns with the asymmetric nature of formal reasoning, where successful proofs provide reliable evidence while proof failures are inherently ambiguous. Using Coins, we conduct a large scale study on HumanEval with a curated set of human written Rocq specifications. Our results show that specification generation remains a formidable challenge, and that verification complexity can obscure genuine differences in specification quality. Overall, we find that accurate specification evaluation, rather than model scaling alone, is central to understanding the power of LLMs for specification synthesis, and that test case based formal reasoning offers a more faithful and discriminative measure of progress.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · primary corpus · published 2026-08-13T17:41:27Z
Zhe Ye, Hantao Lou, Yuechun Sun, Peiyang Song, Zhengxu Yan, Timothe Kasriel, Qingyang Zhang, Kaiyu Yang, Soonho Kong, Jingxuan He, Dawn Song
arXiv categories: cs.LG, cs.AI, cs.LO, cs.PL, cs.SE

AI agents are increasingly used for programming, but do not provide any guarantee on the correctness of generated code. Verified code generation, in which an agent produces both an implementation and a machine-checked proof of its specification, offers a stronger path toward trustworthy AI-generated software. Existing benchmarks in this direction either focus on individual functions or only evaluate proof generation with provided implementations. It is still an open question whether agents can make coherent implementation and proof choices across real multi-module codebases. To bridge this gap, we introduce Vero, the first benchmark to evaluate joint implementation and proof synthesis at the repository level. Vero contains 43 multi-module instances sourced from real-world repositories spanning Python, Dafny, Verus, and Coq, and covering diverse domains from cryptographic protocols to distributed systems. Each instance consists of a multi-module Lean 4 repository with predetermined API interfaces, manually curated formal specifications, and reference implementations, supporting both proof-only and code-and-proof evaluation modes. To improve benchmark reliability, Vero also includes an audit mechanism where agents are allowed to formally prove unsatisfiability of provided specification or incorrectness of reference code, which surfaces and corrects latent code and specification errors during curation. We evaluate frontier coding-agent configurations with Lean toolchain access. The strongest agent fully solves only 27 of 43 instances and closes no specifications on the hardest repositories. Vero provides a concrete testbed for measuring progress toward repository-scale verified software synthesis, where current agents still fall short. We release the benchmark, curation pipeline, and evaluation harness at https://github.com/sunblaze-ucb/vero.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · primary corpus · published 2026-08-14T04:58:01Z
James K. Wiles
arXiv categories: cs.AI, cs.CY, cs.LO

How do we govern AI systems whose reasoning we cannot fully inspect? Governance does not require understanding a system's reasoning. It requires stating what the system is obliged, permitted, and forbidden to do, and checking whether it complied. I present an implementation of Reified Input/Output Logic, the formalism behind the DAPRECO knowledge base, in Wolfram Language: the core I/O axioms, obligations, permissions, constitutive norms, reified eventualities, and temporal operators. I then test whether GPT-4 can translate English legal statements into the formalism, and report the failures: hallucinated functions, omitted temporal scope, deviation from the formalism, and (in the worst cases) code that runs, reads plausibly, but silently encodes the wrong norm. A case study, an AI guard dog operating under a computational contract, shows how formalized rules can extend from a contract directly into the operational code of an embodied agent, producing symbolic, auditable justifications for its behaviour. I argue that computational law can be used as a governance tool and that a desirable goal would be to formalize the law that can and ought to be programmatically executable.

arXiv abstract · PDF

LLM reasoning, grounded agents, and AI assurance · cs.SE candidate · published 2026-08-14T14:51:48Z
Ignacio D. Lopez-Miguel, Andreas Happe, Jürgen Cito, Ezio Bartocci, Bettina Könighofer, Martin Tappler
arXiv categories: cs.SE, cs.LG

Large Language Model (LLM)-based agents are increasingly used for complex tasks such as software testing and cybersecurity assessment. While these agents demonstrate impressive capabilities, their behavior is difficult to understand, explain, and analyze. Existing evaluations focus mainly on task success and execution traces, offering limited insight into the strategies employed by the agent. We present ATLAS (Automata Learning for Agent Trajectory Analysis and Strategy Discovery), an approach for recovering interpretable behavioral models from agent trajectories. ATLAS combines trace abstraction with automata learning to infer finite-state models that capture observed agent-environment interaction strategies. These models provide human-interpretable insights and support automated analyses of recurring behaviors, decision points, successful task-completion paths, and failure loops. As a proof of concept, we apply ATLAS to trajectories generated by an LLM-based penetration-testing agent. The resulting models expose high-level behavioral strategies for exploiting vulnerable machines that are difficult to identify from raw execution traces alone. We discuss how learned behavioral models can support explainability, model-guided exploration, auditing, and analysis of agentic systems. We further demonstrate symbolic model-based knowledge transfer from powerful frontier models to compact language models. In addition, we show how model transformations can derive concise explanations of agent behavior in a penetration-testing case study comprising 12 vulnerable machines. ATLAS highlights a new opportunity for model-driven engineering: transforming agent trajectories into explicit behavioral models that enable systematic understanding and analysis of otherwise opaque AI agents.

arXiv abstract · PDF

Automated reasoning, constraints, and proof search · primary corpus · published 2026-08-11T12:58:02Z
Alessandro Bertagnon, Marco Gavanelli
arXiv categories: cs.AI, cs.LO

The Traveling Salesperson Problem (TSP) is one of the best-known problems in computer science and arises in many engineering applications, such as smart vehicles and intelligent transportation systems. In the "Euclidean" case, each node is defined by its coordinates in the plane and distances are computed using the Euclidean metric. In the Constraint Programming (CP) literature, the Euclidean TSP is typically addressed by computing the full distance matrix and treating it as a general case; however this approach ignores the geometric information carried by the points' coordinates. In this work, we propose new filtering algorithms, implemented in Constraint Logic Programming (CLP), that exploit such geometric information to achieve stronger constraint propagation than existing approaches. Moreover, we show how this methodology can be extended to other Euclidean variants of the TSP, including the Euclidean Generalized Traveling Salesperson Problem (EGTSP), which is relevant in practical routing and logistics applications. Experimental results demonstrate the computational advantages of the proposed approach.

arXiv abstract · PDF

Automated reasoning, constraints, and proof search · primary corpus · published 2026-08-13T09:44:51Z
Giorgio Bacci, Giovanni Bacci, Kim G. Larsen, Daniele Toller
arXiv categories: cs.LO

We present global and local algorithms for solving systems of equations over Noetherian posets with a bottom element, a general setting underlying many verification problems. Our algorithms compute the solution of a selected variable by restricting exploration to those parts of the system required to determine its value. We achieve this by computing variable dependencies by means of dependency oracles. Oracles guide the exploration of the system and provide sound termination criteria for local fixed-point computation. A key advantage of our approach is its flexibility: oracles can be customized, composed, or over-approximated, offering a principled way to trade precision for performance without compromising correctness. We evaluate our solution against existing algorithms from the literature and show that our prototype implementation is competitive and often outperforms specialized solutions, while remaining simple and adaptable across diverse application domains.

arXiv abstract · PDF

Automated reasoning, constraints, and proof search · primary corpus · published 2026-08-14T09:06:10Z
Anouk Oudshoorn, Piotr Gorczyca, Dörthe Arndt
arXiv categories: cs.LO, cs.AI

The Shapes Constraint Language (SHACL) is a W3C recommendation to express syntactic constraints, called shapes, on RDF graphs. SHACL validators are used to test whether a given graph adheres to such a shape. However, RDF graphs often come with OWL ontologies, whose implicit knowledge needs to be taken into account. This is classically handled by first applying reasoning and then performing the constraint checking on the results, often using different technologies which makes the process inefficient and vulnerable for mistakes. To overcome this, we propose to internalise the OWL axioms in the SHACL constraints; we construct a rewriting which takes as input both shapes and an OWL EL$^-$ ontology -- a fragment of OWL EL restricting the usage of existential restrictions -- and produces SHACL constraints. This output can then be evaluated by any validator supporting SHACL core regardless of its reasoning support, while yielding the same results as the traditional approach. The implementation of our translation is evaluated both against applying state-of-the-art reasoners and validators consecutively, as against validators with built-in reasoning support. For our benchmark, we show that our approach is in general more efficient in finding violations compared to the sequential approach, thus providing a powerful tool which simplifies combining reasoning with validation.

arXiv abstract · PDF

Automated reasoning, constraints, and proof search · primary corpus · published 2026-08-14T12:56:24Z
Mikoláš Janota, Joao Marques-Silva
arXiv categories: cs.LO

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

arXiv abstract · PDF

Automated reasoning, constraints, and proof search · primary corpus · published 2026-08-14T14:07:20Z
Mikoláš Janota, William Klieber, Joao Marques-Silva, Edmund Clarke
arXiv categories: cs.LO

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

arXiv abstract · PDF

Temporal, probabilistic, and quantitative reasoning · primary corpus · published 2026-08-10T07:00:55Z
Tanel Tammet
arXiv categories: cs.AI, cs.LO

GK is a query-directed first-order prover that extends ordinary resolution-based proof search with explicit positive and negative claims, numerical confidence values, and prioritized default rules with exceptions. It works directly with non-ground clauses, including equality and function terms. Candidate proofs are found by bounded first-order proof search; exception conditions of defaults are checked by further bounded searches, recursively when exceptions themselves depend on defaults. This avoids requiring a finite global grounding, while allowing incomplete searches to be reported as such. This paper adds structure-preserving quantitative reporting to that framework. Retained proof histories are used in two calculations. The first reconstructs the uncertain ground premises used by each proof and computes the probability that at least one retained proof is available, without counting shared premises independently. The second resolves positive and negative support at intermediate atoms before that support is propagated through later rules; the same calculation evaluates uncertain exception conditions for individual rule applications. Reports separate positive support, negative support, conflict, and ignorance and identify detected incomplete calculations or fallbacks. The implementation performs bounded reconstruction and dependency traversal after proof search and still requires no global grounding. Analytic examples and independent simulators reproduce the reference calculations on their stated fragments. Comparisons with probabilistic logic, probabilistic ASP, default logic, and goal-directed ASP identify cases of agreement, semantic difference, unsupported translation, and incomplete computation.

arXiv abstract · PDF

Temporal, probabilistic, and quantitative reasoning · primary corpus · published 2026-08-11T23:23:31Z
Manfred Droste, Guo-Qiang Zhang
arXiv categories: cs.LO

We study the discrete point-based fragment of Ensemble Logic $\EL(\Nat)$ over the natural numbers, a logic combining displacement $\varphi_u$, bounded metric modalities $\boldBox_t$ and $\mdiamond_t$ with additive bounds, Boolean connectives, and first-order quantification over $\Nat$. Motivated by the need for a unified symbolic layer for biomedical knowledge with temporal, spatial, genomic, and multimodal metric content, we develop the foundational discrete theory of the formalism. We give syntax and semantics, and prove a forward embedding of $\EL(\Nat)$ over a finite proposition set $\mathcal{P}$ into first-order monadic Presburger arithmetic $\FO(\Nat,<,+;\mathcal{P})$. This embedding yields the analytical upper bounds, while a reduction from nondeterministic two-counter machines with recurring control states proves that satisfiability is $Σ^1_1$-complete and validity is dually $Π^1_1$-complete. Expressively, $\EL(\Nat)$ strictly extends the star-free $ω$-languages and is incomparable with the $ω$-regular languages: it defines the non-$ω$-regular counting language $\{a^mb^mc^md^m\mid m\geq 1\}\cdotΣ^ω$, whereas a delimited parity language remains outside the logic by classical Presburger-arithmetic lower bounds. On the proof-theoretic side, we present a sound Hilbert system $\HEL$ and establish completeness relative to monadic Presburger validity as oracle, noting that completeness relative to plain Presburger arithmetic is impossible.

arXiv abstract · PDF

Temporal, probabilistic, and quantitative reasoning · primary corpus · published 2026-08-13T14:06:58Z
Lena Verscht, Hannah Mertens, Kevin Batz, Sebastian Junges, Benjamin Lucien Kaminski, Joost-Pieter Katoen
arXiv categories: cs.PL, cs.LO

Probabilistic programs with nondeterminism model planning problems in which a strategy resolves the nondeterminism to optimize an expected outcome. We study the multiobjective setting, optimizing several outcomes at once along a Pareto front, and provide a deductive, program-level account of strategy synthesis. Its core is a multiobjective preexpectation transformer mapping a tuple of postexpectations to the set of simultaneously achievable values, an element of the convex Hoare powerdomain. It conservatively extends weakest preexpectations and lifts standard loop rules. We develop rules to synthesize witnessing strategies as mixed determinizations that randomize over non-probabilistic determinizations. We prove the transformer and synthesis rules sound against an operational MDP semantics, without requiring a finite state space: our approach can be seen as a symbolic approach - at program level - for multiobjective optimization over infinite MDPs. We demonstrate our machinery using various case studies.

arXiv abstract · PDF

Temporal, probabilistic, and quantitative reasoning · primary corpus · published 2026-08-13T17:15:09Z
Charles Koll, Houssam Abbas
arXiv categories: cs.LO

We give the first theoretical characterization, and the first algorithm, for continuous monitoring of a distributed Cyber-Physical System (CPS) against a dense-time temporal logic specification. A distributed CPS is composed of multiple agents, each with a local clock; these clocks drift from each other, so there is no well-defined global time. When monitoring such a system's output signal against a temporal logic specification, it is not evident how to interpret the temporal constraints of the formula, and what satisfaction means. Yet CPS designers, like control engineers, typically think of their system's operation in terms of global time. Most existing techniques for monitoring distributed systems work with discrete-time specifications not suitable for CPS, and/or require an explicit mapping of temporal constraints to local clocks. We introduce an algorithm that addresses the above challenges for a fragment of Signal Temporal Logic (STL) that still includes all temporal operators. It relies on a novel extension of satisfaction signals to this partially synchronous setting (where clocks drift), and an analysis of the geometry of multi-dimensional partially synchronous time. The algorithm returns the set of all possible global moments that can satisfy the specification. Knowledge of these possible global moments is important for debugging distributed hybrid control systems such as fleets of drones and electrical grids. We derive the worst-case complexity of the algorithm, and implement a sound approximation of it that experimentally illustrates effective monitoring, even in scenarios of up to 50 agents.

arXiv abstract · PDF

Modal, intuitionistic, and proof-theoretic logic · primary corpus · published 2026-08-10T22:31:52Z
Mario Piazza
arXiv categories: cs.LO

We prove decidability of Simpson's intuitionistic modal logic IK$ by working directly with cut-free nested proofs. Once the end formula is fixed, only finitely many combinations of input and output formulae can occur at a node, although the modal tree itself remains unbounded. We order these nested sequents by rooted homeomorphic embedding: weakening may add input formulae, while transitivity allows a modal edge to be stretched into a non-empty path. Kruskal's theorem makes rooted homeomorphic embedding a well-quasi-order, but does not by itself make backward application of the rules effective: an inference may still occur inside an arbitrarily large context. The finite-support lemma shows that a minimal predecessor need retain only the positions used by the inference, the images of the chosen basis elements, and the branch points joining them. Together with an effective enumeration of bounded rule instances, this bound makes the minimal predecessors computable. Backward closure from the initial sequents gives an increasing sequence of finitely based upward-closed sets. The sequence eventually stabilises, and its stable value is the set of provable nested sequents. At that point, finitely many cut-free proofs suffice: every other provable nested sequent is obtained from one of them by weakening along an embedding. Their maximum height gives a uniform proof-height bound.

arXiv abstract · PDF

Modal, intuitionistic, and proof-theoretic logic · primary corpus · published 2026-08-11T14:03:51Z
Sergio Celani, Paula Menchón, Valeria Miguelez
arXiv categories: math.LO

Kleene triples, introduced by Jalali, provide a representation of arbitrary Kleene algebras in terms of twist-products. We introduce modal Kleene algebras and modal Kleene triples, and establish a categorical equivalence between the corresponding categories, extending Jalali's duality to the modal setting. We study the centered case and show that Kleene algebras with implication can be naturally described within this framework by viewing implication as a family of modal operators. Finally, we develop a topological duality for modal Kleene triples.

arXiv abstract · PDF

Modal, intuitionistic, and proof-theoretic logic · primary corpus · published 2026-08-12T11:15:06Z
Steffen van Bakel, David Davies
arXiv categories: cs.LO

We define call-by-name and call-by-value reduction and reduction strategies for the calculi slmu (symmetric lmu), lmmt, and Xs (X with implicit substitution). We establish a strong relation between these notions through defining a single interpretation from slmu to lmmt that respects normal reduction, as well as the call-by-name and call-by-value reduction in slmu within the their counterpart in lmmt; for the strategies, we will show similar, but weaker results. We also define a single mapping from lmmt to Xs, and show that this also respects all three notions. We then continue with studying the natural encoding of Xs into lmmt, and show that only full reduction is respected, but that reduction steps are needed to model substitution, so the CBN and CBV strategies cannot be respected. We conclude with studying the combination of our efforts and define an interpretation of slmu into Xs, and show that CBN and CBV reduction are respected. This result underlines that Xs and lmmt are similar, but different calculi, and that the nature of slmu makes that any encoding into either can never fully respect the strategies.

arXiv abstract · PDF

Modal, intuitionistic, and proof-theoretic logic · primary corpus · published 2026-08-13T14:34:20Z
Xiaohong Chen, Grigore Rosu
arXiv categories: cs.LO

Basic matching logic is matching logic without definedness. Symbols are interpreted as set-valued operations, element variables denote singletons and are bound by $\exists$, and no connective uniformly internalizes totality. For basic matching logic without fixpoints over an arbitrary one-sorted finitary signature, we prove \emph{global completeness} ($Γ\vDash\varphi$ iff $Γ\vdash\varphi$, for arbitrary, possibly infinite $Γ$) and, as a corollary, conservativity of the definedness extension. The proof localizes $Γ$ to a theory $Δ_Γ$ and reduces semantic consequence and derivability to the same local relation: $Γ\vDash\varphi$ iff $Δ_Γ\vDash_\text{loc}\varphi$ iff $Γ\vdash\varphi$. A double-cover construction establishes the semantic equivalence. Least fixpoints destroy effective axiomatizability. Over a signature with one unary and two binary symbols and no constants, validity is not recursively enumerable; hence no sound calculus with a recursively enumerable proof relation is even weakly complete, already for the empty theory and without definedness. The positive result is also sharp in the number of sorts. Global completeness fails with three sorts for a satisfiable $Γ$. Thus the completeness conjecture holds for one sort and fails in general. The negative results arise from sort flow, fixpoint effectivity, and, for hybrid logic, an obstruction to every well-founded calculus whose leaves are hypotheses or valid patterns and whose rules respect localization. This yields a matching-logic-independent dichotomy: the language with state variables bound by $\exists$ and $\forall$ over modalities of arbitrary arity is globally complete without nominals, while no calculus in that well-founded class is globally complete once nominals are added.

arXiv abstract · PDF

Modal, intuitionistic, and proof-theoretic logic · primary corpus · published 2026-08-13T20:39:20Z
Philip Sink
arXiv categories: cs.LO, math.LO

This paper will give a definition of belief revision within simplicial semantics. Starting from the work presented in "A Semantics for Belief in Simplicial Complexes" as a baseline, this paper modifies the semantics for belief given there to allow atomic formulae to be assigned to nodes, not facets. Conceptually and philosophically, this version of the semantics is better suited if one wishes to interpret the nodes of a simplicial model of epistemic logic as a "perspective" assigned to a particular agent. If nodes are perspectives, it then follows that worlds, or the facets of a simplicial model, are composed themselves of perspectives. This allows us to say that two worlds are more similar, or "nearer", if they share more perspectives. With this conceptual notion of nearness in hand, two different formal presentations of revision are given. We conclude by exploring some conceptual pitfalls surrounding these definitions under iterated revision, and motivate a few potential solutions that involve giving the agents a "memory" of what has been announced so far.

arXiv abstract · PDF

Modal, intuitionistic, and proof-theoretic logic · primary corpus · published 2026-08-14T09:20:35Z
Safa Zouari, Rob van Glabbeek, Krzysztof Ziemiański
arXiv categories: cs.LO

Higher-Dimensional Automata (HDAs) provide a geometric model of true concurrency. While hereditary history-preserving (hhp) bisimilarity is the finest behavioural equivalence in van Glabbeek's spectrum, no modal logic has previously characterised it on HDAs. We introduce several new intermediate equivalences that sit strictly between ST- and hhp-bisimilarity. We show how separating similarity and subsumption of paths leads to a clean formulation of these equivalences, and we present a modal logic that characterises hhp-bisimilarity. Natural fragments characterise ST-bisimilarity and the intermediate notions.

arXiv abstract · PDF

Modal, intuitionistic, and proof-theoretic logic · primary corpus · published 2026-08-14T13:28:37Z
Kenji Tokuo
arXiv categories: math.LO, cs.LO

This paper presents a first-order multimodal logic programming system called MMLP. The system accepts arbitrary formulas as both programs and queries, without restricting either side to Horn clauses or a separate goal grammar. Its declarative semantics is given independently by a Hilbert system for selected D, T, I, B, 4, and 5 modal principles. Execution uses a nested proof calculus with finite grammar certificates for modal propagation. Certificate reachability is equivalent to the associated Horn closure, certificate existence is decidable, and the calculus is cut-free complete. For quantified answer computation, we give a unification algorithm based on permission sets that controls eigenparameter scope. The algorithm always terminates and fails exactly when no admissible solution exists. A successful run returns a unifier that is itself admissible and through which all admissible solutions factor. Computed answers are declaratively correct, and each declaratively correct answer is an ordinary output instance of a computed answer. In proof search, MMLP admits syntactic focalization and a fair and complete enumeration of focused answers. It represents exactly the same answer substitutions as Nguyen's pure logical KDI4s5-MPROLOG on their common fragment, while admitting a strictly larger program and query language.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-11T12:54:21Z
Jan Tóth, Qipeng Kuang, Kuncheng Zou, Václav Kůla, Yuyi Wang, Yuanhong Wang, Ondřej Kuželka
arXiv categories: cs.LO

The Weighted First-Order Model Counting Problem (WFOMC) asks for the weighted sum of models of a first-order logical sentence over a domain. It is a fundamental problem in statistical relational learning, with applications extending to enumerative combinatorics and graph polynomials. Computing WFOMC for the three-variable fragment is $\mathsf{\#P}_1$-hard, whereas polynomial-time algorithms exist for the two-variable fragment and its extensions by cardinality constraints and counting quantifiers. In this work, we explore computing WFOMC in polynomial time over linearly ordered domains, enabling tractable reasoning across inference scenarios and combinatorial problems involving sequences. Because encoding a linear order in standard first-order logic requires three variables, negating our polynomial-time aspirations, we add a linear order axiom directly to the language. This forces one predicate to impose a total ordering on domain elements. We first prove that WFOMC with the linear order axiom can be solved in time polynomial in the domain size. We then extend this result to ordered domains with access to successor relations. While this holds when successors are explicitly defined via the linear order, we demonstrate an alternative implicit approach where successor relations are part of the axiom. This implicit method exhibits significantly better performance on all tested instances, sometimes providing exponential runtime improvements. Finally, we analyze scenarios with two distinct linear orders. We show that WFOMC over the two-variable fragment with two linear orders is $\mathsf{\#P}_1$-hard. However, we develop a polynomial-time algorithm for WFOMC with one linear order and a successor relation of another, pushing the intractability barrier further, yet still leaving the question of how close to a second full linear order one can get.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-12T16:01:25Z
Jakub Rydval
arXiv categories: cs.LO, math.LO

We study the amalgamation decision problem: given a universal first-order sentence $Φ$, decide whether the class $\mathrm{fm}(Φ)$ of its finite models has the amalgamation property. We call $Φ$ semantic Horn if $\mathrm{fm}(Φ)$ is closed under binary direct products. By McKinsey's theorem, this is equivalent to $Φ$ being logically equivalent to a universal Horn sentence; the distinction is one of input representation, since $Φ$ itself need not be given in Horn form and conversion to an explicit Horn normal form can incur an exponential blow-up. We prove that the problem is decidable under this semantic promise. Moreover, it belongs to 2EXPTIME, and to EXPTIME for every fixed bound on the arity of the input signature. Thus the semantic Horn fragment admits an unconditional decision procedure for signatures of unbounded relational arity. Our proof starts from the inside-out correspondence, which we use as a black box for the semantic reduction to a finite completion problem. We encode finite completions as homomorphisms to a finite relational template and introduce a finite set-valued local-consistency certificate for completion problems whose template has bounded width. For semantic Horn inputs, the local completions over each fixed source chart are closed under relationwise intersection of the added relations, and these intersections are compatible with restriction maps. This yields a semilattice polymorphism of the completion template. Since the template is binary, the semilattice operation gives width $2$, making the local-consistency certificate complete. The same construction gives a decision procedure whenever the associated completion template has bounded width.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-12T21:59:58Z
Pablo Barceló, Floris Geerts, Matthias Lanzinger, Klara Pakhomenko, Jan Van den Bussche
arXiv categories: cs.LG, cs.LO

We prove that, on finite simple undirected graphs equipped with a single Boolean node feature, the Boolean queries expressible in $Σ$-MPLang, for any collection $Σ$ of eventually constant activation functions and with arbitrary real coefficients, form a strict subclass of the Boolean queries expressible in ReLU-MPLang. We thereby settle a recently posed open problem: whether ReLU-MPLang is more powerful than trReLU-MPLang when it comes to Boolean queries. In particular, this implies that ReLU-GNNs are strictly more expressive than {TrReLU,id}-GNNs with respect to Boolean queries on Boolean-featured graphs.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-12T22:34:05Z
Jonathan Feigert, Daniel Herden, Marcos Mazari-Armida
arXiv categories: math.LO, math.GR

We study the abstract elementary class of acts with pure embeddings. In particular, we show that stability and superstability in this class can be characterized in terms of the monoid $S$ being LO (for every $s,t \in S$, we have that $s \in St$ or $t \in Ss$) and weakly noetherian (every ideal is finitely generated), respectively. Moreover, under mild set-theoretic assumptions, we characterize the stability spectrum via the minimal cardinality of a generating set for every ideal. As an application, we obtain a Baer-like criterion for pure injective acts when $S$ is LO. We use this to provide an alternative proof that the class of acts has enough pure injectives when $S$ is LO.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-13T14:25:31Z
Artem Chernikov
arXiv categories: math.LO

The classes of SOP$_2$ and SOP$_3$ first-order theories coincide. This answers a question of Džamonja and Shelah from 2004.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-13T15:41:58Z
Radu Curticapean, Daniel Neuen, Amir Nikabadi, Tim Seppelt, Ben Young
arXiv categories: cs.LO, cs.CC, math.CO

Two graphs $G$ and $H$ are homomorphism indistinguishable over a graph class $\mathcal{F}$ if they admit the same number of homomorphisms from every graph in $\mathcal{F}$. A wide range of relaxations of graph isomorphism arise this way: isomorphism itself over the class of all graphs [Lovász, Acta Math. Hung. 1967], equivalence under the $k$-dimensional Weisfeiler-Leman algorithm over the graphs of treewidth $\leq k$ [Dvořák, J. Graph Theory 2010], and quantum isomorphism over planar graphs [Mančinska-Roberson, FOCS 2020]. Since the class $\mathcal{F}$ is typically infinite, it is not clear a priori whether homomorphism indistinguishability over $\mathcal{F}$ is decidable; for planar graphs it is undecidable. Every class for which decidability was previously known is sparse. We give the first decidability results for dense graph classes: We introduce the dense Weisfeiler-Leman algorithm that decides homomorphism indistinguishability over the class of graphs of cliquewidth $\leq k$, the dense counterpart of treewidth. This relation was not previously known to be decidable. The algorithm colors $k$-tuples of vertex subsets rather than $k$-tuples of vertices. Beyond the class of all graphs of cliquewidth $\leq k$, we prove a general meta-theorem: homomorphism indistinguishability over every $\mathsf{CMSO}_1$-definable graph class of bounded cliquewidth is decidable, in randomized exponential time. For classes of bounded linear cliquewidth the bound improves to $\mathsf{PSPACE}$, and we show this is tight by exhibiting such a class for which the problem is $\mathsf{PSPACE}$-complete. These are the first general algorithms for homomorphism indistinguishability over dense graph classes.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-13T18:00:20Z
Owen Ngo Hang Chan
arXiv categories: math.LO, math.CT

Given a complete first-order theory $T$, we characterise elimination of hyperimaginaries in $T$ in terms of the exactness of the pro-completion $\textrm{Pro}(\textrm{def}(T))$ of the syntactic category $\textrm{def}(T)$ of $T$, thus extending Makkai's result connecting elimination of imaginaries with the exactness of $\textrm{def}(T)$. Likewise, we characterise the heq construction in terms of the exact completion of $\textrm{Pro}(\textrm{def}(T))$.

arXiv abstract · PDF

Model theory, finite structures, and definability · primary corpus · published 2026-08-14T07:24:47Z
Xiaoduo Wang
arXiv categories: math.LO

We study Hausdorff limits of definable families over arbitrary models of o-minimal expansions of real closed fields. Over the real field, van den Dries proved that Hausdorff limits of definable families are definable, giving a geometric interpretation of the Marker--Steinhorn theorem. We prove a non-Archimedean analogue for definable families which are Lipschitz cells with a fixed cell presentation and a uniform Lipschitz bound. The proof replaces compactness of closed and bounded subsets of $\mathbb R^n$ by dense completions and long Cauchy sequences, and treats the Hausdorff distance as a metric valued in an ordered completion. We show that Hausdorff limits of such families are standard parts of external fibers over tame extensions, and use stable embeddedness of tame pairs to prove that every such limit is definable in the dense completion of the base model. We also prove a uniform version: the collection of these Hausdorff limits forms a definable family in the dense completion.

arXiv abstract · PDF

Set theory, computability, and mathematical foundations · primary corpus · published 2026-08-13T07:13:06Z
Naoya Kato
arXiv categories: math.LO

$\mathrm{PA}_{\mathrm{smu}}^{-}$ is a weak theory of arithmetic obtained by adding two principles concerning powers of two to basic axioms satisfied by the nonnegative part of a discretely ordered ring. We introduce a theory $\mathrm{PA}_{\mathrm{wit}}^{-}$ in which powers of two and the required witnesses are represented by primitive symbols. We show that, along a fixed sequence in the standard model of arithmetic, every one-variable term eventually agrees with a polynomial over the dyadic rationals. A finite avoidance lemma and the Compactness Theorem then yield a model of $\mathrm{PA}_{\mathrm{smu}}^{-}$ in which division by $3$ fails. In this model even the $n=3$ instance of the Standard Euclidean Division Principle pa16 fails. In fact, the model can be chosen to satisfy every universal $\mathcal{L}_0$-sentence true in the standard model. Consequently, neither pa16 nor the Euclidean Division Principle pa17 is derivable even after these universal truths are adjoined to $\mathrm{PA}_{\mathrm{smu}}^{-}$.

arXiv abstract · PDF

Set theory, computability, and mathematical foundations · primary corpus · published 2026-08-13T13:16:23Z
Mohammad Golshani
arXiv categories: math.LO

Starting with CH and Hajnal's coloring, we show that a standard finite-support iteration of $σ$-centered forcing notions gives a model of $ MA_{ω_1}(σ$-centered$)+2^{\aleph_0}=\aleph_2 +ω_1^2\nrightarrow(ω_1^2,3)^2.$ We also isolate a simple forcing-preservation principle: the same ground-model coloring remains a witness after forcing with any poset whose subfamilies of size at most $ω_1$ are countable unions of linked sets. Under $\text{MA}_{ω_1}$, every c.c.c. forcing has this local property, so every existing witness is preserved by every c.c.c. forcing over that model.

arXiv abstract · PDF

Set theory, computability, and mathematical foundations · primary corpus · published 2026-08-14T03:09:39Z
Ulvi Yurtsever
arXiv categories: math.LO

The Hardin-Taylor theorem, a consequence of the axiom of choice, gives a strategy to predict future values of an arbitrary function of time $f:\mathbb{R}\to S$ given its past values. The times in $\mathbb{R}$ at which the strategy fails are shown to form a countable nowhere dense set for any function $f$. The theorem is often presented as a striking result about predicting the future. In this note we discuss the operational content of the theorem and clarify this frequent interpretation. The Hardin--Taylor prediction strategy is online: at time $t$ it depends only on the observed past $f\upharpoonright(-\infty,t)$. Its performance guarantee, however, is offline: the exceptional set consisting of times at which the predictor fails is defined only after the entire function has been realized. We spell out the precise definition of the predictor, discuss a simple two-function example as a sanity check, and emphasize the retrospective nature of verifying the predictor's success. We also examine the proper probabilistic setting in which the success likelihood of the predictor as a forecasting procedure should be evaluated. Our conclusion is that the theorem is best understood as a result about the smallness of the set of times at which the predictor must be course-corrected, rather than as a prospectively verifiable procedure for forecasting the future.

arXiv abstract · PDF

Set theory, computability, and mathematical foundations · primary corpus · published 2026-08-14T17:03:45Z
Tyler Arant
arXiv categories: math.LO

For a real $f\in \mathbb{N}^\mathbb{N}$, it is in general not the case that every set which is both $Σ^1_1(f)$ and $Π^1_1(f)$ is the $f$-section of a $Δ^1_1$ set. However, there are reals $f$ for which this, in fact, does happen; we say that such a real strongly relativizes $Δ^1_1$. In this paper, we will prove that the reals which strongly relativize $Δ^1_1$ are exactly the hyperlow reals, i.e., the $f\in \mathbb{N}^\mathbb{N}$ with $ω_1^f=ω_1^{\text{ck}}$. We will also study reals that strongly relativize the classes $Δ^0_α$ for $1\leq α<ω_1^{\text{ck}}$. We characterize the reals that strongly relativize $Δ^0_1$ subsets of $\mathbb{N}$ as the reals which are computably dominated. For $1\leq α<ω_1^{\text{ck}}$, we show that there are continuum many reals which strongly relativize $Δ^0_α$ subsets of $\mathbb{N}$. We will also find non-trivial examples of reals which strongly relativize $Δ^0_α$ ($1\leq α<ω_1^{\text{ck}}$) subsets of Baire space.

arXiv abstract · PDF

Higher categories, homotopy, and categorical topology · primary corpus · published 2026-08-10T13:26:11Z
Dipankar Maity
arXiv categories: math.AG, math.AT, math.CT

We develop a general $\infty$-categorical framework for internal Eilenberg-MacLane objects, internal homotopy groups, and an internal notion of covering spaces, and study their behavior under suitable localizations. Applying this to the ordinary motivic localization, we identify internal $n$-Eilenberg-MacLane objects with strongly $\mathbb{A}^1$-invariant sheaves of (abelian when $n\geq 2$) groups, yielding a formal obstruction to the motivic homotopy category being an $\infty$-topos. We prove that taking $\mathbb{A}^1$-localizations induces an equivalence between classical $\mathbb{A}^1$-coverings of a Nisnevich local space and the internal motivic coverings of its motivic localization, providing a streamlined proof of a generalized motivic Van Kampen theorem. Along the way, we establish a Nisnevich-local-to-global $\mathbb{A}^1$-connectivity criterion: a $k$-scheme is $\mathbb{A}^1$-connected if and only if it admits a Nisnevich cover by $\mathbb{A}^1$-connected schemes such that each pairwise intersection has a ($k$-)point. Finally, we show that over a general Qcqs base, passing to the birational motivic homotopy category recovers certain essential topos-theoretic properties absent in the ordinary $\mathbb{A}^1$-setting. In fact, for a scheme with finitely many generic points, we show that the birational motivic homotopy category is a Postnikov-complete $\infty$-topos of cohomological dimension $0$.

arXiv abstract · PDF

Higher categories, homotopy, and categorical topology · primary corpus · published 2026-08-11T09:03:47Z
Maxime Ramzi
arXiv categories: math.KT, math.AT, math.CT

We prove that the $\infty$-category of localizing motives in the sense of Blumberg--Gepner--Tabuada is not compactly generated, extending a result of Efimov.

arXiv abstract · PDF

Higher categories, homotopy, and categorical topology · primary corpus · published 2026-08-11T19:07:34Z
Giovanni Ferrer, Brett Hungar, David Penneys, Greyson Wesley
arXiv categories: math.QA, math.CT

In our previous article [arxiv:2410.05120], we introduced the notion of a finite dimensional 3-Hilbert space, categorifying Baez's 2-Hilbert spaces. In this article, by further categorifying Baez's higher linear algebra, we provide useful tools for working with 3-Hilbert spaces, including, generalized scalar multiplication, orthonormal bases, and unitary adjoints for operators. We use these tools to endow the $\mathrm{C}^*$-3-category of 3-Hilbert spaces with a self-enrichment. We prove a Unitary Yoneda Lemma/Riesz Representation Theorem for 3-Hilbert spaces: the Yoneda embedding is an isometric equivalence. Finally, we define a unitary version of the Deligne product on 3-Hilbert spaces and prove that it satisfies an isometric version of the folding trick.

arXiv abstract · PDF

Higher categories, homotopy, and categorical topology · primary corpus · published 2026-08-12T13:21:50Z
Slava Pimenov, Angel Toledo
arXiv categories: math.CT, math.AG

Recently Batanin and Markl developed a theory of Koszul duality for operads over a general operadic category in the spirit of Ginzburg-Kapranov. However, their approach doesn't apply directly to the operadic category of n-trees, which are used to describe categorical structures. In this paper we present a category of (locally constant) 2-nets which addresses the main difficulty of extending their theory to the case of 2-trees. Specifically, our category of 2-nets is an operadic category containing 2-trees as a full subcategory, and every map between 2-nets admits a factorization into a chain of elementary maps.

arXiv abstract · PDF

Higher categories, homotopy, and categorical topology · primary corpus · published 2026-08-13T12:20:49Z
Philippe Gaucher
arXiv categories: math.CT, math.AT

We prove that the q-model category of $\mathcal P$-multipointed d-spaces for $\mathcal P\in\{\mathcal G,\mathcal M\}$ is not left proper by constructing a weak equivalence whose pushout along a q-cofibration obtained by attaching a single 1-dimensional globular cell is not a weak equivalence. The counterexample is constructed in the category of $Δ$-Hausdorff $Δ$-generated spaces. For $\mathcal P=\mathcal G$, all objects are automatically saturated, and for $\mathcal P=\mathcal M$, the original weak equivalence is between saturated objects. The failure is caused by a family of nonconstant execution paths that converges in the ambient mapping space to a constant map which is not an execution path; after the globular cell is attached, this degeneration causes two previously distinct path components to merge.

arXiv abstract · PDF

Higher categories, homotopy, and categorical topology · primary corpus · published 2026-08-13T12:28:58Z
Philippe Gaucher
arXiv categories: math.CT, math.AT

We introduce the notion of a reparametrization category with cuts. For every such reparametrization category $\mathcal P$, we prove the tensor lemma, namely that the tensor product of two objectwise weak homotopy equivalences of $\mathcal P$-spaces is a weak equivalence, and then the left properness of the q-model structure of $\mathcal P$-flows. Finally, we prove that the interval reparametrization categories $\mathcal G$, $\mathcal M$, as well as the final category $\mathbf 1$, have cuts. The last example recovers the left properness of the q-model structure of ordinary flows.

arXiv abstract · PDF

Category theory and higher algebra · primary corpus · published 2026-08-10T07:11:29Z
Kevin Coulembier, Jensen O'Sullivan, Daniel Tubbenhauer
arXiv categories: math.RT, math.CT

This paper studies the asymptotic growth of tensor powers in affine Hecke categories, or equivalently of powers of Kazhdan--Lusztig basis elements in affine Hecke algebras. We prove general bounds in arbitrary affine type, determine precise asymptotics in affine type A1, and establish corresponding results for several natural families in affine type A2.

arXiv abstract · PDF

Category theory and higher algebra · primary corpus · published 2026-08-10T10:55:34Z
Stefano Ambra, Andrea Montoli, Diana Rodelo
arXiv categories: math.CT

We introduce the notion of R-full Schreier internal category, which is the monoid analogue of the notion of aspherical abelian groupoid. We associate with every R-full Schreier internal category a direction, which is a Schreier split extension with commutative and cancellative kernel. We show that this association is functorial and that such functor is a product preserving cofibration. Thanks to these properties, we equip the connected components of the fibres of such functor with canonical commutative monoid structures. Using the equivalence between Schreier internal categories and crossed semimodules of monoids, we describe these commutative monoids in terms of crossed Schreier extensions.

arXiv abstract · PDF

Category theory and higher algebra · primary corpus · published 2026-08-10T16:05:07Z
Xiao-Wu Chen, Jian Liu, Xue-Song Lu, Chencheng Zhang
arXiv categories: math.CT, math.AG, math.RT

In this article, we construct an explicit pre-triangulated category which is not a triangulated category. Its underlying additive category is the category of finitely generated projective modules of the type-$A_5$ preprojective algebra over $\mathbb F_2$, and the suspension is induced by the graph-reflection automorphism.

arXiv abstract · PDF

Category theory and higher algebra · primary corpus · published 2026-08-10T21:42:30Z
Federico Campanini, Carmelo Antonio Finocchiaro
arXiv categories: math.CT, math.RA

We study natural topologies on spaces of subobjects of a fixed object in a suitable category, with the aim of determining when these spaces are spectral. A central step in our approach, which is also of independent interest, is the comparison between the categorical notion of a $λ$-generated object and the order-theoretic notion of a $λ$-compact element in a lattice of subobjects. We prove that these notions coincide under some natural and mild assumptions . In the finitary case, this allows us to describe the finitely generated subobjects purely in order-theoretic terms and to construct, inside each interval of a subobject lattice, a canonical algebraic core. We study this construction abstractly for complete lattices and characterize it by a universal property. We then introduce the categorical Zariski topology on spaces of subobjects, relate it to the Scott topology, and obtain spectrality criteria for the whole subobject space and for its algebraic core.

arXiv abstract · PDF

Category theory and higher algebra · primary corpus · published 2026-08-11T07:14:34Z
Joseph Newton
arXiv categories: math.RT, math.CT

This paper studies simple Lie algebras in the Verlinde category, with canonical fundamental group action, using combinatorial methods. We give an exhaustive list of such Lie algebras which either have length at most 3, or appear as a subalgebra of the restriction of the Lie algebra of a simple algebraic group along a principal morphism. The results and exceptions answer several questions and conjectures regarding Verlinde categories of algebraic groups and their Lie algebras.

arXiv abstract · PDF

Category theory and higher algebra · primary corpus · published 2026-08-11T07:58:38Z
Alessandro Linzi
arXiv categories: math.CT

Nakamura--Reyes showed that the category of commutative mosaics---unital reversible hypermagmas, without associativity---is complete, cocomplete, and has free objects, in contrast to commutative polygroups. Krasner's multivalued addition is designed around ultrametric balls; we take that valuation-theoretic motivation as primary and equip mosaics with valuations, as unit-reflecting unitary morphisms into the tropical polygroup $T(Γ)$. Value-preserving morphisms form the slice over $T(Γ)$, which is complete and cocomplete. The larger lax category of valued mosaics over a fixed ordered abelian group $Γ$ is finitely complete and has all small coproducts; it recovers the category of commutative mosaics for the trivial value group, while lax coequalizers for nontrivial $Γ$ remain open. Associativity is analysed via factor nesting, which implies it under totality and characterises it among total product-ultrametric mosaics such as the Krasner hyperfield and $T(Γ)$, yet is strictly weaker without totality. Among total valued mosaics satisfying factor nesting, the Krasner ball axiom yields associativity and upgrades the weak valuation so that sums are ultrametric balls and the superiorly canonical package follows.

arXiv abstract · PDF

Category theory and higher algebra · primary corpus · published 2026-08-11T18:00:05Z
Gregory W. Moore, Eliezer Rabinovici, Ranveer Kumar Singh
arXiv categories: hep-th, math.CT, math.QA

Given a Lie group $G$, a level $k$, and a Lie subgroup $H$ one can construct 2d conformal field theories by either 1.) gauging a nonanomalous $H$ symmetry of the WZW model constructed from $(G,k)$ or 2.) using an algebraic procedure known as the GKO coset construction. The two models are closely related, but not precisely the same: The gauged WZW model is identified with the corresponding GKO model coupled to a 2d topological field theory. The topological theory is characterized by a commutative Frobenius algebra derived from the endomorphisms of an algebra object in a modular tensor category constructed from $(G,H,k)$. The partition function on the torus of the two models differ by a factor of the dimension of this algebra of endomorphisms. Concrete examples are constructed and some applications to string theory and 2d Yang-Mills coupled to nonanomalous matter are briefly discussed. This paper is a summary of a longer companion paper.

arXiv abstract · PDF

Category theory and higher algebra · primary corpus · published 2026-08-12T11:13:51Z
Maxim Ivanov
arXiv categories: math.GR, math.AT, math.CT

We introduce $C$-lifting functors, which axiomatize lifting properties of non-abelian tensor and exterior products with respect to prescribed classes of group extensions. For a homomorphism $f\colonΓ\to G$, we associate to every $C$-lifting functor $F$ a relative quotient $F_f(G)$. This quotient maps epimorphically onto the subgroup determined by $F$ in every $f$-extension belonging to $C$. We show that the construction is functorial in $f$ and that, for an $f$-extension $p\colon\widetilde G\to G$, it gives a morphism of natural exact sequences. In degree two this yields an epimorphism $ \frac{H_2(G;\mathbb Z)}{f_*H_2(Γ;\mathbb Z)} \longrightarrow \ker p\cap[\widetilde G,\widetilde G]. $ Applying the construction to iterated tensor and exterior powers, we obtain relative Schur-Baer theorems for the lower central and derived series. We also compare the relative tensor and exterior squares, relate the exterior construction to the relative Schur multiplier $H_2(G,Γ;\mathbb Z)$, and derive applications to orderability. As a consequence, we prove that a virtual knot group is left-orderable if and only if it is circularly orderable.

arXiv abstract · PDF

Category theory and higher algebra · primary corpus · published 2026-08-12T14:20:02Z
Arend Rensink, Andrea Corradini
arXiv categories: cs.LO

Nested conditions are used, among other things, as a graphical way to express first order formulas ruling the applicability of a graph transformation rule to a given match. In this paper, we first introduce several operators on conditions mimicking logical connectives. Next we propose an original notion of structural morphism among nested conditions, and we identify circumstances under which morphisms are consistent with the entailment of the corresponding conditions. Finally we frame the results in a categorical context, proving functoriality and universality properties of the various operations.

arXiv abstract · PDF

Category theory and higher algebra · primary corpus · published 2026-08-13T18:38:38Z
Martino Lupini
arXiv categories: math.CT, math.GN, math.GR, math.KT, math.LO

This article shows that the exact completion as a regular category of the homological category of Polish groups and continuous group homomorphisms is the category of groups with a Polish cover and Borel-definable group homomorphisms. We also obtain several equivalent characterizations for the morphisms in the exact completion. An analogous description is deduced for several important subcategories of the category of Polish groups.

arXiv abstract · PDF

Category theory and higher algebra · primary corpus · published 2026-08-14T08:22:48Z
Xiao Han, Peter Schauenburg
arXiv categories: math.CT, math-ph, math.RA, math.RT

We introduce cleft extensions for Hopf algebroids. We prove the equivalence between cleft extensions, $σ$-twisted crossed products, and Hopf-Galois extensions with the normal basis property, thereby generalizing the theory of cleft extensions for Hopf algebroids developed by B{ö}hm and Brzezi{ń}ski, and fitting in with the general theory of Galois and biGalois extensions over Hopf algebroids developed by the authors. We investigate the Ehresmann Hopf algebroid associated with a cleft extension and show that it is isomorphic to a generalized version of the Connes-Moscovici Hopf algebroid. A special case of the Connes-Moscovici Hopf algebroid, namely the case where the coinvariants of the cleft extension coincide with the base of the Hopf algebroid, is a Drinfeld twist of a Hopf algebroid by a two-cocycle, generalizing work of B{ö}hm, Han and Majid.

arXiv abstract · PDF

Categorical, quantum, and computational semantics · primary corpus · published 2026-08-10T13:13:54Z
Chenke Liu, Li Zhou, Boning Meng
arXiv categories: cs.PL, quant-ph

Automatic uncomputation aims to provide programming-language-level support to facilitate the correct and safe use of ancilla qubits in quantum computing, but efforts have only been made for clean ancillas, leaving dirty ancillas unexplored. We present a unified formalization of the uncomputation of both clean and dirty ancillas. For the first time, we prove that checking the existence of uncomputation is coNP-hard. We introduce two complementary synthesis-oriented existence-checking methods: a rewrite-based normalization algorithm (RwUn) and a template-based reasoning system (TpUn) that guarantees uncomputation through structured Store-Use patterns. We implement prototypes of both methods in Qiskit and Python. Compared to the state-of-the-art Reqomp~\cite{reqomp}, RwUn achieves 100% coverage on practical complex-dependency benchmarks, twice the coverage on random classical circuits, and about 50% coverage on random quantum circuits beyond the scope of existing methods, demonstrating broader applicability.

arXiv abstract · PDF

Categorical, quantum, and computational semantics · primary corpus · published 2026-08-10T14:14:02Z
David Binder, David Corfield, Dominic Orchard, Vineet Rajani
arXiv categories: cs.PL, cs.LO

Various type systems have been developed to track the cost $κ$ of a computation using a cost-tracking monad $M\ κτ$. On its own, this only tracks the worst-case cost of a computation. If we also want to track amortized cost, then we can add a type $[κ]τ$ which stores potential $κ$ with a type $τ$, together with operations for storing and releasing potential. In this work, we build on one such system, $λ$-amor: $λ$-amor allows to track cost and potential in the type system and subsumes effect and coeffect-based systems, call-by-value and call-by-name based languages. In this paper, we identify the abstract properties that denotational models of type theories for cost and potential have to satisfy: Cost and potential must be modelled by an adjoint pair of graded functors, where the functor modelling cost forms both a graded monad and a compatible graded comonad. We present three concrete instances of this general abstract scheme: (1) A simple set-theoretic model that ignores the cost tracked by the type system, (2) the Kripke logical relations model in the original $λ$-amor paper (which we show can be turned into an instance of the adjoint model), and (3) a novel model based on copresheaves on a monoidal category of costs, where we model pairs and functions by Day convolution and its right-adjoint.

arXiv abstract · PDF

Categorical, quantum, and computational semantics · primary corpus · published 2026-08-12T04:26:19Z
R. Laniewski
arXiv categories: math.CT, math.NT

This work proposes a semantic environment for arithmetic geometry in which the passage between two presentations of one object carries a measurable weight, rather than dissolving into a transparent identification. Following Lawvere, a category equipped with a cost on its morphisms is enriched over the monoidal poset $([0,\infty],\ge,+)$, so that a height becomes a map controlled by a generalized distance. Following Voevodsky, the identity type of a C-system is a locus of structure open to transport. A labeled quantitative $(2,1)$-category reconciles the two readings, with invertible $2$-morphisms witnessing that two transports differ only by a coherent change of presentation. A comparison between two labeled realizations of one object becomes a transport inequality. If it is asked to descend functorially to an inequality between extensional invariants, then it collapses to a tautology, unless a non-zero load is assigned to the transport itself, at which point the inequality regains its content. We formulate an intensional Szpiro inequality for elliptic packages, where the discriminant height transports along a morphism with a controlled model defect, and relate a bound of this shape to the $abc$ conjecture. We then treat the Birch and Swinnerton-Dyer conjecture in its pre-modularity form, so that the rank and refined forms descend to $\mathrm{ACA}_{0}$ without analytic continuation. The refined constant reads as a transport cost in which the regulator, the period, the local Tamagawa data, and the order of the Tate--Shafarevich group $\mathrm{Sha}(E/K)$ are held apart by the descent obstruction. We reduce the finiteness of $\mathrm{Sha}(E/K)$ to one hypothesis.

arXiv abstract · PDF

Categorical, quantum, and computational semantics · primary corpus · published 2026-08-13T09:33:09Z
Ryo Horiuchi
arXiv categories: math.CT, math.AT

In this note, we show the category of $Γ$-sets with the sphere spectrum, the smash product, and the substitution product gives rise to an isomix linearly distributive category, which is a categorical semantics of the multiplicative fragment of linear logic. We also show Lydakis' assembly map between these two monoidal products corresponds to the mixor.

arXiv abstract · PDF

Other logic and mathematical structures · primary corpus · published 2026-08-10T15:41:49Z
Jakub Kacper Szeląg, Aydin Abadi, Mohammad Naseri
arXiv categories: cs.DC, cs.AI, cs.LG, cs.LO, eess.SY

Decentralization as a concept in computer science has existed for over half a century. Despite its fundamental role across domains such as security, distributed computing, artificial intelligence, cloud infrastructures, and Internet of Things (IoT) architectures, there remains no universally accepted definition of decentralization applicable across computer communication systems. This has become increasingly problematic with the emergence of decentralized AI and machine learning paradigms, including collaborative training, distributed inference, blockchain-based, and agentic AI, where decentralization is often treated as a core design objective. Meanwhile, existing approaches frequently conflate decentralization with related notions such as distribution of trust or specific implementation paradigms. Such ambiguity creates inconsistencies in system analysis, limits comparability between works, and weakens the rigor of formal reasoning surrounding communication architectures and protocol design. In this work, we define this research gap as the Decentralization Problem. We analyze the formal-semantic, epistemological, and pragmatic foundations of decentralization and introduce a graph-based ontology defining it as both relational and subject-specific property of computer communication systems. The framework formally distinguishes decentralization from distribution and supports evaluation through two novel metrics: Void Tolerance and Imperviousness. We also provide a browser-based implementation that enables automated classification and metric computation of arbitrary systems. Instantiations to federated learning and blockchain architectures show consistent, comparable assessments where existing definitions produce incomplete or contradictory conclusions, providing a domain-independent foundation for analysing decentralization across heterogeneous systems.

arXiv abstract · PDF

Other logic and mathematical structures · primary corpus · published 2026-08-10T20:45:48Z
Eugene Zhang
arXiv categories: math.LO

In this paper, a new model for multi-valued logic is presented based on the notion of a bundle of predicates. The degree of truth and various logical operations for predicates in our model of multi-valued logic are rigorously defined and investigated. Furthermore, the bundle of sets as a special type of predicate bundles is thoroughly investigated to provide a rigorous model for fuzzy sets and certain adjectives/adverbs in linguistics. In addition, solutions to necessity/possibility and the sorites paradox in modal logic are given.

arXiv abstract · PDF

Other logic and mathematical structures · primary corpus · published 2026-08-11T18:20:34Z
Tan Özalp
arXiv categories: math.LO

Answering a question of Todorcevic, we prove higher-dimensional canonization theorems for the topological Ramsey space $\mathrm{FIN}^{[\infty]}_2$. Our results build upon the work of Lopez-Abad and continue the line of research initiated by Erdős and Rado, and further developed by Pudlák and Rödl, Prömel and Voigt, Taylor, and Klein and Spinas. We identify the canonical functions on fronts of $\mathrm{FIN}^{[\infty]}_2$ and develop an extension of the separating-mixing technique of Prömel and Voigt to canonize arbitrary functions $g:\mathcal{F}\toω$, where $\mathcal{F}$ is a front of $\mathrm{FIN}^{[\infty]}_2$. We further extend our canonization theorem to arbitrary Borel maps $g:\mathrm{FIN}^{[\infty]}_2\to\mathbb{R}$, establishing new canonical Ramsey theorems for Polish spaces. In particular, we provide a complete classification of the canonical functions on $\mathrm{FIN}^{[n]}_2$, together with an explicit formula for their number as a function of $n$.

arXiv abstract · PDF

Other logic and mathematical structures · primary corpus · published 2026-08-13T17:43:09Z
Peter Banáš
arXiv categories: math.LO

Let $X$ be a Polish space and let $\mathcal K(X)$ be its Vietoris hyperspace. A family $\mathcal I\subseteq\mathcal K(X)$ is hereditary if it is downward closed under inclusion. Matheron and Zelený asked whether every comeager hereditary family in $\mathcal K(X)$ contains a dense hereditary $G_δ$ subfamily. We give an affirmative answer in ZFC.

arXiv abstract · PDF