ZX-Calculus:Trace-Indexed Dependent Types and Epistemic Semantics

• URL: http://arxiv.org/abs/2606.03063v1
• Date: Tue, 02 Jun 2026 02:51:41 GMT
• Title: ZX-Calculus:Trace-Indexed Dependent Types and Epistemic Semantics
• Abstract summary: We propose ZX-Calculus (Knowledge Evolution Calculus), a conservative extension of Martin-Lof Dependent Type (MLTT)<n>It integrates trace-indexed types, presheaf non-monotone semantics, and constructive AGM belief revision.<n>A Coq mechanisation accompanies the paper (34 complete proofs; zero admits for the two central results)
• Score: 3.848983210046659
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We propose ZX-Calculus (Knowledge Evolution Calculus), a conservative extension of Martin-Lof Dependent Type Theory (MLTT) integrating trace-indexed types, presheaf non-monotone semantics, and constructive AGM belief revision. A Coq mechanisation accompanies the paper (34 complete proofs; zero admits for the two central results). (I) Trace types. FinTrace(s0,sn) is an inductive family of typed execution traces. FinTrace and Star(Step) are isomorphic as path types but not judgementally equal; TraceElim exposes the event label e:Event explicitly, giving a more ergonomic interface for event-driven induction. We prove the Trace-Reachability Correspondence, Deterministic Replay, and a canonicity framework via reducibility candidates with a Transport Lemma (RC-elim deferred; all other Core results are Coq-verified). (II) Sheaf semantics. Trace-indexed propositions are contravariant sheaves over the free trace partial-order category Tf. A Separation Theorem (explicit countermodel) distinguishes proof-theoretic monotonicity from semantic non-monotonicity. The term model is an initial CwF (syntactic universal property, not classical completeness). (III) AGM belief revision. We give an explicit constructive partial meet contraction algorithm verified against (C1)-(C4). All eight AGM postulates (R1)-(R8) are theorems. Proofs of R7 and R8 use the Disjunctive Entrenchment Lemma, given a self-contained constructive derivation. (IV) Integration. B^AGM fails the sheaf composition law BP-comp for sequential revision (explicit countermodel, Coq-verified). We introduce Single-Step Revision Systems (SSRS), prove B^AGM is a valid SSRS (Coq-verified), and show this suffices for trace morphisms, retraction characterisation, and revision witnesses. The BP-comp failure reveals a fundamental tension between path-dependent belief revision and functor consistency, not previously identified.

Related papers

• Reasoning Shortcuts and Value Symmetries: What Symmetry Permits, Architecture Realizes, and Optimization Selects [10.012788934490084]
  Reasoning shortcuts are solutions of a neurosymbolic system's rules that produce correct predictions through unintended concepts.<n>A recent framework of Takemura, Inoue, and Nishino analyzes them through an automorphism group of value relabelings.<n>We first show that the framework's key definition, one shared permutation applied at every position, does not apply as stated to any of the four benchmarks it was evaluated on.
  arXiv  Detail & Related papers  (2026-08-11T03:10:20Z)
• Intrinsic Structure: Spectral Identifiability for Mechanistic Interpretability [51.56484100374058]
  We prove the first identifiability theorem for a mechanistic-interpretability primitive.<n>The spectrum is an identifiable, model-intrinsic fingerprint with a stated error bar, not a legible decomposition.
  arXiv  Detail & Related papers  (2026-08-10T19:42:01Z)
• LC-ERD: Mining Latent Logic for Self-Evolving Reasoning via Consistency-Regulated Reward Decomposition [55.572260012037084]
  We introduce LC-ERD (Logic-Consistent Endogenous Reward Decomposition), a framework framing self-alignment as latent structure mining.<n>We derive a Variational Logic Potential by aggregating consensus from the model's Latent Logic Expertise.<n>Experiments show LC-ERD delivers a robust self-evolution path, uncovering trade-offs between logic consistency and accuracy.
  arXiv  Detail & Related papers  (2026-05-19T07:27:50Z)
• NOETHER: A Constructive Framework for Metamorphic Pattern Discovery from Operator Algebras [6.691613382732758]
  Metamorphic Testing is recognised in IEEE/ISO software-testing standards and increasingly recommended for AI systems.<n>Existing approaches share an inductive grounding that leaves three foundational questions open.<n>We propose a framework whose downstream step from operator algebra to MetaPattern set is mechanical and provable.
  arXiv  Detail & Related papers  (2026-05-17T11:18:35Z)
• Probing Structural Mathematical Reasoning in Language Models with Algebraic Trapdoors [0.0]
  We introduce a benchmark suite for evaluating structural mathematical reasoning in language models.<n>Each instance presents a finitely generated subgroup as a list of integer matrices.<n>We report empirical results across five representative reasoning traces from two state-of-the-art models.
  arXiv  Detail & Related papers  (2026-05-05T23:16:30Z)
• Mechanized Foundations of Structural Governance: Machine-Checked Proofs for Governed Intelligence [0.0]
  We present five results in the theory of structural governance for cognitive workflow systems.<n>Three are in Coq 8.19 using the Interaction Trees library with mechanizedized coinduction; two are proved on paper with explicit reductions.<n>A sixth contribution connects the abstract model to the deployed runtime: the Verified Interpreter Specification.
  arXiv  Detail & Related papers  (2026-04-30T01:03:15Z)
• Shorthand for Thought: Compressing LLM Reasoning via Entropy-Guided Supertokens [4.0704009036918025]
  Reasoning in Large Language Models incurs significant inference-time compute.<n>We show that reasoning tokens split into two functional types: low-entropy textitstructural tokens (recurring phrases that scaffold the reasoning process) and higher-entropy textitorganic tokens (problem-specific content that drives toward a solution)<n>We derive textitsupertokens that capture frequent structural patterns, then teach the model to adopt them via supervised fine-tuning.
  arXiv  Detail & Related papers  (2026-04-29T07:06:43Z)
• Formally Verified Patent Analysis via Dependent Type Theory: Machine-Checkable Certificates from a Hybrid AI + Lean 4 Pipeline [0.0]
  We present a formally verified framework for patent analysis as a hybrid AI + Lean 4 pipeline.<n>The DAG-coverage core (Algorithm 1b) is fully machine-verified once bounded match scores are fixed.<n>Claims are encoded as DAGs in Lean 4, match strengths as elements of a verified complete lattice, and confidence scores propagate through dependencies via proven-correct monotone functions.
  arXiv  Detail & Related papers  (2026-04-20T22:02:57Z)
• LiveMathematicianBench: A Live Benchmark for Mathematician-Level Reasoning with Proof Sketches [61.30693283718321]
  We present LiveMathematicianBench, a dynamic multiple-choice benchmark for research-level mathematical reasoning.<n>By grounding evaluation in newly published theorems, it provides a realistic testbed beyond memorized patterns.<n>It employs a proof-sketchguided distractor pipeline that uses high-level proof strategies to construct plausible but invalid answer choices.
  arXiv  Detail & Related papers  (2026-04-02T08:22:17Z)
• ARCHE: A Novel Task to Evaluate LLMs on Latent Reasoning Chain Extraction [70.53044880892196]
  We introduce a novel task named Latent Reasoning Chain Extraction (ARCHE), in which models must decompose complex reasoning arguments into combinations of standard reasoning paradigms in the form of a Reasoning Logic Tree (RLT)<n>To facilitate this task, we release ARCHE Bench, a new benchmark derived from 70 Nature Communications articles, including more than 1,900 references and 38,000 viewpoints.<n> Evaluations on 10 leading LLMs on ARCHE Bench reveal that models exhibit a trade-off between REA and EC, and none are yet able to extract a complete and standard reasoning chain.
  arXiv  Detail & Related papers  (2025-11-16T07:37:09Z)
• DAG-Math: Graph-Guided Mathematical Reasoning in LLMs [54.231935013127206]
  Large Language Models (LLMs) demonstrate strong performance on mathematical problems when prompted with Chain-of-Thought (CoT)<n>We propose modeling CoT as a certain rule-based process over directed acyclic graphs (DAGs)<n>We introduce logical closeness, a metric that quantifies how well a model's CoT trajectory adheres to the DAG structure.
  arXiv  Detail & Related papers  (2025-10-19T21:05:17Z)
• Prototype-based Aleatoric Uncertainty Quantification for Cross-modal Retrieval [139.21955930418815]
  Cross-modal Retrieval methods build similarity relations between vision and language modalities by jointly learning a common representation space. However, the predictions are often unreliable due to the Aleatoric uncertainty, which is induced by low-quality data, e.g., corrupt images, fast-paced videos, and non-detailed texts. We propose a novel Prototype-based Aleatoric Uncertainty Quantification (PAU) framework to provide trustworthy predictions by quantifying the uncertainty arisen from the inherent data ambiguity.
  arXiv  Detail & Related papers  (2023-09-29T09:41:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.