跳到正文
研踪PaperTrail

YOUR RESEARCH, IN SIGHT

让下一篇重要论文,不再错过。

覆盖计算机全学科,以 AI 为快捷入口。关注方向、作者和关键词,把发现变成持续的研究积累。

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

全站更新概况

+0新增论文
+0其中 AI 相关
+1已有论文修订
+100新增 AI 导读

arXiv 最近完成扫描:2026-11-08 22:53 · 全站最近入库:2026-11-08 06:02各信源进度 →

统计口径与数据新鲜度

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

最近完成检查:2026-11-08 22:53最近发现新增版本:2026-11-08 06:02库内论文最新更新时间:2026-11-06 02:59

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

17,100 已收录论文14,661 AI 相关4,057 有修订112 HF 社区发现

浏览论文库

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

找到 181 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-08 22:48(北京时间)
版本更新 · v3arXiv:2604.10669

A Linear Temporal Logic of Frequencies on Series of Events

Melissa Antonelli, Alessandro Giuseppe Buda, Leonardo Ceragioli, Ferdinando Fugazza Calda, Giuseppe Primiero

原文摘要

This paper introduces LTLFS, a linear temporal logic for reasoning about frequencies in finite series of probabilistic events. The logic conservatively extends linear temporal logic over finite traces with measure-sensitive operators that compare the empirical distribution observed at any point in a series with an independently specified target distribution. Its semantics integrates the actual sequence of events, the probability distribution governing individual outcomes, and the set of finite assignments compatible with the target frequency. This supports two complementary tasks: verifying whether an observed partial distribution is compatible with the benchmark, and predicting whether and with what probability the completed series can still satisfy it. The language can express observed and attainable frequencies, the probability of realizing a desired final distribution, and conditional probabilities for subsequent outcomes under the assumption that the benchmark is met. We establish formal properties of the operators and characterize their interaction with the temporal structure. A running example concerning representational fairness in sequential outputs from a generative AI system illustrates how the framework can distinguish temporary deviations from irrecoverable violations and support early, logically interpretable intervention. LTLFS thereby provides a symbolic foundation for runtime monitoring of evolving quantitative requirements, with applications to explainable and responsible AI.

cs.LO · math.LO

版本更新 · v5arXiv:2609.36279

Proofs Without Nominals: Gödel's Ontological Argument, its Shallow Embedding, and the Open Questions of the Monatshefte Notes

Christoph Benzmüller

原文摘要

The shallow embedding of higher-order modal logic in classical higher-order logic, used in Benzmüller and Scott's Notes on Gödel's and Scott's variants of the ontological argument, reaches beyond the modal object language: its quantifiers range over domains containing the nominals and satisfaction operators of hybrid logic. A proof using one proves a theorem of the embedding, not necessarily of the modal logic. Whether a result is one of the modal logic can be settled by replaying it in an explicit calculus, or, more cheaply and for all results at once, by analysing what the embedding's proofs substitute. Every statement the Notes prove has a proof in the embedding substituting nothing outside the object language, 294 of them explicit. The Notes' own proofs substitute none either; what it flags are terms a prover introduced. A soundness theorem over general models closed under the object language, and a sentence of that language the embedding proves but which fails in such a model, fix what the certificate says. The Notes' three open questions are settled too, without nominals, but by the empty instance of the conjunction axiom, too cheaply to convince. Generalised to Gödel's "any number of summands", the axiom covers the empty conjunction and the singleton. This article restricts it to at least two different conjuncts, a non-degenerate reading of Gödel's footnote, and settles them again without nominals. In effect only the empty conjunction is excluded; the singleton comes back with the other axioms. In one variant the restriction refutes the possible existence of a God-like being; the answers return, with no side condition, once the Notes' non-emptiness clause is confined to Gödel's essence. Every theorem here is verified in Isabelle/HOL and independently in Lean 4, the separating model in its propositional part; the countermodels are Nitpick's, checked by the build.

cs.LO · cs.AI · math.LO

版本更新 · v6arXiv:2307.12454

Extracting total Amb programs from proofs

Ulrich Berger, Hideki Tsuiki

原文摘要

We present a logical system CFP (Concurrent Fixed Point Logic) supporting the extraction of nondeterministic and concurrent programs that are provably total and correct. CFP is an intuitionistic first-order logic with inductive and coinductive definitions extended by two propositional operators: Restriction (binary), a strengthening of implication, and a unary operator for total concurrency. The source of the extraction is formal CFP proofs, the target is a lambda calculus with constructors and recursion extended by a constructor Amb (for McCarthy's amb) which is interpreted operationally as globally angelic choice and is used to implement nondeterminism and concurrency. The correctness of extracted programs is proven via an intermediate domain-theoretic denotational semantics. We demonstrate the usefulness of our system by extracting a nondeterministic program that translates infinite Gray code into the signed digit representation. A noteworthy feature of CFP is the fact that the proof rules for restriction and concurrency involve variants of the classical law of excluded middle that would not be interpretable computationally without Amb. This is a revised and extended version of the conference paper presented at ESOP 2022 with the same title that contains full proofs of all major results.

cs.LO

新论文 · v1arXiv:2611.01501

Order-Invariant CFO Contains Local-Order-Invariant FO

Derek R. Aoki

原文摘要

Order-invariant cluster first-order logic (CFO) and local-order-invariant first-order logic are two fragments of order-invariant first-order logic, both motivated by the study of invariant logics on classes of bounded degree. Our main result is that order-invariant CFO contains local-order-invariant FO on arbitrary classes of finite structures, settling the conjecture of Ghasemi and Grange that order-invariant CFO contains plain FO. By combining this with a collapse result of Ghasemi and Grange, we obtain the equivalence of FO, local-order-invariant FO, and order-invariant CFO on classes of finite colored graphs of bounded degree. The proof makes use of Gaifman normal form, which allows our translation from local-order-invariant FO to order-invariant CFO to be effective. Combined with the fixed-parameter tractability of model-checking for order-invariant CFO on bounded-degree colored graph classes, this shows that model-checking for local-order-invariant FO on bounded-degree colored graph classes is fixed-parameter tractable. To generalize our collapse and model-checking results beyond colored graphs, we use a method based on first-order interpretations which also yields a collapse of order-invariant FO to FO when restricted to graph classes of bounded shrub-depth. Finally, we give an application to the database-motivated frozen-witness logic of Abiteboul, Simon, and Vianu by showing that local-order-invariant FO contains deterministic frozen-witness FO, and thus that deterministic frozen-witness FO collapses to FO on classes of finite structures of bounded degree.

math.LO · cs.LO

版本更新 · v4arXiv:2510.24993

Morita Rigidity for Kleene Algebras

Luke Serafin

原文摘要

We introduce Morita equivalence to the study of Kleene algebras and modules. Classical characterizations of Morita-equivalent semirings such as having equivalent categories of modules and one semiring being a full idempotent corner of a finite matrix semiring over the other transfer easily to this new context. We also observe that Morita equivalence can be applied to extending and restricting scalars in Lindenbaum--Tarski algebras of propositional dynamic logics, and that an appropriately-defined category of generalized finite automata satisfies the property that when the underlying Kleene algebras are Morita equivalent then the corresponding categories of generalized automata are equivalent. But the signature results which we obtain relate to rigidity of Kleene algebras in this context. Specifically, every semiring that is Morita-equivalent to the semiring reduct of a Kleene algebra has a unique expansion to a Kleene algebra, and semiring bimodules witnessing Morita-equivalence of semirings which are reducts of Kleene algebras are already Kleene bimodules.

cs.LO · math.LO

新论文 · v1arXiv:2611.01357

ProofPatch: Reviewing Lean Statements and Keeping the Reviews Valid as Formalizations Evolve

Xujun Che, Depeng Xu, Jian Xiang, Taufiqua Khan

原文摘要

The kernel of the Lean proof assistant checks that a proof establishes its statement. Whether the statement says what was intended is left to human reviewers. This is the old problem of validating a specification, and it grows more pressing as language models write formal statements in bulk and agents edit formal developments continuously. We present ProofPatch, a tool that helps reviewers judge Lean statements and keeps their judgments valid while the development changes. A reviewer can ask the kernel targeted questions about a statement, such as whether a hypothesis is needed or whether a counterexample exists. Each decision is stored with fingerprints of the statement as Lean elaborated it and of the definitions it depends on, and any declaration can be pinned so that a patch changing it is blocked, whether a person or an agent built on a large language model (LLM) wrote the patch. Working on elaborated terms rather than source text is the central design choice: notation and formatting changes leave a decision intact, and a changed definition reaches every theorem that uses it. On 229 pairs of consecutive revisions of Mathlib, Lean's mathematics library, ProofPatch sends 118 of 12,898 synthetic decisions back for review. Every text-based alternative misses at least 38 of these or sends back at least 13 times as many. On 1,527 labeled statements, kernel evidence flags unfaithful ones with precision 0.88 to 0.96, and in 344 runs of an LLM agent no change to a pinned statement got through.

cs.LO · cs.AI · cs.SE

新论文 · v1arXiv:2610.40560

FARMS:面向自动化计算科学的可验证基础

FARMS: A Verifiable Foundation for Automated Computational Science

Di Wu, Ling Liang, Haizhao Yang

AI 速读 基于摘要

作者提出 FARMS,将计算数学知识转化为可供 AI 解释与复用、并带有显式保证的“计算知识”基础。

cs.AI · cs.LO

查看原文摘要

Automated computational science could accelerate discovery by selecting, adapting and developing numerical methods. This prospect requires mathematical knowledge that AI systems can interpret and reuse with explicit guarantees. Here we present FARMS, a faithful and efficient foundation that transforms computational mathematics into AI-ready computing knowledge. FARMS connects formal statements to source context, algorithmic meaning and quantitative guarantees through source preparation, reusable representations and semantic review. Across 171 targets in randomized numerical linear algebra and numerical partial differential equations, 157 were accepted by the pipeline, with mean estimated costs of US \$0.85-2.29 per target across sources. Lean-checked implications from explicit source premises connect selected statements to computational skills, illustrated by a heat-flow solve and wave-response compression. FARMS therefore supports an affordable, reusable knowledge foundation for trustworthy automated computational science.

新论文 · v1arXiv:2610.40538

crush:面向 Lean 的可扩展证明自动化

crush: Extensible Proof Automation for Lean

Mike He, Dexin Zhang, Aarti Gupta

AI 速读 基于摘要

提出一个基于 SMT 的可扩展 Lean 证明自动化框架 crush,用去函数化桥接高阶构造与一阶求解器,并支持可扩展的翻译与证明重建。

cs.LO · cs.PL

查看原文摘要

Lean's rich expressiveness supports higher-order functions, inductive datatypes, and user-defined abstractions, making it challenging to translate proof obligations into first-order Satisfiability Modulo Theory (SMT) queries and reconstruct kernel checked proofs. We present crush, an extensible SMT-backed proof automation framework for Lean. To bridge the gap between Lean's higher-order constructs and the solver's first-order logic, crush uses defunctionalization to encode function values and their applications. We formalize this translation for a supported higher-order fragment and prove its soundness. Moreover, crush provides metaprogramming interfaces for extending both Lean-to-SMT translation and the reconstruction of Lean proofs from solver certificates without modifying the translation pipeline. We implement crush as both a tactic and a backend for other third-party automation systems. We show that across four such use cases that target verification and general proof automation, crush discharges more obligations than the competing backends and reconstructs more kernel-checked proofs than the baselines.

新论文 · v1arXiv:2610.40503

代数世界模型:从探索到证明

Algebraic World Model: From Exploration to Proofs

Guancheng Pan, Qixin Tan, Yang Yuan, Andrew Chi-Chih Yao

AI 速读 基于摘要

提出代数世界模型(AWM),将未知环境中的探索转化为可执行假设、范畴论引导的结构化模型,并在 Lean 4 中形式化证明可达性与不可能性。

cs.AI · cs.LO

查看原文摘要

AI has made remarkable progress in mathematics, solving challenging problems with machine-checkable proofs in Lean, yet typically relying on predefined mathematical definitions and formal specifications. This raises a natural question: can it reason rigorously about an unknown world? We introduce the Algebraic World Model (AWM), a framework that turns interaction with unfamiliar environments into explicit mathematical models supporting formal reasoning. AWM explores the environment and develops executable Python hypotheses, continually testing and revising them against observations. It then structures these hypotheses into typed objects and shared rules, simplifies their structure through category-theory-guided transformations, and formalizes the resulting model in Lean 4 to prove reachability and impossibility. AWM can formally prove that a goal is unreachable, even beyond explored trajectories. On two impossible game levels, it constructs closed, kernel-checked Lean proofs excluding every legal winning sequence in all six runs, while Claude Opus 5.5 and GPT-6 Astra, equipped with coding tools, produce none in twelve baseline runs. Four of AWM's six initial bounds are correct, compared with one for Opus 5.5 and none for GPT-6 Astra; given only feedback that a cheaper win exists, AWM revises its rules and constructs new proofs, reaching six of six correct bounds. Moreover, AWM produces interpretable mathematical models whose rules can be inspected and tested step by step. Across all 25 public ARC-AGI-3 games, these models enable Lean to replay the winning trajectories of all 183 levels and generalize beyond observed play, predicting unseen transitions and detecting changes in game mechanics. With Claude Opus 5, AWM clears all levels with a score of 99.9, while its certified winning trajectories use only 43% of the human baseline's actions.

新论文 · v1arXiv:2610.40378

论二维约束循环问题的判定

On Deciding the Constraint Loop Problem in Dimension Two

Daria Goliasova, Toghrul Karimov

AI 速读 基于摘要

作者通过分析无限运行见证的结构,将二维线性约束循环终止性判定从多项式空间改进到多项式时间,并给出基于 Z3 的实现。

cs.LO

查看原文摘要

Recently, Guilmant, Lefaucheux, Ouaknine, and Worrell [2] proved decidability of the termination problem for linear constraint loops over two real-valued variables, thus settling a wellknown open problem. Their algorithm is based on a theoretical result that such a loop does not terminate if and only if it has a witness of an infinite run of a specific shape. By analysing the structure of the witness carefully, we show that termination such loops can be decided in polynomial time, improving on the polynomial space bound argued by Guilmant et al. We also present an efficient implementation of the polynomial-time algorithm based on the satisfiability modulo theories (SMT) solver Z3.

新论文 · v1arXiv:2610.40377

面向基于逻辑的工作流模式的组合过程层次结构

A Hierarchy of Composition Procedures for Logic-Based Workflow Patterns

Radosław Klimek

AI 速读 基于摘要

论文提出从 ΠC₀ 到 ΠC₄ 的模式组合过程层次,将工作流模式的组合复杂度与时间逻辑片段 TL_j 的表达力分离,形成 ΠC_i[TL_j] 框架。

cs.LO

查看原文摘要

Logic-based workflow patterns capture recurring behavioural structures together with reusable temporal specifications. Their composition raises distinct problems as workflow structures become richer, including instantiation, nesting, conditional execution, repeated occurrences, and traceability of generated formulae. This paper proposes a hierarchy of Pattern Composition ($ΠC$) procedures, from $ΠC_0$ to $ΠC_4$, that organizes these requirements as progressively richer compositional capabilities. The hierarchy separates compositional complexity from the expressive power of the temporal-logic fragment, represented by $TL_j$, yielding a framework $ΠC_i[TL_j]$ for developing logical workflow specifications. We develop activation-aware Pattern Composition ($ΠC_2$), which distinguishes the structural presence of a nested pattern from its execution in a particular workflow context. We formalise its recursive procedure, analyse its properties, and define an evaluation protocol for conditional activation, conservativity under mandatory composition, and specification growth. The hierarchy also characterizes selective occurrence qualification for iterative patterns ($ΠC_3$) and provenance for tracing generated formulae to their sources ($ΠC_4$). Finally, we outline $ΠC_{\mathrm{Assist}}$, an orthogonal mode in which AI proposes and refines pattern expressions subject to the hierarchy's compositional checks.

版本更新 · v2arXiv:2512.06959

遗传历史保持互模拟:基于后向就绪多重集的特征刻画

Hereditary History-Preserving Bisimilarity: Characterizations via Backward Ready Multisets

Marco Bernardo, Andrea Esposito, Claudio A. Mezzina

AI 速读 基于摘要

作者提出用后向就绪多重集相等增强前向后向互模拟,从而在稳定配置结构和可逆进程演算中给出遗传历史保持互模拟(HHPB)的两种互补刻画。

cs.LO

查看原文摘要

We devise two complementary characterizations of hereditary history-preserving bisimilarity (HHPB): a denotational one, over stable configuration structures, and an operational one, in a reversible process calculus. Our characterizations rely on forward-reverse bisimilarity (FRB) augmented with backward ready multiset equality, which is able to distinguish between autoconcurrency and autocausation. With respect to previous work, we thus shift the emphasis from uniquely identifying events, as done in other characterizations, to counting occurrences of identically labeled events associated with incoming transitions. This yields a more lightweight behavioral equivalence than HHPB: our bisimulations are still binary relations instead of ternary ones and do not need to incrementally build any labeling- and causality-preserving bijection for occurred events. We show that our characterizations are valid in the absence of non-local autoconflicts. We then study the logical foundations of these characterizations by relating event identifier logic, which captures HHPB, and backward ready multiset logic, developed for our extension of FRB.

新论文 · v1arXiv:2610.40310

在 Lean 中用 Vampire 进行自动定理证明

Hammering with Vampire in Lean

Jonas Bodingbauer, Laura Kovács

AI 速读 基于摘要

作者提出 Vampire-Hammer,将 Lean 目标交给 Vampire 自动定理证明器求解,并重建可由 Lean 内核检查的证明。

cs.LO · cs.AI

查看原文摘要

We present Vampire-Hammer, a hammer for the Lean interactive theorem prover that discharges goals using the Vampire automated theorem prover and reconstructs proofs checked by the Lean kernel. Vampire-Hammer uses the Lean-auto framework to process goals and premises before dispatching them to Vampire for proof search. Doing so, we rely on standard TPTP problem formats and annotated TSTP proofs that support proof reconstruction. With a 10-second budget on 196,083 eligible Mathlib theorems, Vampire-Hammer solves 21,158 problems not solved by other evaluated tools within the same budget.

新论文 · v1arXiv:2610.40154

A Quantitative Interpretation of Useful Call-by-Value

Pablo Barenbaum, Delia Kesner, Mariana Milicich

原文摘要

In this work, we present the first semantic interpretation of useful call-by-value evaluation through a non-idempotent intersection type system called U. One first contribution of this paper is a characterisation of termination of useful call-by-value evaluation via U-typability. That is, a term is typable in system U if and only if it terminates in the useful call-by-value strategy. As a second contribution, we show that system U provides a quantitative interpretation for useful call-by-value evaluation, offering exact step-count information for program evaluation. Even though the specification of the operational semantics of useful evaluation is highly complex, system U is notably simple. As far as we know, system U is one of the scarce quantitative type systems capturing exactly the substitution step-count for variables and abstractions in an open call-by-value strategy. Our third contribution is a termination-equivalence result between standard call-by-value, which may perform erasing reductions, and useful call-by-value, which is non-erasing. To establish this result, we introduce a non-erasing restriction of standard call-by-value, a refinement that serves as an intermediate calculus bridging standard and useful call-by-value. We show that all three calculi have the same termination behaviour, and hence induce the same observational equivalence.

cs.LO

版本更新 · v2arXiv:1504.06203

A Behavioural Thesis of Synchronous Parallel Algorithms -- Correction of the Simplified Parallel ASM Thesis

Flavio Ferrarotti, Klaus-Dieter Schewe, Loredana Tec, Qing Wang

原文摘要

A behavioural theory consists of machine-independent postulates characterizing a particular class of algorithms or systems, an abstract machine model that provably satisfies these postulates, and a rigorous proof that any algorithm or system stipulated by the postulates is captured by the abstract machine model. The class of interest in this article is that of synchronous parallel algorithms. For this class a behavioural theory has already been developed by Blass and Gurevich, which, though mathematically correct, fails to be convincing, as it is not intuitively clear that the postulates really capture the essence of (synchronous) parallel algorithms. We present a much simpler (and presumably more convincing) set of four postulates for (synchronous) parallel algorithms, which are close to those of Gurevich's sequential ASM thesis. The key difference is an extension of the bounded exploration postulate using multiset comprehension terms instead of ground terms formulated over the signature of the states. In addition, all implicit assumptions are made explicit, which amounts to representing states of a parallel algorithm by meta-finite first-order structures. The article first provides evidence that the axiomatization characterizes the whole class of deterministic, synchronous, parallel algorithms, then formally proves that parallel algorithms are captured by Abstract State Machines (ASMs). The proof uses the requirement of the bounded exploration postulate that update sets be uniformly definable, by equality-free first-order formulae, in the finite critical structures determined by the witness terms; these formulae are translated into the guards of a parallel ASM rule. This version corrects the characterization proof of the first version, whose key lemma was false; the bounded exploration postulate has been amended accordingly.

cs.LO

版本更新 · v2arXiv:2604.22020

Interpolation above S4

Simon Santschi, Niels C. Vooijs

原文摘要

We complete Maksimova's classification of Craig and deductive interpolation in normal extensions of S4. In particular, we prove Craig interpolation for the six extensions of S4 for which the status of the property was still open. The proof strategy builds upon the ideas of Smoryński, but employs a novel approach using Fine's frame formulas for splitting clusters in transitive models.

math.LO · cs.LO

新论文 · v1arXiv:2610.40042

UPPAAi: Towards LLM-Assisted Modeling, Verification, Analysis and Synthesis

Peter Dolog, Kim G. Larsen, Marius Mikučionis, Frederik F. K. Rasmussen

原文摘要

For more than three decades, UPPAAL has supported the modelling and analysis of real-time and cyber-physical systems. Yet building a suitable model, formalising the intended properties, choosing analysis techniques and interpreting counterexamples remain iterative tasks that demand substantial expertise. Large language models (LLMs) can offer plausible explanations and even solutions, but they are not necessarily correct. We present UPPAAI, an extension of UPPAAL in which users construct, explain, debug and specify models in dialogue with an LLM. The guiding principle is that the user requests, the LLM proposes, explains and orchestrates, and UPPAAL verifies. UPPAAI exposes the UPPAAL editor, queries and verifier through a Tools API. We report on seven case studies, from explaining to a newcomer to learning a controller, covering timed automata, stochastic hybrid automata and strategy learning. LLMs proved to be extremely helpful in not just generating solutions but also pro-actively suggesting relevant UPPAAL features it was not asked about.

cs.SE · cs.AI · cs.LO

版本更新 · v3arXiv:2502.18259

Generalization of terms via universal algebra

Tommaso Flaminio, Sara Ugolini

原文摘要

We provide a new foundational approach to the generalization of terms up to equational theories. We interpret generalization problems in a universal-algebraic setting making a key use of projective and exact algebras in the variety associated to the considered equational theory. We prove that the generality poset of a problem and its type (i.e., the cardinality of a complete set of least general solutions) can be studied in this algebraic setting. Moreover, we identify a class of varieties where the study of the generality poset can be fully reduced to the study of the congruence lattice of the 1-generated free algebra. We apply our results to varieties of algebras and to (algebraizable) logics. In particular we obtain several examples of unitary type: abelian groups; commutative monoids and commutative semigroups; all varieties whose 1-generated free algebra is trivial, e.g., lattices, semilattices, varieties without constants whose operations are idempotent; Boolean algebras, Kleene algebras, and Gödel algebras, which are the equivalent algebraic semantics of, respectively, classical, 3-valued Kleene, and Gödel-Dummett logic. Finally, we prove that the variety of MV-algebras, the equivalent algebraic semantics of Lukasiewicz logic, has nullary type.

math.LO · cs.LO

版本更新 · v2arXiv:1912.00012

Negative Translations for Affine and Lukasiewicz Logic

Rob Arthan, Paulo Oliva

原文摘要

We investigate four well-known negative translations of classical logic into intuitionistic logic within a substructural setting. We find that in \emph{affine logic} the translation schemes due to Kolmogorov and Gödel both satisfy Troelstra's criteria for a negative translation. On the other hand, the schemes of Glivenko and Gentzen both fail for affine logic, but for different reasons: one can extend affine logic to make Glivenko work and Gentzen fail and {\it vice versa}. By contrast, in the setting of \emph{Łukasiewicz logic}, we can prove a general result asserting that a wide class of formula translations including those of Kolmogorov, Gödel, Gentzen and Glivenko not only satisfy Troelstra's criteria with respect to a natural intuitionistic fragment of Łukasiewicz logic but are all equivalent.

cs.LO · math.LO

新论文 · v1arXiv:2610.39776

Solving quantified constraint satisfaction problems with applications to control

Éric Goubault, Nuwan Herath Mudiyanselage, Sylvie Putot

原文摘要

Many problems in control can be expressed as quantified constraints, such as robust forward and backward reachability, synthesis of controllers, solutions to motion planning problems. In this paper, we develop a method for computing inner and outer approximations of global solutions to very general quantified constraints, generalizing widely the state of the art on similar problems, usually restricted to at most one alternation of quantifiers or to local solutions. By global solutions, we mean characterizing accurately the entire set of solutions, within some prescribed bounds. For this, our approach uses a set inversion technique relying on oracles for set inclusion using local solutions to related quantified reachability problems. We exemplify the approach throughout the paper on different examples related to control problems.

cs.LO

新论文 · v1arXiv:2610.39774

Step Recursion: Exact Membership Spectra, Mixed Strides, and Collapse

Kirill Osipov

原文摘要

For a strictly increasing $G:\mathbb{N}\to\mathbb{N}$ with $G(0)\geq 1$, we study minimal-basis function algebras generated by recursion along generalized inverses of its iterates. Bounded recursion requires an earlier pointwise majorant; unbounded recursion has no such requirement. If the orbit $G^{[t]}(0)$ has no polynomial upper bound, we obtain exact fixed-function membership spectra, reverse-divisibility inclusion, and indexed intersections that need not be single-stride algebras. Every finite divisibility-downset is realized in both regimes, and mixed strides admit fixed functions expressing any finite monotone Boolean condition on their additive stride monoid. For every generator, the realized bounded spectra form a bounded meet-semilattice: a construction sharing a bounding input coordinate realizes finite intersections without an unrestricted selector. Polynomial orbit growth is equivalent to definability of each of ordinary predecessor, unary doubling, and addition in any fixed unbounded stride algebra. In this case the algebra is ordinary primitive recursion relative to its inverse map, giving full collapse for primitive-recursive $G$. Ordinary predecessor belongs to a bounded stride algebra exactly when the orbit is polynomially bounded and $G$ has bounded successive differences; equivalently, ordinary bounded recursion embeds. A locality obstruction explains the additional bounded requirement, and two primitive-recursive generators with quadratic orbits have opposite bounded collapse behavior.

cs.LO · math.LO

新论文 · v1arXiv:2610.39746

Step Recursion: Rational Strides and Exact Inclusion Orders over the Reals

Kirill Osipov

原文摘要

We study finite-terminating, address-only step recursion on the nonnegative reals, from zero, unit successor and projections. For reduced positive rational strides $s=a/q$ and $t=b/v$, we prove $\mathcal{C}s\subseteq\mathcal{C}t$ if and only if $q$ divides $v$, for both the bounded and unbounded algebras $\mathcal{C}\in{\mathcal{B},\mathcal{U}}$. The bounded compiler preserves earlier global majorants on every auxiliary input. Mixed rational stride sets are classified by least common denominators and supernatural denominators. Primitive-recursive translated-coordinate grid codes characterize the unbounded algebras and yield $\mathcal{U}{1/q}\cap\mathcal{U}{1/v}=\mathcal{U}{1/\gcd(q,v)}$. For bounded intersections, we prove an exact reduction: all corresponding identities hold if and only if the single identity $\mathcal{B}{1/2}\cap\mathcal{B}_{1/3}=\mathcal{B}_1$ holds, equivalently if the Boolean parts of the integer successor and addition algebras under scalar bounded recursion coincide. A Boolean reconstruction reduces general functions to predicates; a clipped fine-grid simulation with a frozen global resource bound identifies the union of predicate precision classes with the addition level. These reductions do not decide the resulting predicate equality, so literal bounded intersections remain unresolved. We also prove that unbounded-program equality is $Π^0_1$-complete and extensional bounded-algebra membership is $Σ^0_2$-complete. The model has no free real arithmetic or Zeno limits; semantic majorant validity is distinguished from syntax transformation.

cs.LO · math.LO

版本更新 · v2arXiv:2609.27392

Handling Complex Interference Compositionally: A Concurrent Garbage Collector Case Study

Nisansala P. Yatapanage

原文摘要

Rely/Guarantee is a well-known verification technique for reasoning about concurrent programs. However, for some algorithms, devising suitable rely and guarantee conditions is challenging, due to the strong interference exhibited in these algorithms. The Ben-Ari concurrent garbage collector is an algorithm where the complex interactions between the components prevent the construction of compositional rely and guarantee conditions. This paper investigates an approach for verifying the Ben-Ari algorithm, which enables reasoning to be performed in a more compositional manner in cases where compositional reasoning would not otherwise be possible. This is accomplished by reasoning that a given property holds for all instances of a particular variable and then instantiating the variable to the local variable required. As well as providing a reasoning approach which is more compositional, the result is the identification of the core property required of a component, thus enabling a deeper understanding about the reasons why the algorithm works correctly. This helps to reveal the reasons why the rely/guarantee approach does not work directly for some problems.

cs.LO

新论文 · v1arXiv:2610.39735

From the Transformer to a Formal Semantics of Coordinated Transformations

Marco Giunti, Fabrizia Giulia Garavaglia

原文摘要

We develop a formal semantics for a general class of coordinated systems of parameterized transformations, taking the Transformer as a paradigmatic starting point but abstracting from its particular mathematical instantiation. Representational vectors receive both extensional reference and ordered intensional interpretations, while parameter structures acquire relative, second-level interpretations that determine how argument properties are preserved, replaced, or combined. This yields the notion of a transforming concept: a parameterized transformation whose numerical action is coordinated with a corresponding property-level map. We then distinguish the common algebraic-semantic core of these systems from their architecture-specific functional organization, allowing different mathematical instantiations and mechanical realizations of the same abstract system type. The framework is applied to attention heads and residual connections, providing semantic explanations that depend only on the shared algebraic-semantic core and their local functional organization and therefore generalize beyond the standard Transformer. These analyses also reveal the modularity of the framework: complex architectures can be decomposed into simpler semantically coordinated subsystems whose organization may recur across different abstract system types.

cs.AI · cs.CL · cs.LO

版本更新 · v3arXiv:2607.01671

Self-Referential $K$-SAT and the Finite Analogue of Gödel's Incompleteness Theorem

Wen Fang, Xianxian Li, Jun Liu, Jie Luo, Yongxin Tong, Ke Xu

原文摘要

We study self-reference and solution independence in Boolean $K$-SAT as a finite analogue of Gödel incompleteness. Independence is defined through factorial moments of the solution count. Constant-width random formulas fail this criterion due to correlations among overlapping assignments. At a covering threshold, logarithmic-width random CNFs have a Poisson solution count, with positive probabilities of unsatisfiability and unique satisfiability. Replacing a redundant clause by one falsified by the unique solution yields an unsatisfiable companion preserving the unsigned incidence graph. For every permitted local view of a good uniquely satisfiable formula, an unsatisfiable companion preserves that view. Irreducibility defeats deterministic and bounded-error evaluators using $N^c$ clause queries, for fixed $0<c<1$. It establishes a local information obstruction, not an unrestricted time lower bound. For fixed $δ>0$, transcripts of $N^{1-δ}$ queries leave $N-o(N)$ bits of witness entropy. On typical support graphs, expansion yields linear Resolution width, linear PC/PCR and SOS degree, and exponential proof size. Bounds hold for semantic Cutting Planes under a partition condition and for Positivstellensatz with bounded product width, uniformly over unsatisfiable support-preserving signings. Structural evidence and the limits of acceleration strategies motivate the self-referential $K$-SAT exhaustive-search hypothesis (SRK-ESH): no uniform deterministic algorithm deciding the promise family achieves a fixed proportional saving in the exponent. This dual-evidence criterion combines intrinsic hardness mechanisms with algorithmic evidence. We interpret this hypothesis as a quantitative projection of the Gödel-style local--global gap. The information obstruction constrains quantum local observation and statistical learning from bounded local information.

cs.CC · cs.DS · cs.IT · cs.LO

新论文 · v1arXiv:2610.39723

Countable Nondeterminism in Weighted Programming with an Application to Mechanized Foundations for Probabilistic Program Verification

Sebastian Körner, Oliver Emil Bøving, Christoph Matheja

原文摘要

Weighted programming is a framework by Batz et al. for describing mathematical models or optimization problems as imperative programs parametrized over semirings and then analyzing them with program verification techniques like weakest precondition calculi. Applications include reasoning about expected outcomes of probabilistic programs and competitive analysis of online algorithms. We extend weighted programming with (1) countable nondeterminism and (2) user-defined additive rewards, where programs are parametrized over modules instead of semirings. The resulting framework enables reasoning about expected resource consumption of probabilistic programs and about optimal scores of combinatorial games. A technical challenge is that wp-calculi for weighted programs with (1) and (2) over arbitrary modules can be unsound, because it is well-known that continuity properties commonly used in program semantics break in the presence of countable nondeterminism. We study conditions under which a wp-style transformer for reasoning about weighted programs is sound with respect to an operational ground truth defined in terms of weighted decision processes (WDPs) - transition systems that generalize Markov decision processes by drawing transition weights and state rewards from a module. Based on those conditions, we show that a range of concrete instances of the weighted programming framework enjoy sound weakest precondition reasoning. We demonstrate the usefulness of our wp-semantics through case studies for different modules. We mechanized our extended weighted programming framework and our main soundness results in the interactive theorem prover Lean. Instantiating these results for probabilistic programming yields, to the best of our knowledge, the first mechanized proof of a fixed point characterization of minimal expected rewards in Markov decision processes with countable nondeterminism.

cs.PL · cs.LO

新论文 · v1arXiv:2610.39678

Tree Equivalence of Higher-Order Recursion Schemes Is Undecidable

Mingkun Xiao, Yixuan Sun

原文摘要

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

cs.FL · cs.LO

版本更新 · v4arXiv:2602.12446

Model checking with temporal graphs and their derivative

Binh-Minh Bui-Xuan, Florent Krasnopol, Bruno Monasson, Nathalie Sznajder

原文摘要

Temporal graphs are graphs where the presence or properties of their vertices and edges change over time. When time is discrete, a temporal graph can be defined as a sequence of static graphs over a discrete time span, called lifetime, or as a single graph where each edge is associated with a specific set of time instants where the edge is alive. For static graphs, Courcelle's Theorem asserts that any graph problem expressible in monadic second-order logic can be solved in linear time on graphs of bounded tree-width. We propose the first adaptation of Courcelle's Theorem for monadic second-order logic on temporal graphs that does not explicitly rely on a parameter proportional to the lifetime, or defined as the maximum number of time-edges incident with any vertex which in the worst case is higher than the lifetime. We then introduce the notion of derivative over a sliding time window of a chosen size, and define the tree-width and twin-width of the temporal graph's derivative. We exemplify its usefulness with meta-theorems with respect to a temporal variant of first-order logic. The resulting logic expresses a wide range of temporal graph problems including a version of temporal cliques, an important notion when querying time series databases for community structures.

cs.DS · cs.LO

版本更新 · v5arXiv:2603.03971

No Certificate, No Categorical Speech Act: A Brouwerian Assertibility Constraint for Public Reason

Michael Jülich

原文摘要

Generative AI can convert uncertainty into authoritative-seeming verdicts, displacing the justificatory work on which democratic epistemic agency depends. As a corrective, I propose a Brouwer-inspired assertibility constraint for responsible AI: in high-stakes domains, systems may assert or deny claims only if they can provide a publicly inspectable and contestable certificate of entitlement; otherwise they must return Undetermined. This constraint yields a three-status interface semantics (Asserted, Denied, Undetermined) whose statuses mark entitlement to categorical speech rather than truth values of the underlying world-claim. The framework distinguishes internal entitlement from public standing while connecting them through the certificate as a boundary object. Philosophically, it develops a form of applied intuitionism: resistance to unwarranted completeness becomes a norm of public machine speech, under which categorical commitment requires exhibited and contestable entitlement. I operationalize the constraint through structured certificates, decision-layer gates for threshold and argmax predicates, and a reason-coded output contract. A design lemma shows that, under a refutation-soundness condition on the contractually specified negative side, certificate-sound binary totality presupposes witnessed decidability on the declared scope. Under the proposed normative output contract, Undetermined is not a tunable reject option but a mandatory status whenever the available certificates do not uniquely license assertion or denial. By making outputs answerable to contestable warrants rather than confidence alone, the paper aims to preserve epistemic agency where automated speech enters public justification.

cs.CY · cs.AI · cs.LG · cs.LO

新论文 · v1arXiv:2610.39536

Semantic Path Orders are Generalized Weighted Path Orders

Teppei Saito, Nao Hirokawa

原文摘要

Monotonic semantic path orders (MSPOs) are powerful reduction orders, but their effective use in theorem proving and termination analysis raises three issues: efficient comparison of terms, ground totality, and a reduction-pair formulation. Inspired by weighted path orders (WPOs), we introduce generalized weighted path orders (GWPOs) which encompass both WPOs and MSPOs. GWPOs and MSPOs coincide as classes of reduction orders, thereby yielding efficient and ground-total subclasses of MSPOs. We further formulate the reduction-pair version of the GWPO for the dependency pair method, from which a reduction-pair version of the MSPO is obtained. In contrast to the reduction-order setting, the correspondence between GWPOs and MSPOs no longer fully carries over, establishing the GWPO as a framework of independent interest. Effectiveness of the resulting reduction pairs is assessed by standard termination benchmarks.

cs.LO