跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+197新增论文
+151其中 AI 相关
+16已有论文修订
+91新增 AI 导读

arXiv 最近完成扫描:2026-11-21 12:19 · 全站最近入库:2026-11-21 12:19各信源进度 →

统计口径与数据新鲜度

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

最近完成检查:2026-11-21 12:19最近发现新增版本:2026-11-21 12:19库内论文最新更新时间:2026-11-20 02:59

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

29,158 已收录论文24,181 AI 相关8,992 有修订112 HF 社区发现

浏览论文库

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

找到 367 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-21 12:17(北京时间)
版本更新 · v2arXiv:2606.26525

Theory-Scale Auto-Formalization of Logic for Computer Science

Yuming Feng, Frederick Pu, One An, Osbert Bastani, Li Zhang, Jiani Huang, Xujie Si, Ziyang Li

原文摘要

Auto-formalization is critical for scalable formal verification, but existing progress largely focuses on isolated statements, while theory-scale auto-formalization, which coherently translates hundreds of interdependent definitions, lemmas, and theorems, remains open due to challenges in consistency, faithfulness, scalability, and correctness. In this paper, we introduce LCS-Bench, a stand-alone, theory-scale benchmark based on Logic for Computer Science. LCS-Bench is built through a novel semi-automated agentic pipeline that leverages concept graphs, formal signature planning, issue tracking, sorry-filling with counter-example search, complemented by faithfulness review from human experts. The resulting artifact covers 327 textbook items, over 4,076 Lean declarations, and more than 85K lines of Lean code. The dataset supports broad evaluation through a data engine that automatically derives five tracks of evaluation benchmarks, measuring different aspects of auto-formalization and theorem-proving capabilities. We also introduce a novel evaluation protocol featuring definitional equivalence checkers, enabling more fine-grained and faithful assessment. Through extensive evaluation on 17 models, we demonstrate that (1) LCS-Bench is of high quality, consistent, and faithful; (2) the benchmark is challenging, with state-of-the-art models achieving only 20.3% on auto-formalization tasks; and (3) our analysis reveals key findings regarding theory-scale auto-formalization and suggests promising directions for future work.

cs.LG · cs.LO · cs.PL

新论文 · v1arXiv:2611.22010

On Formal Counterfactual Explanations

Alexey Ignatiev, Peter J. Stuckey, Joao Marques-Silva

原文摘要

Counterfactual explanations are often seen as counterfactual conditionals under closest-world semantics, requiring one to reason over all minimally distant counterexamples. In contrast, formal XAI typically relies on feature-based abductive explanations (AXps) and contrastive explanations (CXps), which admit efficient computation and a minimal hitting-set duality. This paper bridges these perspectives by (i) characterizing closest-world counterfactual explanations explicitly as a disjunctive normal form over all minimally distant counterexample instances, and (ii) introducing conjunctive counterfactual explanations (CFXps), a subclass of counterfactual antecedents restricted to conjunctions of feature literals that guarantee prediction change. The paper establishes structural results connecting CXps, AXps and CFXps: every CXp induces an AXp for its witness instance, and every CXp together with a witness AXp induces a CFXp whose support is precisely determined by that AXp. These theoretical results yield a modular approach for computing CFXps using existing AXp/CXp machinery. Experiments on a representative set of benchmarks using tree ensembles and neural networks show that CFXp extraction is practically efficient. Compared with popular point-based counterfactual explainers, CFXps generally require no more feature changes and can guarantee the counterfactual prediction beyond a single instance.

cs.AI · cs.LG · cs.LO

新论文 · v1arXiv:2611.21826

Logical Relations on Display

Steven Schaefer, Johnson He, Max S. New

原文摘要

The metatheory of programming languages suffers from a lack of reuse. Researchers develop individual calculi and prove standard properties, but very few results are truly reused across papers. The problem is worse in proof assistants, where developments routinely duplicate code from prior work or rebuild it from scratch. Category theory provides the most promising path toward reusable programming language semantics. Universal properties capture the type connectives---products, functions, sums---together with their $β$/$η$ laws. Free categorical structures identify syntactic calculi. \emph{Displayed} categories provide a uniform language for specifying logical relations, and general theorems about fibrations allow their structure to be assembled compositionally. In this work we develop a library of formalized category theory in the Cubical Agda proof assistant directly applicable to programming language metatheory. We develop theories of universal properties and free categorical structures, apply them to define denotational semantics and logical relations for simply typed calculi, and identify encodings of the categorical constructions that make typechecking them tractable. From the same categorical components, we construct several familiar results via a logical relations construction---canonicity,parametricity,conservativity---and provide a proof of coherence for monoidal categories.

cs.PL · cs.LO

新论文 · v1arXiv:2611.21599

Hyperlyve: Parallelized Enumeration and Exact Lyapunov Stability Certification for Deep ReLU Networks

Brian Yarbrough, Jesse Wayment, Jingbo Wang, Philip E. Paré, Shreyas Sundaram

原文摘要

We introduce Hyperlyve (Hyperplane Partitioned Lyapunov Verification and Enumeration), a framework for proving the asymptotic stability of nonlinear dynamical systems, including those with neural network controllers. Hyperlyve learns and formally certifies continuous piecewise-affine (CPA) neural Lyapunov functions within a counterexample-guided inductive synthesis (CEGIS) loop. Hyperlyve's key innovation is a parallel algorithm that enumerates the hyperplane arrangement formed by the ReLU activations of deep networks and certifies that Lyapunov conditions hold within each polyhedral region. We derive sound and complete regional tests to verify the asymptotic stability of the exact smooth dynamics (rather than a piecewise-linear approximation) within a compact domain of interest. Furthermore, we formally characterize the computational complexity of the CPA neural Lyapunov verification problem as co-NP-complete, filling a key gap in the literature. Empirical results demonstrate that Hyperlyve enumerates ReLU networks over 150-times faster than competing tools, which contributes to Hyperlyve proving the asymptotic stability of systems that are currently intractable for state-of-the-art verifiers.

eess.SY · cs.CG · cs.LG · cs.LO · math.DS

版本更新 · v2arXiv:2611.15992

The multiplicative complexity of the three-bit low-half multiplier

Bshara Alhodali, Gregory Morse

原文摘要

We prove that the multiplicative complexity of the three-bit low-half multiplier is six, giving a structural, enumeration-free lower-bound proof valid against unrestricted nonlinear reuse in Boolean XOR-AND circuits. The value was first established by SAT searches of the first author and independently confirmed by the second author. An explicit six-AND circuit supplies the upper bound. The lower bound combines derivatives, quadratic products, complementary minors, and extraction modulo a Boolean ideal. Independent finite checks accompany the arguments. $\mathrm{MC}(M_3)=6$ is fully formalized in Lean 4, using only Lean's three standard axioms (propositional extensionality, choice and quotient soundness).

cs.CC · cs.LO · math.CO

新论文 · v1arXiv:2611.21402

Harmonic-Mean Aggregation of Continuous-Time Markov Chains with Reachability Error Bounds

Bingqing Hu, Landon Taylor, Zhen Zhang

原文摘要

Abstracting a continuous-time Markov chain by grouping its states into blocks raises a fundamental question: which rates should the abstract chain use when states within a block have different exit rates and transition probabilities? We study harmonic-mean aggregation, which matches the mean waiting time and next-block distribution of a local experiment that uniformly selects a state within the block and observes its next jump. Equivalently, the abstract transition rates are averages of the concrete rates with inverse-exit-rate weights. Since the aggregation does not preserve reachability probabilities in general, we derive theoretical error bounds for time-bounded reachability. We decompose the error into a blockwise mean and centered-within-block deviations, and show that the rate mismatch has zero weighted mean. Exploiting this cancellation and differences between abstract reachability values, we obtain bounds valid at every time horizon through a linear comparison system with two quantities per block, without computing concrete reachability values. All results are formalized and proven in Lean 4.

cs.LO

版本更新 · v2arXiv:2506.14307

Non-Wellfounded and Labelled Sequent Calculi for Bimodal Provability Logics

Justus Becker

原文摘要

Bimodal provability logics are modal logics where the two modalities are interpreted as two formal provability predicates of arithmetic theories. We present modular labelled calculi for four different bimodal provability logics, whose rules arise from the relational semantics of these logics, while the second-order property of Noetherianity of models is enforced using techniques from cyclic proof theory. Completeness with respect to the semantics is established via proof search and countermodel construction. We further present regular and finite variants of the calculi via proof transformations.

cs.LO · math.LO

新论文 · v1arXiv:2611.21375

Proceedings Eighth International Workshop on Formal Methods for Autonomous Systems

Matt Luckcuck, Maike Schwammberger, Akhila Bairy

原文摘要

This EPTCS volume contains the papers from the Eighth International Workshop on Formal Methods for Autonomous Systems (FMAS 2026), which was held on the 17th and 18th of November 2026. FMAS 2026 was co-located with the 27th International Conference on Formal Engineering Methods (ICFEM), and hosted at the Leonardo Royal Grand Harbour Hotel in Southampton.

cs.LO · cs.AI

版本更新 · v3arXiv:2510.10189

Formally Verified Certification of Unsolvability of Temporal Planning Problems

David Wang, Mohammad Abdulaziz

原文摘要

We present an approach to unsolvability certification of temporal planning. Our approach is based on encoding the planning problem into a network of timed automata, and then using an efficient model checker on the network followed by a certificate checker to certify the output of the model checker. Our approach prioritises trustworthiness of the certification: we formally verify our implementation of the encoding to timed automata using the theorem prover Isabelle/HOL and we use an existing certificate checker (also formally verified in Isabelle/HOL) to certify the model checking result.

cs.LO · cs.AI

版本更新 · v2arXiv:2607.23798

Interpolation via Generalized Splitting

Lutz Straßburger

原文摘要

We propose a new proof theoretical method for proving Lyndon interpolation. Our proof does not use the sequent calculus but is based on a generalization of the splitting lemma in deep inference. We then formulate the interpolation theorem as a decomposition of a derivation into an up-fragment and a down-fragment. This can be seen as (i) a strengthening of the standard formulation of the interpolation theorem, and (ii) a generalization of the cut elimination theorem. We demonstrate the flexibility of our approach by applying it to linear logic, classical logic, and modal logics. For this, we also introduce novel cut-free proof systems for several modal logics in deep inference.

cs.LO

新论文 · v1arXiv:2611.21287

Connecting Extended Modal Dependence Logics

Johan van Benthem, Chenwei Shi, Wenfei Ouyang

原文摘要

We consider three natural extensions of the basic decidable dependence logic LFD, adding, respectively, conditional dependence atoms, independence atoms, and identity atoms between variables. We show that these systems are all connected to first-order logic with identity by SAT reductions and in several cases also faithful translations. In particular, this implies that all these extended modal-style dependence logics are undecidable. This solves a number of problems left open in the original publication [1] introducing the LFD framework. The definitions and proofs presented here were found by ChatGPT and checked and streamlined as needed by the authors. At the end, we provide some discussion of what new things we learnt about dependence logics and about the methodology of using AI in logical research.

cs.LO

版本更新 · v2arXiv:2611.14783

A Multi-Prover Interactive Protocol for Certification of Resolution Refutations

Philipp Czerner, Adrian Krauss, Josia Pietsch, Javier Esparza

原文摘要

A resolution refutation of a SAT-formula $\varphi$ is an independently checkable certificate proving that $\varphi$ is unsatisfiable. However, the refutations of $\varphi$ can be exponentially larger than $\varphi$. So, a verifier needs worst-case exponential time in the size of $\varphi$ to check their correctness. We present ResCertify, an interactive probabilistic protocol in which the verifier interacts with multiple independent, untrusted provers (MIP) to check the refutation with very low probability of error. The verifier runs in linear time in the size of $\varphi$. The provers require time $\mathcal{O}(n \cdot |Φ|)$, where $Φ$ is the resolution refutation and $n$ is the number of variables of $\varphi$. If they can be trusted to act as a multilinear oracle on certain queries, a single prover suffices, and the runtime can be improved to $\mathcal{O}(|Φ|)$. Finally, while the focus of our work is theoretical, we also report on a proof-of-concept implementation of ResCertify.

cs.LO

版本更新 · v6arXiv:2405.15647

A Logic of Knowledge and Justifications, with an Application to Computational Trust

Francesco A. Genco

原文摘要

We present a logical framework that enables us to define a formal theory of computational trust in which this notion is analysed in terms of epistemic attitudes towards the possible objects of trust and in relation to existing evidence in favour of the trustworthiness of these objects. The framework is based on a quantified epistemic and justification logic featuring a non-standard handling of identities. Thus, the theory is able to account for the hyperintensional nature of computational trust. We present a proof system and a frame semantics for the logic, we prove soundness and completeness results and we introduce the syntactical machinery required to define a theory of trust.

cs.LO

新论文 · v1arXiv:2611.21157

Going Deep Inside Public Announcement Logic

Clara Lerouvillois, Lutz Straßburger

原文摘要

Dynamic Epistemic Logic (DEL) is a family of logics that extend Epistemic Logic by adding dynamic modalities to the language, which represent communication and yield updates of knowledge. Among its various systems, Public Announcement Logic (PAL) provides a simple and interesting framework to analyse how knowledge gets updated through public communication. While its semantics has been extensively studied, its proof-theory remains more fragmented. In particular, the structural analysis of the announcements and their composition is yet to be refined. Deep inference naturally appears as well suited proof formalism when it comes to decompose formulas from the inside. It also offers a formalism with less syntax, that dispenses with bureaucracy. This paper presents the first deep inference proof system for PAL, using the formalism of open deduction. We show soundness, completeness, and cut admissibility for the new system.

cs.LO

版本更新 · v2arXiv:2607.12226

Flex: A Foundational Proof-Producing Horn Solver

Jam Kabeer Ali Khan, Petros Markopoulos, Niki Vazou, Nico Lehmann, Ranjit Jhala

原文摘要

Constrained Horn Clauses (CHCs) are a versatile intermediate representation for program verification, but leading CHC solvers rely on SMT-based reasoning over supported background theories. Specifications involving user-defined recursive functions or bespoke operators can require additional semantic encodings and reasoning beyond these theories. We observe that CHCs are existentially quantified propositions in a foundational logic, and so can be proved within an interactive theorem prover, where specifications can use native definitions, and users can complete proofs when automation stalls. However, in a foundational setting, every Horn variable solution must be justified by a kernel-checked proof. We present Flex, a proof-producing CHC solver implemented as a Lean metaprogram, that combines predicate synthesis with proof construction. Flex comprises a suite of tactics: Zap, which synthesizes strongest predicates for acyclic Horn variables and exploits their structure to construct elimination proofs without any proof search; Fix, which uses predicate abstraction over templates built from arbitrary Lean terms, discovered by scraping the CHCs and associated definitions, to infer inductive invariants for cyclic Horn variables; and a certifying pipeline that keeps external SMT-based solvers like Spacer and Eldarica outside the trusted computing base. We use Flex to verify the functional correctness of sorting algorithms, hash tables, ring buffers from the Tock OS kernel, and Rust std library challenges. We show that Zap constructs elimination proofs 28.2x and 44.6x faster than grind and aesop, respectively. With Zap and Fix, Flex automatically proves 98.0% of the refinement-typechecker CHCs in our evaluation.

cs.PL · cs.LO · cs.SE

新论文 · v1arXiv:2611.21084

CompCert4Lean: Porting a Verified C Compiler to Lean in Six Weeks with Parallel Coding Agents

Cong Wang, Zhiyang Chen, Fan Long, Martin Rinard

原文摘要

We present CompCert4Lean, a large-scale port of CompCert 3.17's verified compiler core from Rocq to Lean, completed in approximately six weeks by one expert directing parallel LLM agents. Our migration workflow partitions the development along its dependencies, audits translated definitions and theorem statements before large-scale proof reconstruction, and then reconstructs proofs in parallel against stable interfaces. The resulting compiler covers typed CompCert C through x86-64 assembly, discharges all 4,908 recorded proof obligations without project-specific axioms, and produces executable Linux binaries. The workflow enabled the expert to concentrate on organizing the work rather than supplying technical solutions. Of 1,071 human interactions, 88.8% concerned workflow and coordination, while only three supplied technical direction. Optimization campaigns further demonstrate the benefit of the Lean port for agent-driven verified development. Under matched budgets of 24 active hours, GPT-6-astra produced a Lean candidate with 11.7% lower generated-program runtime across 29 small-tests programs, compared with 2.3% lower for its Rocq candidate, both relative to original CompCert 3.17 and while preserving the end-to-end correctness theorem. These results show that parallel LLM agents can support large-scale migration with limited human technical direction and subsequently improve the migrated compiler while retaining its formal guarantees.

cs.PL · cs.LO

版本更新 · v2arXiv:2611.00153

On Small Universal Reversible Turing Machines

T. Yokoyama

原文摘要

A reversible Turing machine (RTM) is a Turing machine in which every instantaneous description has at most one predecessor. Writing $\mathrm{URTM}(m,n)$ for a universal RTM with $m$ states and $n$ symbols, we construct $\mathrm{URTM}(3,600)$, $\mathrm{URTM}(4,38)$, $\mathrm{URTM}(5,36)$, $\mathrm{URTM}(6,28)$, $\mathrm{URTM}(7,26)$, $\mathrm{URTM}(8,21)$, $\mathrm{URTM}(9,8)$, $\mathrm{URTM}(10,7)$, and $\mathrm{URTM}(85,2)$; each of them has fewer states or fewer symbols than each of the nine URTMs in Morita's book (2017). Most of them come from improved versions of Morita's conversions to three states, to four states, and to two symbols; for example, the improved conversion to three states uses $O(mn^2)$ symbols instead of $O(m^2n^3)$. $\mathrm{URTM}(10,7)$ comes from merging two states of Morita's $\mathrm{URTM}(13,7)$, recording the difference in tags on the tape cells, and then merging symbols, three times; one more such step gives $\mathrm{URTM}(9,8)$. We also show that the halting problem of RTMs with at most two states is decidable for finite instantaneous descriptions, so that no RTM with at most two states is universal under any notion of universality that reduces the halting problem of Turing machines to it by a computable encoding into finite instantaneous descriptions; in particular, there is no URTM with at most two states in our formalization of Morita's definition. We also show that no three-state, two-symbol RTM is universal in that formalization.

cs.FL · cs.LO

版本更新 · v3arXiv:2209.15035

Double negation stable h-propositions in cubical sets

Andrew W. Swan

原文摘要

We give a construction of classifiers for double negation stable h-propositions in a variety of cubical set models of homotopy type theory and cubical type theory. This is used to give some relative consistency results: classifiers for double negation stable propositions exist in cubical sets whenever they exist in the metatheory; the Dedekind real numbers can be added to homotopy type theory without changing the consistency strength; we construct a model of homotopy type theory with extended Church's thesis, which states that all partial functions with double negation stable domain are computable.

math.LO · cs.LO

新论文 · v1arXiv:2611.20943

From Strong Normalization to WhatsApp: the Journey of an Axiom

Giuseppe Castagna

原文摘要

Twenty years ago, Mariangiola Dezani-Ciancaglini, Daniele Varacca and I showed that Milner's classic encoding of functions into processes does not respect one of the laws of intersection types, the one stating that $(σ\toτ)\land(σ\toρ)$ is a subtype of $σ\to(τ\landρ)$, which Barendregt, Coppo and Dezani-Ciancaglini had stated in 1983 for their filter $λ$-model. In this essay I show that this observation is the key to closing what a colleague at Meta calls ``the main typing gap in Erlang''---the language in which the servers of WhatsApp are written: the type of the function that implements a server is not related to the type of the server, so that a client may expect from the server a reply that the server will never send. Actually, closing this gap is just an excuse to follow the journey of the law above, and of some of its relatives, from the study of strong normalization in the $λ$-calculus to the type systems of Elixir and Erlang: a journey that shows how much the practical typing of these languages owes to the work of Mario Coppo, Mariangiola Dezani-Ciancaglini and Simona Ronchi Della Rocca, to whom this essay is dedicated for their eightieth birthdays.

cs.PL · cs.LO

新论文 · v1arXiv:2611.20845

Tight Width Minimisation of Self-Join-Free Quantified Conjunctive Queries

Hubie Chen, Fabio Mogavero, Sam M. Thompson

原文摘要

Query minimisation is a classical problem in database theory and the width of a formula, defined as the maximum number of free variables over all subformulae, is a central measure for query evaluation. We study width minimisation for a subclass of quantified conjunctive queries (QCQs), namely self-join-free QCQs. For this subclass, we show that rewriting optimality coincides with semantic optimality: given a query $φ$, the minimum-width query obtainable from $φ$ by applying natural and established rewriting rules has minimum width among all first-order formulae logically equivalent to $φ$. As a consequence, the width of a self-join-free QCQ can be optimised by a logical-equivalence-preserving rewriting algorithm.

cs.DB · cs.LO

版本更新 · v2arXiv:2408.05033

Approximate Distributed Monitoring under Partial Synchrony: Balancing Speed and Accuracy

Borzoo Bonakdarpour, Anik Momtaz, Dejan Ničković, N. Ege Saraç

原文摘要

In distributed systems with processes that do not share a global clock, \emph{partial synchrony} can be achieved by clock synchronization that guarantees bounded clock skew among all processes. Existing solutions for distributed runtime verification under partial synchrony against temporal logic specifications are exact but suffer from significant computational overhead. In this paper, we propose an \emph{approximate} distributed monitoring algorithm for Signal Temporal Logic (STL) that mitigates this issue by abstracting away potential interleaving behaviors. This conservative abstraction enables a significant speedup, albeit with a tradeoff in precision. We address this tradeoff by combining our approximate monitor with its exact counterpart, gaining efficiency without sacrificing precision. Our framework supports \emph{offline} monitoring of both future and past STL, as well as \emph{online} monitoring of past STL. We evaluate our approach with multiple experiments, showcasing its efficacy in both real-world applications and synthetic examples.

cs.LO

新论文 · v1arXiv:2611.20781

Verification-Guided Safety-Repair of Learned Controllers

Fabian Kresse, Sobhan Gharanfoli, Nikolaus Vertovec, Alessandro Abate, Thomas A. Henzinger, Christoph H. Lampert

原文摘要

Formal verification can certify that a learned controller is safe. But what should be done when verification fails? Simply suppressing actions that lead to unsafe next states is insufficient because the dangerous action that ultimately caused the safety violation might have occurred many steps earlier. Retraining modifies the policy globally, thereby potentially introducing new failures. Instead, we introduce ReachECO, a verification-guided repair procedure that exploits the information of failed multi-step reachability analysis for synthesizing explicit constraints on controller behavior. For Differentiable Weightless Controllers, the repairs compile into exact circuit patches that leave the controller unchanged everywhere outside the targeted policy cells. We prove soundness and termination of the repair procedure for ReachECO, as well as, assuming exhaustive continuation search, completeness relative to the reachability abstraction. Empirically, we demonstrate \method's ability to successfully repair otherwise unsafe controllers in three continuous-control benchmarks: ACC, Docking2D and Car2D.

cs.LO · eess.SY

新论文 · v1arXiv:2611.20517

Postselection on Halting and Reductions to the Halting Problem

Saman Farhat, Farzad Didehvar

原文摘要

A probabilistic Turing machine is an ordinary Turing machine that may also toss fair coins, with no limit on its running time or memory. If it always halts, it decides only computable problems. Aaronson et al. studied machines that may run forever on some coin tosses, with the answer read only from the runs that halt. Suppose the correct answer must be more than twice as likely as the wrong one. They showed that these machines decide exactly the problems solvable with a fixed list of questions about the halting problem. They asked what happens when the correct answer need only be the more likely one. We show that the machines then decide exactly the problems solvable by asking such questions one after another, each chosen after the earlier answers. We also show that the factor two can be replaced by any fixed factor greater than one. A machine may promise two numbers: a lower bound on its probability of halting, and a lower bound on its probability of being right when it halts. From these two numbers we compute exactly how many questions fixed in advance the machine can replace. The main idea is that probability acts as a budget for how often a computable guess may change its mind. The results extend to oracle machines and to machines nested inside each other. Quantum machines decide the same problems.

cs.CC · cs.LO · math.LO · quant-ph

新论文 · v1arXiv:2611.20453

Taint Analysis via Heap-Aware Propagation

Yusen Su, Jorge A. Navas, Arie Gurfinkel

原文摘要

Taint analysis for C depends on how precisely the analysis tracks tainted values as they flow through memory objects. Without field sensitivity, a tainted object field can spuriously taint an entire object, producing significant false alarms. In this paper, we present a field-sensitive taint analysis that combines Data Structure Analysis (DSA) for field-sensitive points-to information with a data-flow analysis for tracking explicit dependencies. We identify that existing DSA-style analyses lose precision on a common object pattern: a C struct object that mixes scalar fields with a flexible array member. When such an array is accessed with symbolic indices, DSA loses points-to field sensitivity for the entire object, inflating false alarms in the data-flow analysis. To address this, we propose I-DSA, which extends DSA by representing field positions as intervals, so that a pointer with symbolic bounds merges only the fields within those bounds. We further develop a sound data-flow analysis based on abstract interpretation. We implement I-DSA on top of SeaDSA and the data-flow analysis inside Crab. Our tool targets LLVM IR and supports configurable taint policies by instrumenting the IR with taint intrinsics. Our experiments show that I-DSA reduces the false alarms caused by this pattern at little cost in the pointer analysis, that SVF, an inclusion-based pointer analysis, shows a similar field-sensitivity loss, and that our taint analysis scales better than PhASAR on real-world programs.

cs.LO · cs.CR · cs.PL

版本更新 · v6arXiv:2603.03971

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

Michael Jülich

原文摘要

Suppose a citizen asks a reliable AI chatbot whether a cabinet secretary engaged in serious corruption. What entitles the chatbot to answer yes or no? Drawing on Brouwer's account of constructive assertion, I argue that categorical machine speech in high-stakes domains requires an auditor-checkable and publicly contestable certificate of entitlement. Citizens expected to rely on a verdict must be able to identify and challenge the grounds on which it is issued. This requirement yields three statuses -- licensed assertion, licensed denial, and Undetermined -- that mark entitlement to categorical speech, not truth. Undetermined is neither a truth-value gap nor a tunable reject option. A design lemma shows what eliminating the third status would cost. Under stated assumptions, an interface that certifies a verdict in every case by establishing or refuting its deployed predicate provides a witnessed decision procedure on its declared scope. Where no such procedure is available, a certificate-sound interface cannot guarantee a categorical verdict for every case. I defend an output contract that keeps unsettled cases within scope and requires Undetermined whenever the available certificates fail to license exactly one side. In the corruption case, the citizen can accept a committee's finding that payments bought favorable lease terms and still ask why the materiality threshold is set at $500,000. The contract makes that choice explicit, and the certificate records how it is applied. Responsibility for defending the threshold remains with the institutions that set it, not with the machine.

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

版本更新 · v2arXiv:2603.29921

Quantale-Enriched Co-Design: Toward a Framework for Quantitative Heterogeneous System Design

Hans Riess, Yujun Huang, Matthew Klawonn, Gioele Zardini, Matthew Hale

原文摘要

Monotone co-design enables compositional engineering design by modeling components as feasibility relations between required resources and provided functionalities. However, its boolean formulation cannot natively represent quantitative criteria such as cost, confidence, or implementation choice. In practice, these considerations are introduced through ad-hoc scalarization or by augmenting the resource space, which obscures system structure and increases computational complexity. Therefore, we develop a quantale-enriched theory of co-design in which resources and functionalities are quantale-enriched categories and design problems are quantale-enriched profunctors, which lifts co-design from boolean feasibility to quantitative evaluation. Series, parallel, and feedback composition remain valid over any commutative quantale, and change-of-base maps between quantales yield heterogeneous composition, so that subsystems evaluated in different local semantics can be composed in a common framework. Numerical examples on a target-tracking system and a UAV delivery problem demonstrate this framework and show how it avoids the drawbacks of boolean-only formulations.

eess.SY · cs.LO · math.CT · math.OC

版本更新 · v4arXiv:2410.13508

Formalizing Hyperspaces and Operations on Subsets of Polish Spaces over Abstract Exact Real Numbers

Michal Konečný, Sewon Park, Holger Thies

原文摘要

Building on our prior work on axiomatization of exact real computation by formalizing nondeterministic first-order partial computations over real and complex numbers in a constructive dependent type theory, we present a framework for certified computation on hyperspaces of subsets by formalizing various higher-order data types and operations. We first define open, closed, compact and overt subsets for generic spaces in an abstract topological way that allows short and elegant proofs with computational content coinciding with standard definitions in computable analysis and constructive mathematics. From these proofs we can extract programs for testing inclusion, overlapping of sets, et cetera. To enhance the efficiency of the extracted programs, we then focus on Polish spaces, where we give more efficient encodings based on metric properties of the space. As various computational properties depend on the continuity of the encoding functions, we introduce a nondeterministic version of a continuity principle which is natural in our formalization and valid under the standard type-2 realizability interpretation. Using this principle we further derive the computational equivalence between the generic and the metric encodings. Our theory is fully implemented in the Coq proof assistant. From proofs in this Coq formalization, we can extract certified programs for error-free operations on subsets. As an application, we provide a function that constructs fractals in Euclidean space, such as the Sierpinski triangle, from iterated function systems using the limit operation. The resulting programs can be used to draw such fractals up to any desired resolution.

cs.LO

版本更新 · v3arXiv:2610.37534

Computing GR(1) Assume-Guarantee Contracts

Yigit Narter, Emily Zhao, Inigo Incer

原文摘要

Assume-guarantee contracts provide a set of algebraic operations that enable the efficient compositional design and analysis of complex engineering systems. The explicit computation of these operations at component interfaces is currently supported only for some logics lacking a notion of time. This paper develops theory and algorithms to compute these operations when the contracts are expressed in the GR(1) modulo theory. The key challenge is the computation of two quantifier elimination problems for temporal formulas. We develop context-aided variable elimination procedures on GR(1)-modulo formulas, establish their soundness, characterize subproblem-wise optimal solutions within an admissible class of formulas, and use the procedures to compute contract operations, including composition and quotient. We implement the resulting framework in Pacti, automating compositional reasoning over GR(1) contracts. Finally, we demonstrate the framework on an automated emergency-braking case study, where we compute system-level contracts and expose compatibility conditions arising from the interaction of component specifications. Experiments on synthetic families show that the cost is governed by the number of eliminated variables and liveness conjuncts, and a comparison with exact automata-based elimination shows complementary scaling.

cs.LO · eess.SY

版本更新 · v3arXiv:2609.25556

Pointwise provable equality and the failure of composition

Florian Lengyel

原文摘要

In their studies of pathologies in recursion categories, Montagna (1989) and Di Paola--Montagna (1991) introduce the algebraic systems $S'$ and $S'_T$, respectively, and claim that they are categories. We show that the proposed composition is not independent of the choice of representatives. For every consistent recursively enumerable extension $T$ of Peano arithmetic ($\mathrm{PA}$), we exhibit two unary programs whose partial functions are provably equal in $T$, separately at each standard input. Composing each after a program that searches for a $T$-proof of contradiction and returns its code yields programs that are not equivalent in this sense. An alternative proof uses the productivity of the complement of the diagonal halting set. Montagna's $S'$ is the case $T=\mathrm{PA}$. More generally, for consistent $T\supseteq\mathrm{PA}$, pointwise provable equality is a composition congruence exactly when $T$ proves every true $Π^0_1$ sentence, in which case it is extensional equality. This completeness condition fails for every consistent recursively enumerable $T\supseteq\mathrm{PA}$ by Gödel's second incompleteness theorem. For every extension $T\supseteq\mathrm{PA}$, the least composition congruence containing pointwise provable equality is extensional equality if $T$ is $Σ^0_1$-sound and the universal relation otherwise.

math.LO · cs.LO

新论文 · v1arXiv:2611.19736

Coalgebra for True Concurrency

Yong Wang

原文摘要

We give the coalgebra for true concurrency along the way paved by traditional coalgebra based on bisimulation. This coalgebra is based on truly concurrent bisimulation, and we give its definition and a simple truly concurrent process algebra.

cs.LO