跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+1680新增论文
+1333其中 AI 相关
+187已有论文修订
+59新增 AI 导读

arXiv 最近完成扫描:2026-11-18 04:28 · 全站最近入库:2026-11-17 23:35各信源进度 →

统计口径与数据新鲜度

统计 2026-11-17 11:27 — 2026-11-18 11:27(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-18 04:28最近发现新增版本:2026-11-17 23:35库内论文最新更新时间:2026-11-17 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

25,786 已收录论文21,491 AI 相关7,725 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 309 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-18 04:27(北京时间)
新论文 · v1arXiv:2611.19613

Towards Understanding the Complexity of CAQE: A Proof-Theoretic Analysis of its Core Procedure

Benjamin Böhm, Olaf Beyersdorff

原文摘要

CAQE (Clausal Abstraction for Quantifier Elimination) is currently the most successful algorithmic paradigm for solving Quantified Boolean Formulas (QBF) in practice, clearly dominating recent QBF competitions. While apparently being a very strong solver, not much is known about CAQE in theory. We propose a framework for formalising runs of the basic CAQE algorithm (where failed assumptions are not considered) as proofs in a proof system CAQE$^{\mathsf{Core}}$, which we use to analyse the algorithm proof-theoretically and which provides methods for future work to separate it from optimised versions of CAQE that are used in practice. We show that one can perform strategy extraction on the CAQE$^{\mathsf{Core}}$ proof system in such a way that strategy size serves as a lower bound for basic CAQE runs. Furthermore, we introduce a measure, which we call CAQE width, which not only acts as a lower bound on CAQE$^{\mathsf{Core}}$ proofs, but -- with the number of $\exists\forall$ alternations as exponent -- as an upper bound as well. Using this analysis, we prove that Q-resolution with an NP oracle simulates CAQE$^{\mathsf{Core}}$ on QCNFs of bounded quantifier alternation. The same holds for QCDCL (Quantified Conflict-Driven Clause Learning, formalised as a proof system) on $Σ_3^b$ QCNFs when purely propositional CDCL steps are not counted, after a simple preprocessing step. In this setting, both systems are indeed strictly stronger than CAQE$^{\mathsf{Core}}$, where the separation of QCDCL from CAQE$^{\mathsf{Core}}$ uses cube learning.

cs.LO · cs.CC

新论文 · v1arXiv:2611.19597

Synthetic Neurosymbolic Task Generation with Controlled Constraint Complexity

Mykhailo Buleshnyi, Zsolt Zombori, Michael Benedikt

原文摘要

We introduce NeSySy, a synthetic generator for neurosymbolic learning tasks that jointly produces logical constraints and consistent datasets. Unlike existing benchmarks, NeSySy provides fine-grained control over key properties such as constraint structure, tightness, input dependence, and data generation and alignment strategies. In particular, it allows the use of rich constraints over infinite domains, and uses solvers to ensure that the constraints are meaningful and that generated samples satisfy the constraints. We design NeSySy to support both learning with declarative constraints and learning from distant supervision. Across a range of constraint families, we provide evidence that its parameters induce systematic and largely independent effects on task difficulty. Using NeSySy, we study constraint-aware learning methods, identifying regimes where explicit constraint enforcement is beneficial and where expressive unconstrained models can instead learn constraint structure directly from data. Our results establish NeSySy as a controlled testbed for analysing the interaction between learning and logical structure. NeSySy is built around a pipeline that incorporates solvers. Satisfiability checkers (CNFgen and Z3) generate and certify constraints. Constrained optimizers (RC2 for MaxSAT, Z3 for OMT) compute optimal repairs that guarantee every generated sample is consistent.

cs.LG · cs.AI · cs.LO · cs.NE · cs.SC

新论文 · v1arXiv:2611.19551

TrustBound: Mechanized Completeness for Payment Epochs Initiated by AI Agents

Sandip Nandi, Aishwarya Bose, Apurba Bose, Soovadeep Bakshi

原文摘要

Payment operations requested by an AI agent may remain executable, or their outcomes unresolved, after the agent has stopped. We study when a trusted payment service can account for every payment in an epoch and exclude further payments under earlier authority. We give a Lean model in which operations are recorded before they receive execution authority and both actions are serialized with an admission fence. We prove that fencing fixes a journal that covers every modeled effect and outstanding right; that discharging those rights prevents further effects; and that truthful outcomes for the recorded identities then give exact accounting. A provider-contract model, mapped to the admission model, makes created payment objects inert until registered. Premise-removal mutations confirm that each key premise is needed. We connect the models to an executable service: six service histories are checked against the model in Lean, and bounded schedules, scripted clients and concurrent workers exercise its reconciliation. The concurrent experiments uncovered a conflict caused by reordered provider reads, which serializing retrieval with journal updates removes in all tested cases. The result separates two obligations that are easily conflated in practice - preventing future payments and accounting for past ones - and states precisely which service guarantees establish each.

cs.CR · cs.LO

版本更新 · v2arXiv:2607.20088

What is a Model of the Linear Lambda Calculus?

Arturo De Faveri

原文摘要

We investigate the notion of model of the linear $λ$-calculus from an algebraic perspective. Our starting point is the operad of linear $λ$-terms, whose algebras provide a natural candidate. We prove that this notion of model is equivalent to two other structures: a linear analogue of Curry's $λ$-algebras, and semiclosed operads, a class of operads equipped with an internal abstraction operation. The equivalence between these three approaches unifies three complementary answers to the question of what should be regarded as a model of the linear $λ$-calculus. As a second contribution, we give a finite equational presentation for the linear variant of $λ$-algebras using the linear combinators $\mathbf{B}$, $\mathbf{C}$, and $\mathbf{I}$. Finally, exploiting the equivalence with semiclosed operads, we establish a linear analogue of Scott's representation theorem by showing that every model arises as a reflexive object in a natural monoidal closed category of presheaves.

cs.LO

版本更新 · v2arXiv:2602.12083

Differentiable Modal Logic for Multi-Agent Diagnosis, Orchestration and Communication

Antonin Sulc

原文摘要

As multi-agent AI systems evolve from simple chatbots to autonomous swarms, debugging semantic failures requires reasoning about knowledge, belief, causality, and obligation, precisely what modal logic was designed to formalize. However, traditional modal logic requires manual specification of relationship structures that are unknown or dynamic in real systems. This tutorial demonstrates differentiable modal logic (DML), implemented via Modal Logic Neural Networks (MLNNs), enabling systems to learn trust networks, temporal orders, and regulatory boundaries from behavioral data. We present a unified neurosymbolic debugging framework through four modalities: epistemic (who to trust), temporal (what can follow what), deontic (what actions are permitted), and doxastic (who believes what). Each modality is demonstrated on concrete multi-agent scenarios (from exposing an attacker in a drone swarm to deciding when to consult another LLM code reviewer), with complete implementations showing how logical contradictions become learnable optimization objectives. Key contributions for the neurosymbolic community: (1) interpretable learned structures where trust and temporal order are explicit parameters, not opaque embeddings; (2) knowledge injection via differentiable axioms that guide learning with sparse data; (3) compositional multi-modal reasoning that combines epistemic and doxastic constraints; and (4) practical deployment patterns for monitoring, active control and communication of multi-agent systems. All code is provided as executable Python scripts.

cs.AI · cs.LO

版本更新 · v3arXiv:2203.08416

On Higher-Order Reachability Games vs May Reachability

Kazuyuki Asada, Hiroyuki Katsura, Naoki Kobayashi

原文摘要

We consider the reachability problem for higher-order functional programs and study the relationship between reachability games (i.e., the reachability problem for programs with angelic and demonic nondeterminism) and may-reachability (i.e., the reachability problem for programs with only angelic nondeterminism). We show that reachability games for order-n programs can be reduced to may-reachability for order-(n+1) programs, and vice versa. We formalize the reductions by using higher-order fixpoint logic and prove their correctness. We also discuss applications of the reductions to higher-order program verification.

cs.LO · cs.PL

版本更新 · v3arXiv:1312.7275

Arithmetical Foundations - Recursion. Evaluation. Consistency

Michael Pfender

原文摘要

We fix constructive foundations for Arithmetic on a map theoretical, algorithmic level. In contrast to elementhood and quantification based traditional foundations such as Principia Mathematica PM, Zermelo-Fraenkel set theory ZF, or v. Neumann-Goedel-Bernays set theory NGB, our fundamental primitive recursive theory PR has as its basic "undefined" (not further defined) terms just terms for objects and maps. Goodstein's axiomatic uniqueness rules are derived as theorems in PR - with equality definability as a side result -, S is obtained by predicate comprehension, and the equivalence of the theory of partially defined maps and the categorical theory of mu-recursion identifies mu-recursive maps and while-loops with partially defined maps. Keywords: Goedel theorems, primitive recursion, categorical free-variables Arithmetic, mu-recursion, totality

math.LO · cs.LO · math.CT

新论文 · v1arXiv:2611.18541

没有自由格包含 FL(3) 的无限严格递增副本链

No free lattice contains an infinite ascending chain of copies of FL(3)

William DeMeo, Ralph Freese

AI 速读 基于摘要

作者证明任何自由格都不包含无限严格递增的、同构于三生成自由格 FL(3) 的子格链,并给出 Agda 形式化验证。

math.RA · cs.LO · math.GR · math.LO

查看原文摘要

No free lattice contains an infinite strictly ascending chain of sublattices isomorphic to FL(3), the free lattice on three generators; this answers a question that R. A. Dean asked and the second author's 1997 notes on the problem left open. Every such chain would yield, inside FL(3), a coherent chain of proper self-embeddings $Θ_0, Θ_1, Θ_2, \dots$ with $Θ_k \circ Θ_j = Θ_j$ for $j < k$, so that each later embedding fixes the image of each earlier one pointwise. Every proper self-embedding of FL(3) whose fixed sublattice contains a free generating triple fixes one of the three generators, say $z$, because a power of it or of its dual lies above the identity, and a self-embedding that moves every generator and lies above the identity fixes at most eleven elements. Up to duality, a proper self-embedding fixing the image of such a $Θ_1$ pointwise fixes only elements above $z \wedge (x \vee y)$, where no free generating triple containing $z$ can lie. We also verify the one-step example of the 1997 notes, prove that no step toward such a chain is self-similar, and show that the configuration the argument rules out at length three does occur at length two. Without freeness the answer reverses: FL(3) contains an infinite strictly ascending chain of 3-generated sublattices, so the lattice analogue of Takahasi's chain condition for free groups fails. The theorem itself is checked by the Agda proof assistant under its safe flags, for free lattices over generators with decidable equality, and its formal proof uses no classical principle: finite searches and an induction on a finite set replace the infinite pigeonhole principle by which a chain yields a coherent chain.

版本更新 · v2arXiv:2611.16509

面向带指针并发程序的可靠自动锁放置

Sound Automatic Lock Placement for Concurrent Programs with Pointers

Nicolas Waldburger, Florian Faissole, Ryo Okabe, Denis Cousineau

AI 速读 基于摘要

提出一种轻量级方法,为缺少或没有用户互斥锁的并发 POSIX 程序自动插入互斥锁,并形式化证明无数据竞争。

cs.LO

查看原文摘要

We propose a lightweight method for automatic lock placement in concurrent POSIX programs with explicit pointer manipulation, such as C programs. Given a program that lacks sufficient user-placed mutexes, or contains none at all, our method introduces new mutexes to prevent data races. The method is formally proven to guarantee the absence of data races and mainly consists of three steps. The first step performs lockset analysis and may-happen-in-parallel analysis. The second step conducts a concurrent points-to analysis derived from a Steensgaard-like procedural analysis, where per-thread points-to graphs are unified using a special completion rule. The final step places locks to prevent data races while respecting a lock ordering to avoid deadlocks. In addition, user-annotated critical sections are protected through insertion of dedicated locks. Since lock placement is a complex and error-prone task, our method aims at helping developers write correct concurrent programs.

版本更新 · v5arXiv:2502.02220

On the Existential Theory of the Reals Enriched with Integer Powers of a Computable Number

Jorge Gallego-Hernández, Alessio Mansutti

原文摘要

This paper investigates $\exists\mathbb{R}(r^{\mathbb{Z}})$, that is the extension of the existential theory of the reals by an additional unary predicate $r^{\mathbb{Z}}$ for the integer powers of a fixed computable real number $r > 0$. If all we have access to is a Turing machine computing $r$, it is not possible to decide whether an input formula from this theory satisfiable. However, we show an algorithm to decide this problem when: 1. $r$ is known to be transcendental, or 2. $r$ is a root of some given integer polynomial (that is, $r$ is algebraic). In other words, knowing the algebraicity of $r$ suffices to circumvent undecidability. Furthermore, we establish complexity results under the proviso that $r$ enjoys what we call a polynomial root barrier. Using this notion, we show that the satisfiability problem of $\exists\mathbb{R}(r^{\mathbb{Z}})$ is 1. in NEXPTIME if $r$ is a natural number, 2. in EXPSPACE if $r$ is an algebraic number, and 3. in 3EXP if $r$ belongs to a family of transcendental numbers including $π$ and Euler's $e$. As a by-product of our results, we are able to remove the appeal to Schanuel's conjecture from the proof of decidability of the entropic risk threshold problem for stochastic games with rational probabilities, rewards and threshold [Baier et al., MFCS'23]: when the base of the entropic risk is Euler's $e$ and the aversion factor is a fixed algebraic number, the problem is in EXP.

cs.LO

新论文 · v1arXiv:2611.18369

How rigid is maximum cardinality search? Stability and locality of MCS orderings under edge updates, verified in Lean

Md Thoriqul Islam Thonmay, Gregory Morse

原文摘要

For which sets F of edge modifications do a graph G and the modified graph share a maximum cardinality search (MCS) ordering? We prove that they do whenever, along every proper common MCS prefix, each unchosen vertex's neighbour count in the second graph exceeds its count in the first by zero or one. In particular, inserting or deleting any matching, or flipping a single edge, preserves a common ordering, and under the same hypothesis every common MCS prefix extends to a full common ordering without backtracking. Neither part of the hypothesis can simply be dropped: inserting a triangle, a P_4 or a 2P_3 shows that the +1 bound cannot be relaxed to +2, and a disjoint mixed insert/delete pair shows that the one-directional condition is needed. For the canonical ordering (smallest-index tie-breaking) under a single-edge update, an insertion can first change the ordering only strictly between the endpoints' positions, and a deletion only at the later endpoint; when no break fires, the ordering is unchanged. A boolean-adjacency executable refines the abstract probe-then-repair update. All of these results, including the four obstructions, are proved in Lean 4 over Mathlib, re-checked by independent kernel checkers, and registered in the Palomar registry. On paper we further show that the first break of an insertion is located in O((deg(v)+1) log n) time, independent of the window length. We claim no worst-case asymptotic speedup over recomputation.

cs.DS · cs.LO

版本更新 · v3arXiv:2610.29771

Logics vs doctrines, a mirror symmetry

Ivan Di Liberti, Umberto Tarantino, Lingyuan Ye

原文摘要

We study the relationship between doctrines, encoding 2-categories of theories in predicate logic, and fragments of geometric logic, defined through Kan injectivity in the 2-category of topoi. After a brief historical account of the notion of doctrine, we propose our working definition. Our main result then establishes a Galois connection between doctrines and subgeometric logics. This connection suggests a mirror symmetry between the world of doctrines and the world of logics, in which constructions and results on either side admit counterparts on the other. We develop this symmetry through constructions of syntactic categories and classifying topoi in both settings, recovering the familiar examples from categorical logic. We prove paired Diaconescu-type theorems and give symmetric descriptions of the two closure operators induced by the Galois connection. Finally, we characterise when passing from a doctrine to its closure induces a reflection between the corresponding 2-categories of algebras, and we relate this reflection to conceptual completeness.

math.CT · cs.LO · math.LO

版本更新 · v5arXiv:2503.04759

Games with $ω$-Automatic Preference Relations

Véronique Bruyère, Christophe Grandmont, Jean-François Raskin

原文摘要

This paper investigates Nash equilibria (NEs) in multi-player turn-based games on graphs, where player preferences are modeled as $ω$-automatic relations via deterministic parity automata. Unlike much of the existing literature, which focuses on specific reward functions, our results apply to any preference relation definable by an $ω$-automatic relation. We analyze the computational complexity of determining the existence of an NE (possibly under some constraints), verifying whether a given strategy profile forms an NE, and checking whether a specific outcome can be realized by an NE. When a (constrained) NE exists, we show that there always exists one with finite-memory strategies. Finally, we explore fundamental properties of $ω$-automatic relations and their implications for the existence of equilibria.

cs.LO · cs.GT

版本更新 · v4arXiv:2601.21843

The Leibniz adjunction in homotopy type theory, with an application to simplicial type theory

Tom de Jong, Nicolai Kraus, Axel Ljungström

原文摘要

Simplicial type theory extends homotopy type theory and equips types with a notion of directed morphisms. A Segal type is defined to be a type in which these directed morphisms can be composed. We show that all higher coherences can be stated and derived if simplicial type theory is taken to be homotopy type theory with a postulated interval type. In technical terms, this means that if a type has unique fillers for $(2,1)$-horns, it has unique fillers for all inner $(n,k)$-horns. This generalizes a result of Riehl and Shulman for the case $n = 3, k \in \{1, 2\}$. Our main technical tool is the Leibniz adjunction: the pushout-product is left adjoint to the pullback-hom in the wild category of types. While this adjunction is well known for ordinary categories, it is much more involved for higher categories, and the fact that it can be proved for the wild category of types (a higher category without stated higher coherences) is non-trivial. We make profitable use of the equivalence between the wild category of maps and that of families. We have formalized the results in Cubical Agda.

math.CT · cs.LO · math.LO

新论文 · v1arXiv:2611.18175

Safety Analysis of Parameterized Networks with Shared Counters

June Roupin, Arnaud Sangnier

原文摘要

We study networks with an unbounded number of processes sharing some natural counters that can be decremented, incremented and tested to zero. We look at two safety problems: the first one asks whether there is a network with an execution bringing a process in a given final state and the other one asks the execution to bring all the processes in the final state. In their full generality, these two problems are undecidable, but we show that decidability can be regained by either using a single counter or by forbidding the use of zero-tests (as it is is the case in Vector Addition Systems with States). For these decidable cases, we obtain low complexity results, the problems being solvable either in non-deterministic logarithmic space or in polynomial time.

cs.LO

新论文 · v1arXiv:2611.18169

The QBF Gallery 2026

Cynthia Peyrer, Luca Pulina, Martina Seidl

原文摘要

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

cs.LO

版本更新 · v4arXiv:2605.13348

Adequate Losses via Quantitative Linear Logic

Matteo Capucci, Robert Atkey, Charles Grellois, Ekaterina Komendantskaya, Matthew Daggitt

原文摘要

As neural components are increasingly embedded in existing symbolic software -- including safety-critical systems -- the question arises of how to specify and enforce the safety of the newly introduced neural parts. Unlike traditional logical specifications, these must be amenable not only to the standard Boolean interpretation, but also to training and optimisation. The latter calls for a quantitative interpretation of the logical syntax, subject to further requirements such as smoothness and differentiability. Moreover, the qualitative and quantitative sides of the logic must share a unifying proof-theoretic and categorical semantics. Finally, the new logic should link cleanly to the substructural and program logics that underpin the verification of existing symbolic programs. In this paper, we present a logic that ticks all of these boxes. We introduce a family of calculi, $p$QLL, indexed by a hardness degree $p$, prove a cut-elimination theorem for them, and establish completeness with respect to enriched residuated `soft' lattices. At $p = \infty$, $p$QLL reduces to multiplicative additive linear logic (MALL), and provability in $p$QLL converges to provability in MALL as $p \to \infty$. We express optimisation objectives in the syntax of this logic and prove the quantitative adequacy of neuro-symbolic loss functions -- a result that has eluded the neuro-symbolic machine learning community for nearly a decade.

cs.LO · math.LO

新论文 · v1arXiv:2611.18147

Evidence-Carrying Transport Across Effects

Félix Castro, Liron Cohen, Ariel Grunfeld, Étienne Miquey

原文摘要

A program logic proved sound against one effectful semantics need not remain sound when the effect is re-implemented, yet the semantic relationship between reasoning before and after a change of effect is usually left implicit and re-established by hand. This paper provides a uniform, proof-relevant account of it. Working in realizability, where a notion of computation determines a model whose entailments carry explicit program evidence, we introduce simulations between effectful realizability cores, generalizing Longley's applicative morphisms to computation over an arbitrary strong monad. A single simulation transports the source logic along a ladder: it induces a morphism of the associated evidenced frames and, functorially, of the induced triposes. These passages are $2$-fully-faithful, so the three levels agree and a change of effect carries the entire higher-order program logic together with the evidence witnessing each derivation. A computationally dense simulation moreover computes a modality on the source logic, a nucleus through which the transport factors and which marks exactly the reasoning stable under the change, read off from the translation rather than postulated. This recovers known examples such as the double-negation modality of classical realizability, and examples such as sheafification arise from a modal refinement of the construction. Overall, the framework makes a change of effect a first-class object, one that can be composed, factored through its modality, and shown in cases not to exist, opening a path to transporting verified reasoning across effects.

cs.LO

新论文 · v1arXiv:2611.18132

Parameterized Weakest-Precondition Calculus for Fine-grained Properties of Quantum Loops

Tianshi Yu, Minbo Gao, Li Zhou

原文摘要

Quantum loops may execute arbitrarily many iterations, and understanding their runtime behavior requires knowing how often they terminate, how long terminating runs take, and how common very long runs are. We develop a compositional weakest-precondition framework for analyzing these properties on possibly infinite-dimensional state spaces. It uses parameterized predicates: families of quantum effects indexed by a positive observation scale. These families retain runtime information even when the expected runtime is infinite and can be reused through sequential composition and nested loops. We prove that weakest-precondition equations for loops have unique solutions in the parameterized predicate domain. From the asymptotic behavior of the derived weakest preconditions, we then recover these runtime properties and quantify the influence of very long terminating executions. For the classic discrete-time quantum walk on the one-dimensional infinite line with one absorbing boundary at the origin and the Hadamard gate as its coin operator, we verify its termination probability $2/π$, conditional mean $π/2$, and logarithmic growth of the conditional capped second moment. We then reuse the walk's specification to verify the termination probability and conditional mean runtime of an outer loop that repeatedly invokes it.

cs.LO · cs.PL

新论文 · v1arXiv:2611.18017

On Structure-Aware SAT Solving

Eugene Goldberg

原文摘要

Although modern SAT solvers have made remarkable progress, they still exploit formula structure only to a limited extent. We present two techniques that make SAT solving more structure-aware and provide experimental results showing their promise. The first technique ``$\mathit{melts}$'' the formula by reducing interaction between its parts. This is achieved by adding new variables, using existential quantifiers, and applying a procedure called partial quantifier elimination. The second technique exploits the notion of a $\mathit{local}$ $\mathit{proof}$. The latter establishes that a formula is unsatisfiable by proving that certain literals of its clauses are redundant. We show that using local proofs makes SAT solving more formula-specific.

cs.LO

版本更新 · v3arXiv:2608.02596

Staying Productive Under the Palm Trees: On Graded Coeffect Typing in the Tropical Semiring

Rémy Cerda, Ugo Dal Lago

原文摘要

We give a temporal reading of graded coeffects: tropical grades carry guards on infinite computation. To illustrate it, we first define $G_T$, a polymorphic calculus with guarded recursive types that guarantees productive infinite computation, in the form of hereditary head normalisation. The calculus supports stream computing via the Scott encoding, and embeds Nakano's later modality. We then introduce $I_T$, a graded intersection type system with guarded infinitary types for the pure λ-calculus, whose typability allows for an exact characterisation of hereditary head normalisation. We prove that the characterising typability predicate is $Π_0^2$, matching the recursion-theoretic complexity of the characterised property.

cs.LO · cs.PL

新论文 · v1arXiv:2611.17937

Tracing Actual Causes with Counterfactual Witness Maps

Tim Woydt, Matej Zečević, Kristian Kersting, Moritz Willig

原文摘要

Halpernian actual causation, the formal study of which events in a specific situation caused a specific outcome in acyclic structural causal models, underpins legal responsibility, moral blame, and the assessment of causal harm. Despite the rich logical framework, no prior sound and complete enumeration procedure is known for finding all actual causes in a given setting, blocking downstream tasks such as responsibility attribution, blame assessment, and causal-harm grading that aggregate over the full cause set. We close this gap by introducing witness targets: sets of joint configurations containing every counterfactual witness. In combination with an ancestor intervention grammar we derive a finite directed acyclic witness map. We prove that for every actual cause there exists a contingency set such that the joint intervention set appears as a node of this map, and present an algorithm for Tracing Actual Causes (TrAC) that is sound and complete for enumerating all actual causes of any target event. We compare TrAC empirically with existing single-cause baselines on random Boolean structural causal models, demonstrating practical feasibility for graphs of up to 15 nodes.

cs.AI · cs.LO

新论文 · v1arXiv:2611.17884

HOL in HOL: mechanized soundness, completeness and consistency, with and without infinity

Christoph Benzmüller, Daniel Kirchner

原文摘要

What can a logic certify about a copy of itself? For Church's simple theory of types, formalized as a deep embedding in Isabelle/HOL with Henkin semantics and a natural-deduction calculus, the answer has two tiers. On the first tier, plain Isabelle/HOL certifies the logic without an axiom of infinity, by a standard model with one individual. On the second tier, the logic with a Dedekind-style axiom of infinity is certified only in Isabelle/HOL extended by a large enough set-theoretic universe. Both tiers appear in Harrison's self-verification of HOL Light. What the present formalization adds is Henkin completeness, and with it a semantics that matches the calculus exactly, compactness and model existence on the first tier, and the boundary between the tiers. Comparing two ways of adding infinity to the object logic shows where the boundary lies. One is an infinite domain of individuals, expressed by the first-order sentences "there are at least $n$ individuals", each of which has a finite model; the other is the Dedekind axiom, a single sentence with no finite model, and there the first tier ends. In the calculus the axiom is strictly stronger than the sentences together: it derives each of them, but they do not derive it. The witness is a countable Henkin model in which every sentence holds and the axiom fails, because its function domain is too sparse for an injective, non-surjective self-map. On the second tier, the universe serves one purpose only: to prove the Dedekind axiom consistent. Everything that follows, completeness and even the countable Henkin model of the axiom, is obtained in plain Isabelle/HOL. The universe axiom is Harrison-style, realized in Paulson's ZFC_in_HOL with the domain of every type in $V_{ω+ω}$; with it, full classical higher-order logic with infinity and relational choice is consistent relative to set theory.

math.LO · cs.LO

新论文 · v1arXiv:2611.17866

Active Learning of Temporal Specifications through Distinguishing Queries

Rajarshi Roy, Xiaowei Huang

原文摘要

Temporal specifications are essential for verification and monitoring, yet writing formulas that capture the intended behaviour is difficult. Active learning derives such specifications through interaction between a learner and a teacher, but remains underexplored for temporal logics. Existing approaches require the teacher to answer equivalence queries and to construct counterexamples, and they often rely on SAT-based learning procedures that restart the search after each new example. We present an active-learning framework for LTLf in which the teacher only labels traces and answers natural-language questions about the intended behaviour. The learner maintains an enumerated version space of candidate formulas, generates traces that distinguish candidates, and uses the teacher's hints to rank candidates or to restrict the search. We prove consistency with the observed examples, identification within bounded hypothesis classes with a bound on the number of queries, and a PAC guarantee for the final hypothesis. In experiments with a simulated teacher on 36 targets, including targets in four standard environments, the learner identifies every target when it compares all rivals, with fewer than seven queries beyond an initial sample of ten traces on average. Correct hints reduce the number of queries by up to 16% and the number of generated candidates by a fifth, and hints used for ranking never prevent identification, even when incorrect. Our enumeration-based version space is faster than the SAT-based approach of previous learners at every target size.

cs.LO · cs.AI

新论文 · v1arXiv:2611.17742

Analysing Busy Beaver Machines (Or How to Find Ossified Ocelots)

James Harland

原文摘要

The busy beaver problem involves working with machines which can produce very large numbers, both for the output of certain Turing machines and for the number of steps taken to execute them. Given that these numbers can involve thousands of digits, it is crucial to have a means of proving properties of the relevant machines which allow manipulation of such large numbers. In this paper we introduce the notion of \textit{shape computations} as a means of isolating key properties that allow efficient execution of the relevant Turing machines based on verifiable properties of state transitions. In particular, this notion allows us to provide an analytical result which demonstrates the quadratic relationship between the size of the output and the number of steps required to generate it. We have also developed an initial implementation of our approach, and we provide empirical evaluation of it on a suite of 240 example machines.

cs.FL · cs.LO

版本更新 · v3arXiv:2605.10005

Hybrid Mechanical and Agentic Specification Inference

Wolfgang Grieskamp, Teng Zhang, Vineeth Kashyap

原文摘要

Adoption of formal verification has long been hindered by the cost of manual specification. To prove high-level properties, one must also write contracts for supporting functions, many of which are mechanical and low-level. Specification inference automatically derives such contracts from the program. We present a hybrid of mechanical and agentic inference for Move, a smart contract language, integrated into its verifier, the Move Prover. A large language model (LLM) agent drives inference and verification through a tool that calls the Move Prover and derives specifications from code by weakest-precondition (WP) analysis. We evaluate our approach on 26 targets, 24 of them extracted from public Move functions of the Aptos framework that have no specifications, under a frontier model and a mid-tier model of the same family (Sol 5.6 and Terra 5.6). With and without WP, the agent completes over 90% of its runs, so agentic inference is effective on its own. Adding WP lowers its cost by 11-21% overall and by 40-64% on targets without loops.

cs.PL · cs.AI · cs.LO · cs.SE

新论文 · v1arXiv:2611.17618

Lean-PEP: Performance-Estimation Certificates to Formally Verified Algorithmic Bounds

Xinyuan Guo, Andersen Ang

原文摘要

Performance-estimation certificates describe worst-case bounds for optimization algorithms. Turning a certificate into a formal theorem requires exact verification of its algebra and a connection between its coordinates, constraints and objective and the intended function-level problem. Lean-PEP provides a reusable interface for this task. It checks a submitted source and exact certificate against a supported canonical finite model, and a parameterized analytic theorem transfers the resulting finite bound to every admissible algorithm trajectory. Generated computation proofs discharge the obligations that depend on each certificate. An additional capture entry checks the numerical record and reconstruction policy. The implemented two-step proximal-gradient consumer verifies a new input with normalized bound 62500/499999, and a fixed eight-configuration batch yields seven distinct payloads with accepted certificates and executed Lean proofs. PG/GD cases and one-step attainment witnesses establish the corresponding algorithmic conclusions, and a fresh installation reproduces consumption of the supplied input. These results show how new certificate data can reuse a proved analytic interface to obtain function-level bounds within the supported models.

cs.LO

版本更新 · v3arXiv:2101.00834

Symbolic Control for Stochastic Systems via Finite Parity Games

Rupak Majumdar, Kaushik Mallik, Anne-Kathrin Schmuck, Sadegh Soudjani

原文摘要

We consider the problem of computing the maximal probability of satisfying an omega-regular specification for stochastic nonlinear systems evolving in discrete time. The problem reduces, after automata-theoretic constructions, to finding the maximal probability of satisfying a parity condition on a (possibly hybrid) state space. While characterizing the exact satisfaction probability is open, we show that a lower bound on this probability can be obtained by (I) computing an under-approximation of the qualitative winning region, i.e., states from which the parity condition can be enforced almost surely, and (II) computing the maximal probability of reaching this qualitative winning region. The heart of our approach is a technique to symbolically compute the under-approximation of the qualitative winning region in step (I) via a finite-state abstraction of the original system as a 2.5-player parity game. Our abstraction procedure uses only the support of the probabilistic evolution; it does not use precise numerical transition probabilities. We prove that the winning set in the abstract 2.5-player game induces an under-approximation of the qualitative winning region in the original synthesis problem, along with a policy to solve it. By combining these contributions with (a) a symbolic fixpoint algorithm to solve 2.5-player games and (b) existing techniques for reachability policy synthesis in stochastic nonlinear systems, we get an abstraction-based algorithm for finding a lower bound on the maximal satisfaction probability. We have implemented the abstraction-based algorithm in Mascot-SDS (Majumdar et al., 2020), where we combined the outlined abstraction step with our recent tool FairSyn. We evaluated our implementation on the nonlinear model of a perturbed bistable switch from the literature. We outperform a recently proposed tool for solving this problem by a large margin.

eess.SY · cs.LO

新论文 · v1arXiv:2611.17127

分级交集类型

Graded Intersection Types

Rémy Cerda, Ugo Dal Lago

AI 速读 基于摘要

作者提出分级交集类型,用半环系数标记箭头域的多重集,统一幂等与非幂等交集类型,并给出保持归约与展开的代数条件。

cs.LO · cs.PL

查看原文摘要

We introduce graded intersection types, in which arrow domains are multisets of types with coefficients in a semiring. Boolean and natural number grades recover idempotent and non-idempotent intersection types. We give algebraic conditions on the semiring for subject reduction and expansion in finite systems and in locally finite systems with guarded infinite types. We construct a lifting to multisets of grades corresponding, in this general setting, to lifting the idempotent system to the non-idempotent one. We recall the main existing operational characterisations from the literature, and show some general extensions.

新论文 · v1arXiv:2611.17106

对称编程与推理的数学基础

Mathematical foundations for symmetric programming and reasoning

Ohad Kammar, Matija Pretnar

AI 速读 基于摘要

该文基于数学中“不失一般性”(w.l.o.g.)的证明原则,提出一种统一利用对称性的数学抽象,用于编程与推理。

cs.PL · cs.LO · math.CT · math.GR · math.LO

查看原文摘要

We develop a mathematical abstraction for uniformly exploiting symmetries in programming and reasoning based on the mathematical proof principle `without-loss-of-generality' (w.l.o.g.). Given: group actions that describe symmetries of the input and the output; and a canoniser, which captures how arbitrary inputs get sent to canonical ones, our construction extends any function from the canonical inputs to the whole domain. We characterise the conditions on the canonisers which guarantee that the construction gives the unique equivariant (i.e. symmetry-preserving) extension. Furthermore, we adapt the construction to a dependently-typed setting, where it captures traditional symmetric w.l.o.g. arguments via the Curry-Howard correspondence. Finally, we extend the construction to algebraic data types, where the symmetries of the constructors both uniquely determine the symmetries of the data type and pave the way for efficient execution.