{"id":"19cbeaec-c377-4894-8312-6921e7778da8","arxiv_id":"2412.07986","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Dual-indeterminate polynomial semirings provide a provenance semantics for full first-order logic with negation, enabling reverse provenance analysis and repair computation.","lead":"This paper gives a way to track how each fact in a database or logical model contributes to the truth of a first-order query, including facts that are absent. The method uses special polynomial semirings with paired positive and negative variables, and it can also explain why a query answer is missing or repair a broken database constraint.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the proof-tree characterization in Theorem 2 is sound within the paper's explicit finite-universe scope, and the reader's ACCEPT verdict stands.","rationale":"The reader flagged finiteness as the weakest assumption; I agree it is the only boundary of the framework, but because it is explicitly stated and standard for database provenance, it does not constitute a load-bearing correctness concern. I also verified the algebra of dual-indeterminate polynomials: the ideal quotient is sound, the universal property (Proposition 10) holds, and the sanity checks around positivity and model-defining interpretations go through. The repair and update results (Propositions 15 and 16) are direct corollaries of Theorem 2 and Corollary 3, and the proofs by specialization are valid. The paper's novelty is lower because much comes from the earlier preprint [28], but the reader already weighed this and accepted; that is a scope and contribution judgment, not a correctness risk. The central claim is therefore well supported, and no verdict adjustment is needed.","tokens_in":54735,"tokens_out":20114,"duration_ms":217535,"concrete_test":"Recompute B[[forall x(P(x) or not P(x))]] on a finite universe A={1,...,n} with B(P(i))=x_i and B(not P(i))=xbar_i. Verify that the expanded polynomial contains exactly 2^n monomials, each with coefficient 1 and with no complementary pair x_i*xbar_i, and that each monomial corresponds to exactly one compatible model in which the sentence holds. This check exercises the universal-quantifier step that Theorem 2 and Corollary 2 depend on most heavily and would expose any hidden issue in the finite distributive-law argument.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I found no internal inconsistency in the central proof-theoretic claim. Theorem 1 is a straightforward induction on NNF; the universal-quantifier case uses the finite distributive law, and the quotient N[X,Xbar] is handled correctly via the normal form that deletes monomials containing complementary tokens. Theorem 2 then specializes Theorem 1 to model-compatible interpretations: a nonzero monomial cannot contain complementary tokens, so it determines a compatible model, and every proof tree of a compatible model specializes to that monomial. Corollary 2's satisfiability/validity criteria follow from this reasoning. The only substantive limitation is that the universe A must be finite; this is explicit in Section 3.1 and is essential for proof trees to have finitely many children under universal quantifiers. For infinite universes the definitions would require infinitary semiring operations, which the paper explicitly excludes. A minor presentational gap is that proof trees are defined only for NNF connectives while Theorem 1 states 'every FO sentence'; the intended reading is proof trees of nnf(psi), which suffices by Proposition 1. This is not a correctness defect.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a semiring provenance semantics for full first-order logic with negation, based on quotient semirings of polynomials with dual indeterminates N[X,Xbar]. It defines S-interpretations over finite universes, proves a fundamental homomorphism property and a sum-of-proof-trees theorem, and then establishes a proof-tree characterization for model-compatible interpretations. From this it derives reverse provenance results, including restricted satisfiability and validity criteria, model specialization, update of provenance polynomials, and methods for explaining missing answers and computing repairs. The paper also surveys subsequent developments in semiring semantics for fixed-point logics, games, and model theory.","tokens_in":54937,"tokens_out":19969,"duration_ms":203519,"significance":"If the central claims hold, the paper fills a long-standing gap by extending provenance analysis from negation-free query languages to full first-order logic. The dual-indeterminate polynomial semiring is a concrete and natural construction, and the paper gives explicit, self-contained proofs of the main theorems plus worked examples showing how to obtain explanations, repairs, and confidence scores. The finite-universe restriction is stated clearly up front, and the proof-tree characterization in Theorem 2 is a strong, falsifiable claim. The paper also gives credit to the surrounding literature and spells out several applications.","major_comments":[{"comment":"As written, Definition 6 does not require that different facts receive different provenance tokens, and §4.2 explicitly contemplates sharing the same token pair across several facts. Under that reading, Corollary 2 is false. Let the universe be {a,b}, let B(P(a)) = B(P(b)) = x and B(¬P(a)) = B(¬P(b)) = xbar, and let ψ = P(a) ∧ ¬P(b). Then B[[ψ]] = x · xbar = 0 in N[X,Xbar], yet the model with P(a) true and P(b) false is compatible with B and satisfies ψ. Thus the criterion 'ψ is Mod_B-satisfiable iff B[[ψ]] ≠ 0' fails. The same issue propagates to Corollary 3 and Proposition 16, where monomial variables are mapped back to individual facts. If the intended convention is that each token pair is reserved for exactly one ground literal, that injectivity condition should be stated explicitly in Definition 6, and the shared-token discussion in §4.2 should be reconciled with it.","section":"§4.1, Definition 6, Corollary 2"}],"minor_comments":[{"comment":"The definition of evaluation trees and proof trees only provides clauses for literals and the connectives ∧, ∨, ∃, ∀, while Theorem 1 is stated for every FO sentence. Please state explicitly that the theorem is applied to nnf(ψ), or extend the tree definition so that the root of an arbitrary FO formula is handled via Proposition 1.","section":"§3.5"},{"comment":"The proof of Proposition 7 is only sketched: the induction measure is not stated and the literal base case is left implicit. Since the result is used to justify the 'consistency' discussion, a short explicit structural induction on NNF would make the argument easier to verify.","section":"§3.4, Proposition 7"},{"comment":"The complexity claims are asserted with 'a simple induction' and 'an examination of the proof' rather than proved. Given that the size model is a stated contribution, please expand these arguments or give precise bounds on the number of monomials.","section":"§4.3, Propositions 12 and 13"},{"comment":"In the paragraph introducing the general model-compatible interpretation, the set 'D+ ∩ D−' appears to be a typo for 'D+ ∪ D−'; as written, the intersection is empty and the definition does not cover the intended updates.","section":"§6"},{"comment":"The notation for complementary tokens is not always consistent in the examples: sometimes a negative literal is annotated with 'x' and sometimes with 'xbar'. Using a uniform bar convention, as in the formal definition in §4.1, would prevent confusion.","section":"§4.2 and §5.1"}],"recommendation":"major_revision","confidential_remarks":"The paper is a substantial contribution and the central proof-theoretic results are convincing. The main issue is the missing injectivity condition on provenance tokens; once that is clarified or enforced, the counterexample to Corollary 2 disappears and the results should hold as intended. I would be happy to accept after that fix and the minor clarifications."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nTrust the reader's ACCEPT. I read it with the same expectations and came away thinking the central theorem holds and the exposition is mostly clean.\n\nWhat's new: the dual-indeterminate polynomial semiring and the proof-tree summation theorem trace to the authors' own 2017 preprint [28], so the paper is honest about being a revised and expanded version. The real additions are the model-compatible interpretation machinery (Section 5.2), the specialization/corollary that connects provenance to model satisfaction, and the repairs/updates application in Sections 6-7, especially Proposition 16. Those extensions are proved in the text and they genuinely tie together a line of work that was previously scattered.\n\nThe main theorem (Theorem 2) is proved by induction on NNF, with the finite-universe restriction explicit where it is used. The quotient by complementary-token products is handled correctly, and the proof-tree reading of monomials checks out. Proposition 16's repair characterization is a straightforward consequence of Theorem 2 and the proof is sound.\n\nSoft spots:\n\n- Novelty is limited. The core ideas are in [28] and the repair material in [42]. The authors admit this. The value is in consolidation, expansion, and the useful survey of follow-up work.\n- Proposition 7's proof is sketched. It's a minor gap, not a correctness issue.\n- Theorem 1 says \"every FO sentence\" but proof trees are only defined for NNF connectives. The intended reading is nnf(psi), which Proposition 1 justifies. Presentational slip.\n- The finite-universe condition is essential and acknowledged; infinite structures need infinitary semirings. Scope limit, not a flaw.\n\nCitation pattern is honest: heavy self-citation, but deserved because the work is a direct continuation.\n\nThis is for database provenance researchers and semiring semantics people. A serious referee should engage with it because the proofs of Theorem 2 and Proposition 16 deserve that check. Verdict matches the reader's: accept with minor revisions.\n\nSend to peer review.","headline":"Solid consolidation of the authors' own 2017 framework; the proof-tree semantics and repair machinery are genuinely useful, novelty is limited but the paper earns a serious referee.","tokens_in":55457,"tokens_out":2750,"would_cite":true,"duration_ms":26384,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03B70","68P15"],"pacs":[],"model":"deepseek-v4-flash","headline":"Full first-order logic gains a provenance semantics: every sentence maps to a polynomial that catalogs its proof trees.","keywords":["provenance semantics","semiring semantics","first-order logic","negation","dual indeterminates","proof trees","reverse provenance","database repairs"],"falsifier":"Choose a finite model-compatible interpretation, enumerate all evaluation trees of a sentence by brute force, and compare the coefficient of each monomial in $\\mathcal{B}[\\![\\psi]\\!]$ with the number of distinct proof trees using exactly those tracked literals; any mismatch would refute Theorem 2.","tokens_in":54522,"feed_emoji":"🧮","tokens_out":9413,"duration_ms":77513,"temperature":0.7,"pith_summary":"This paper extends semiring provenance, the practice of annotating data items with algebraic values so that a query's output tracks which input facts it depends on, from positive query languages to full first-order logic with negation. The key move is to evaluate sentences in a quotient semiring of polynomials whose indeterminates come in positive-negative pairs, with each token and its dual forced to multiply to zero. For any sentence and any model-compatible annotation of literals, the resulting polynomial lists every proof tree that verifies the sentence: each monomial stands for a family of distinct proof trees, and the polynomial is zero exactly when no proof tree exists. If this is right, model-checking with negation can be analyzed with the same tools that worked for positive queries, and the same polynomials support reverse provenance, explanations of missing answers and integrity-constraint failures, and repair computation.","feed_headline":"Negation joins provenance: FO sentences map to proof-tree polynomials","feed_subtitle":"Polynomials with paired positive and negative tokens enumerate every proof tree, enabling explanations and repairs.","key_machinery":"The central object is the semiring $\\mathbb{N}[X,\\bar X]$ of dual-indeterminate provenance polynomials: multivariate polynomials over two disjoint token sets $X$ and $\\bar X$ in one-to-one correspondence, quotiented by $x\\cdot\\bar x=0$ for each complementary pair. A model-compatible interpretation annotates each literal with its own token, with 1 for facts accepted freely, or with 0 for absent facts, and never uses a token and its dual inconsistently for the same fact. The value of a sentence is built by interpreting disjunction and existential quantifiers as sums, conjunction and universal quantifiers as products over the finite universe, and negation by conversion to negation normal form. Theorem 1 — the value of any sentence equals the sum of the valuations of its evaluation trees — is what turns these polynomials into a complete census of proof trees, with dual tokens canceling exactly the trees that would rely on contradictory premises.","core_discovery":"On the paper's own terms, the central claim is Theorem 2: for any model-compatible interpretation $\\mathcal{B}$ mapping literals to dual-indeterminate polynomials over paired tokens, and any first-order sentence $\\psi$, the value $\\mathcal{B}[\\![\\psi]\\!]$ describes all proof trees that verify $\\psi$ using premises that $\\mathcal{B}$ maps to tokens or to 1. Each monomial $c\\,x_1^{a_1}\\cdots x_k^{a_k}$ corresponds to $c$ distinct proof trees using the annotated literals with the indicated multiplicities, and $\\mathcal{B}[\\![\\psi]\\!]\\neq 0$ iff some proof tree exists. From this the paper derives Corollary 2: $\\psi$ is $\\mathrm{Mod}_{\\mathcal{B}}$-satisfiable iff $\\mathcal{B}[\\![\\psi]\\!]\\neq 0$, and $\\psi$ is $\\mathrm{Mod}_{\\mathcal{B}}$-valid iff $\\mathcal{B}[\\![\\neg\\psi]\\!]=0$. Specializing $\\mathcal{B}$ to a particular model $\\mathfrak{A}$ — setting to zero the tokens of literals false in $\\mathfrak{A}$ — recovers the provenance of ordinary model-checking, while the unspecialized polynomial supports reverse analysis: each monomial identifies models compatible with the annotations that satisfy $\\psi$, and solving $\\mathcal{B}[\\![\\neg\\psi]\\!]=0$ yields repairs that make a failed query answer or integrity constraint true.","pith_inferences":["If Theorem 2 holds, the same dual-indeterminate construction should transfer to any logic whose semantics is compositional over conjunction, disjunction, and quantifiers with negation in normal form, such as modal logics or description logics; the paper mentions such extensions elsewhere, and this is a direct extrapolation rather than a claim it tests.","The repair mechanism implicitly defines a cost-aware repair-selection procedure: once the model-compatible interpretation is fixed, choosing among repairs by tropical or Viterbi valuations is a single homomorphism evaluation, which suggests a practical pipeline for inconsistent databases that the paper illustrates but does not develop into an algorithm with guarantees.","The finiteness restriction is the real boundary of the theorem: on infinite universes the quantifier clauses would require infinitary semiring operations, so the proof-tree summation would need a different algebraic setting; the paper points to such extensions in related work, but the main claim here is finite-structure only."],"forward_implications":["Full first-order logic, not just positive fragments, gets a uniform semiring provenance semantics, with negation handled without flattening to Boolean truth.","The monomials of $\\mathcal{B}[\\![\\psi]\\!]$ give a complete account of which combinations of positive and negative facts support the truth of $\\psi$, and how many distinct proof trees each combination supports.","Reverse provenance becomes a by-product: $\\mathcal{B}[\\![\\psi]\\!]\\neq 0$ decides satisfiability within the class of models compatible with the tracking assumptions, and $\\mathcal{B}[\\![\\neg\\psi]\\!]=0$ decides validity within that class.","Missing query answers and integrity-constraint failures can be explained by the monomials of the provenance of the negated query, and minimal repairs are obtained by solving $\\mathcal{B}[\\![\\neg\\psi]\\!]=0$, with costs or confidences then compared in other semirings.","Provenance can be updated after insertions and deletions by specializing one model-compatible polynomial, rather than recomputing from scratch."],"supporting_citations":[{"why":"supplies the original semiring provenance framework for positive query languages that this paper extends to negation.","marker":"[33]"},{"why":"is the earlier preprint by the same authors that first proposed the dual-indeterminate approach for first-order model checking and is the basis of this expanded version.","marker":"[28]"},{"why":"relates semiring valuations to game strategies and proves Sum-of-Strategies theorems, giving the proof-tree viewpoint used in Theorem 1.","marker":"[29]"},{"why":"addresses semiring semantics on infinite universes via infinitary operations, which marks the boundary of the finite-universe assumption essential here.","marker":"[11]"},{"why":"provides an earlier treatment of explanations for missing answers and integrity repairs that Section 7 develops into the repair method by solving provenance equations.","marker":"[42]"}],"fun_headline_variants":["Full first-order provenance: proof trees become polynomials with dual tokens","Polynomials track every proof tree in full first-order logic, negation included","Negation no longer breaks provenance: FO semantics via dual-indeterminate polynomials","Reverse provenance: polynomials with paired tokens explain missing answers and repairs","Proof-trace polynomials crack negation: full FO logic gets semiring provenance"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The framework assumes a finite universe: quantifiers are evaluated as finite sums and products, so Theorem 2, reverse provenance, and repairs are stated for finite structures only.","fun_headline_variants_meta":{"raw":{"variants":["Full first-order provenance: proof trees become polynomials with dual tokens","Polynomials track every proof tree in full first-order logic, negation included","Negation no longer breaks provenance: FO semantics via dual-indeterminate polynomials","Reverse provenance: polynomials with paired tokens explain missing answers and repairs","Proof-trace polynomials crack negation: full FO logic gets semiring provenance"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000229,"raw_usage":{"total_tokens":1514,"prompt_tokens":1018,"completion_tokens":496,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":634,"completion_tokens_details":{"reasoning_tokens":402}},"tokens_in":634,"tokens_out":496,"duration_ms":5637,"temperature":1.0,"reasoning_tokens":402,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T18:20:09.882581+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Choose a finite model-compatible interpretation, enumerate all evaluation trees of a sentence by brute force, and compare the coefficient of each monomial in $\\mathcal{B}[\\![\\psi]\\!]$ with the number of distinct proof trees using exactly those tracked literals; any mismatch would refute Theorem 2.","supporting_citations":[{"cited_title":"Green, G","cited_arxiv_id":null,"evidence_quote":"supplies the original semiring provenance framework for positive query languages that this paper extends to negation."},{"cited_title":"Provenance Analysis for Logic and Games","cited_arxiv_id":"1907.08470","evidence_quote":"relates semiring valuations to game strategies and proves Sum-of-Strategies theorems, giving the proof-tree viewpoint used in Theorem 1."},{"cited_title":"Brinke, E","cited_arxiv_id":null,"evidence_quote":"addresses semiring semantics on infinite universes via infinitary operations, which marks the boundary of the finite-universe assumption essential here."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"provides an earlier treatment of explanations for missing answers and integrity repairs that Section 7 develops into the repair method by solving provenance equations."}],"review_version":1}