{"id":"bbb5b4f5-10c7-45e7-b699-0c33c5115b6a","arxiv_id":"2510.08127","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Probabilistic membership for context-free languages is in PTIME for unambiguous and poly-slicewise-unambiguous languages, #P-hard for some unions of two linear unambiguous CFLs, and tractable via complement-capable circuits for primitive words and PAL2.","lead":"This paper introduces a new counting question: given a probabilistic word, compute the probability that a word drawn from it belongs to a fixed context-free language. It maps which language classes make this problem tractable or #P-hard, and develops circuit techniques that extend tractability to primitive words and concatenations of two palindromes.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Claim 5.5's OBDD for L3 tests a-pairs at index distance k, while the defined L3 places n letters between the a's (index distance n+1); the circuit does not capture L3 as written.","rationale":"The reader's conditional verdict focuses on the unproved external Lemma 6.10 behind PAL2. That is a legitimate concern, but I found a more immediately verifiable internal inconsistency in Claim 5.5, which is the paper's key example that tractable circuits strictly generalize poly-slicewise-unambiguous languages. The language L3 as written has n letters between the two a's, so the index difference is n+1. The OBDD in Claim 5.5 checks index difference n (or k in the formal proof). The length-4 example shows a concrete mismatch: 'abba' is in L3 but rejected by the circuit, and 'baaa' is accepted by the circuit but not in L3. This means Claim 5.5 does not establish what it claims for the language as defined. Because the example is small and the intended fix is plausible, this does not overturn the paper's broader program, but it strengthens the case for a conditional verdict and requires a correction to either the language definition or the circuit construction. I therefore leave the reader's CONDITIONAL verdict unchanged.","tokens_in":33430,"tokens_out":26078,"duration_ms":201385,"concrete_test":"Take input length 4 and run the construction of Claim 5.5 (n=4, k=2). Inspect S(C): it accepts 'baaa' (positions 2 and 4 are a) and rejects 'abba' (neither pair (1,3) nor (2,4) has both a's). Compare with L3 as defined: for total length 4 the definition gives a (a+b)^2 a, so 'abba' is in L3 and 'baaa' is not. If the construction is corrected to check pairs (i, i+n+1), the mismatch disappears; but as written the claimed circuit does not capture L3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 5's only example showing that tractable circuits strictly generalize poly-slicewise-unambiguity is L3 (Claim 5.5). The definition L3 = {(a+b)^k a (a+b)^n a (a+b)^{n-k-2}} places n letters between the two a's, so the a-positions differ by n+1. The OBDD in Claim 5.5, however, tests pairs (i, i+n); in the proof, with input length 2k, it tests (i, i+k), i.e., index distance k (k-1 letters between). For input length 4, L3 contains 'abba' (a's at positions 1 and 4), but the constructed circuit rejects it; conversely it accepts 'baaa' (a's at positions 2 and 4), which is not in L3. Thus the circuit captures a different language (two a's at index distance n), not the L3 actually defined. Since this is the paper's evidence that tractable circuits go beyond poly-slicewise-unambiguity, Claim 5.5 as written is unsupported. This is an internal inconsistency, not merely a missing external proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces and studies the probabilistic membership problem for context-free languages: given a probabilistic word (a sequence of per-position distributions over an alphabet) and a fixed language L, compute the total probability that a random word drawn from the product distribution belongs to L. The authors establish a complexity landscape: the problem is in polynomial time for unambiguous CFLs (Proposition 3.1); it is #P-hard for some unions of two linear uCFLs (Proposition 3.6); it is tractable for the newly introduced class of poly-slicewise-unambiguous languages, covering bounded CFLs and unambiguous polynomial-time counter automata; it remains #P-hard for some nondeterministic one-counter/Parikh automata. The paper then introduces tractable ×,⊎-circuits and ×,⊎,∁-circuits from knowledge compilation, claiming these strictly generalize poly-slicewise-unambiguity, and uses them to prove tractability for primitive words (Proposition 6.4) and for the concatenation of two palindromes PAL2 (Theorem 6.9). Finally, it claims a conditional undecidability result for the meta-problem of deciding, from a CFG, whether the corresponding #pM problem is tractable or #P-hard (Proposition 7.1). The body gives proof sketches, with detailed proofs in the appendices.","tokens_in":33740,"tokens_out":13004,"duration_ms":114478,"significance":"If the main claims were established, this would be a valuable contribution to the complexity of weighted counting for context-free languages, connecting formal-language theory with knowledge compilation. The positive results for uCFLs (via a weighted CYK-style dynamic program), the #P-hardness reductions via PP2DNF and Turing-machine runs, the poly-slicewise-unambiguous framework, and the circuit constructions are well-motivated and largely coherent. The paper also gives explicit polynomial-time algorithms for primitive words and PAL2 that go beyond what follows from unambiguity, and it identifies a natural class (poly-slicewise-unambiguity) that unifies several otherwise disparate tractable cases. The detailed appendix is a strength. However, as detailed below, several load-bearing points are currently not correct as written: Claim 5.5's circuit mismatch for L3, a non-constructive step in Proposition 7.1's undecidability reduction, and a disjointness error in the PAL2 circuit construction. These issues affect the paper's headline claims and need to be repaired.","major_comments":[{"comment":"The circuit construction does not capture the language L3 as formally defined. The definition L3 = {(a+b)^k a (a+b)^n a (a+b)^{n-k-2}} places n letters between the two a's, so the two a-positions differ by n+1. The OBDD in Claim 5.5 tests pairs (i, i+n), whose positions differ by n. For input length 4, 'abba' is in L3 (a's at positions 1 and 4) but the constructed circuit rejects it, while 'baaa' (a's at positions 2 and 4) is accepted but not in L3. Thus the circuit captures a different language (two a's at index distance n), not L3 as defined. Since L3 is the paper's only evidence that tractable circuits strictly generalize poly-slicewise-unambiguity, Claim 5.5 as written is unsupported.","section":"Section 5, Claim 5.5"},{"comment":"The proof of tractability for PAL2 relies on a disjoint union that is false. Claim E.6 asserts that M_{n,d,j} is the disjoint union of the L_{n,pd,j mod (n/pd)} sets. This conflates the offset of a decomposition of v (where u = v^d) with the unique offset of the primitive root of u guaranteed by Lemma 6.10. A word in PAL2 may have several decompositions into two palindromes even when its primitive root has a unique one. For example, 'abab' is in M_{4,1,1} (decomposition 'a' + 'bab') and also in M_{4,1,3} (decomposition 'aba' + 'b'), so the claimed disjointness fails. Consequently Equation (3) and the ensuing induction do not establish that PAL2 admits tractable ×,⊎,∁-circuits, and Theorem 6.9 is not supported by the proof given.","section":"Appendix E.4, Claim E.6 / Theorem 6.9"},{"comment":"The proof of conditional undecidability is not a valid reduction as written. In the hardness direction for a non-universal Γ, the reduction is supposed to map an input p for #pM(L0) to the probabilistic word wp, where w is 'an arbitrary word w ∉ L(Γ)'. But such a w is not computable from Γ in general: the reduction is not effective. A many-one reduction must be a computable function of Γ; merely knowing that a witness exists is insufficient. The paper's appeal that 'we do not care about the decidability of picking this constant word' is not acceptable for a complexity-theoretic reduction. The claim may be salvageable, e.g., using Greibach's theorem or a different construction, but the proof as stated does not establish Proposition 7.1.","section":"Appendix F, Proposition 7.1"}],"minor_comments":[{"comment":"The informal phrase 'words of length 2n which contain two occurrences of a at distance exactly n' is ambiguous and is the source of the mismatch in Claim 5.5. If the intended language is the one in the formal definition, the distance (position difference) is n+1; if the intended language is the one captured by the circuit, the formal definition should be changed to place n-1 letters between the two a's.","section":"Section 5"},{"comment":"In the proof of Proposition 3.5, the sentence 'The proof is the same as Proposition 3.5' should refer to Proposition 3.4.","section":"Appendix B.2"},{"comment":"Lemma 6.10 is imported from [53] and is load-bearing for the PAL2 result. Given the extensive use of the unique-decomposition property in the circuit construction, the paper should either state and prove Lemma 6.10 or give a precise citation with the exact statement, as the current proof of Theorem 6.9 depends on it structurally.","section":"Section 6"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper gives a real new problem—probabilistic membership for probabilistic words—and backs it with a serious complexity landscape. The uCFL dynamic program (Prop 3.1), the #P-hardness for unions of two linear uCFLs via run encoding (Prop 3.6), the poly-slicewise-unambiguous framework unifying uCFLs, bounded CFLs, and unambiguous counter automata, and the complement-circuit constructions for primitive words and PAL2 are all substantive. The appendix contains detailed proofs for nearly everything, and the work is free of fitted parameters or empirical post-hoc reasoning. I also agree with the reader that the abstract's combined-complexity claims are backed by actual theorems; that concern did not survive reading the full text.\n\nThe soft spot is real, and it is the one the stress-test flags. Claim 5.5 does not hold as written. The language L3 is defined with n letters between the two a's—positions differ by n+1—but the constructed OBDD tests pairs at index distance n. Concretely, for n=2 the word 'abba' is in L3 (a's at positions 1 and 4), yet the circuit rejects it; the circuit accepts 'baaa' (a's at positions 2 and 4), which is not in L3. So the circuit captures a different language. Since L3 is the only example used to show that tractable circuits strictly generalize poly-slicewise-unambiguity, that strictness claim is currently unsupported. The fix is likely easy—test pairs (i, i+n+1)—but the authors need to either repair the construction or redefine L3 consistently with the cited ambiguity/lower-bound results. The rest of the paper does not depend on this example, so the damage is local, but it is a genuine internal inconsistency, not a missing proof.\n\nThe reader's worry about Theorem 6.9 leaning on Kemp's unique-decomposition lemma is minor; importing a published combinatorial lemma is standard practice and the paper attributes it. That is not a flaw in proportion.\n\nBottom line: this paper deserves a serious referee. The contributions are substantial and mostly rigorous, and the Section 5 issue is repairable. An editor should send it out, but the referee should specifically check Claim 5.5 and the surrounding argument before accepting the circuit hierarchy claim.","headline":"Genuinely new problem and substantial complexity landscape, but the Section 5 example that circuits beat poly-slicewise-unambiguity is broken as written.","tokens_in":34222,"tokens_out":4536,"would_cite":true,"duration_ms":38164,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q45","68Q17","68Q15"],"pacs":[],"model":"deepseek-v4-flash","headline":"For probabilistic words, membership in unambiguous context-free languages is computable in polynomial time, while some mildly ambiguous cases are already #P-hard.","keywords":["probabilistic words","context-free languages","unambiguous grammars","#P-hardness","poly-slicewise-unambiguous","tractable circuits","primitive words","palindrome concatenation"],"falsifier":"A brute-force check on small alphabets (e.g., all words over {a,b} up to length 12) comparing the O(n^3|Σ|) circuit-based count with the true count of the two-palindrome language would falsify the algorithm; a direct refutation would be finding one word in that language whose primitive root splits into palindromes in two distinct ways.","tokens_in":33331,"feed_emoji":"🎲","tokens_out":6902,"duration_ms":55920,"temperature":0.7,"pith_summary":"This paper introduces probabilistic membership: given a word in which each position carries a probability distribution over letters, compute the probability that a randomly drawn word belongs to a fixed language. The paper shows that unambiguity is a broad source of tractability—unambiguous context-free languages are solvable in cubic polynomial time—and introduces a hierarchy of poly-slicewise-unambiguous languages and tractable circuits that extends tractability to some inherently ambiguous languages. It proves that hardness starts very early: the problem is #P-hard already for unions of two linear unambiguous context-free languages, though it remains tractable for bounded CFLs and unambiguous polynomial-time counter automata. The circuit framework, enriched with complementation, yields polynomial-time algorithms for primitive words and concatenations of two palindromes. Finally, assuming FP≠#P, deciding from a grammar whether its probabilistic membership is tractable is undecidable.","feed_headline":"Unambiguous grammars yield fast probabilistic membership","feed_subtitle":"But a union of just two unambiguous linear grammars makes it #P-hard","key_machinery":"The central device is a circuit representation of a language's length slices. A ×,⊎-circuit is a directed acyclic circuit whose ×-gates build Cartesian products over disjoint position domains (decomposable) and whose ⊎-gates build disjoint unions of equal-domain assignment sets (deterministic and smooth); probabilities evaluate in linear time by multiplying at ×-gates and summing at ⊎-gates. Adding ∁-gates, which complement the assignment set of a subcircuit, preserves this linear evaluation and enables inclusion–exclusion constructions. For the two-palindrome language, the key mechanism is a partition of words by the order and offset of their primitive-root decomposition into two palindrome","core_discovery":"The paper's central claim is that probabilistic membership mirrors a grammar's ambiguity structure: with at most one parse tree per word, summing probabilities of derivation trees is exact and runs in polynomial time; once ambiguity is allowed, the problem can become #P-hard, already for a union of two linear unambiguous grammars. The paper develops a circuit calculus—×,⊎-circuits with decomposable products, deterministic disjoint unions, and optional complementation—that represents the length-n slice of a language as a factorized set of assignments, so the desired probability is computed by a single bottom-up pass of multiplications, additions, and complements. This calculus subsumes poly-s","pith_inferences":["The circuit-based criterion suggests a broader measurement: what matters is whether each length-n slice can be represented by a small factorized, disjoint decomposition; this points to knowledge compilation as the natural lens for characterizing tractable languages beyond grammars.","If the uniqueness lemma on primitive roots of two-palindrome words generalizes to longer palindromic factorizations, the same complement-based construction could make PAL3 or palindromic stars tractable; the paper explicitly leaves this open.","The conditional undecidability of the meta-problem hints that any eventual full dichotomy for probabilistic membership would need input beyond the bare grammar—for example, a semantics-preserving normal form or an oracle for ambiguity—rather than a syntactic check.","Because the hardness proofs work even when wildcards are restricted to a two-letter subalphabet, the #P-hardness is intrinsic to counting completions, not an artifact of rich probability values."],"forward_implications":["Probabilistic membership is in PTIME, in fact in O(n^3|Γ|) in combined complexity, for every unambiguous context-free grammar, covering deterministic CFLs and all regular languages.","The problem is #P-hard already for a union of two linear unambiguous CFLs, and also for some languages recognized by nondeterministic one-counter and Parikh automata.","Every poly-slicewise-unambiguous language, including all bounded/polyslender CFLs and languages of unambiguous polynomial-time counter automata, has polynomial-time probabilistic membership.","Languages admitting tractable ×,⊎-circuits or ×,⊎,∁-circuits have polynomial-time probabilistic membership; this class is strictly larger than poly-slicewise-unambiguous languages.","Assuming FP≠#P, the meta-problem of deciding from a linear CFG whether its probabilistic membership problem is tractable is undecidable.","Tractable probabilistic membership for a language implies efficient sampling, enumeration, and ranking in radix order via self-reducibility.","The tractability results extend to complements of the studied languages, because complementation can be handled by subtracting the answer from 1."],"fun_headline_variants":["Unambiguous: P; union of two: #P-hard","One parse tree: P; two parse trees: #P-hard","Counting words: unambiguous easy, ambiguous #P-hard","From P to #P-hard: ambiguity makes counting hard","Union of two unambiguous grammars: #P-hard"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The tractability of the two-palindrome language rests on the imported combinatorial claim that every word in that language has a unique primitive-root decomposition into two palindromes; if that claim ever fails, the partition used by the algorithm double-counts and the polynomial-time guarantee collapses.","fun_headline_variants_meta":{"raw":{"variants":["Unambiguous: P; union of two: #P-hard","One parse tree: P; two parse trees: #P-hard","Counting words: unambiguous easy, ambiguous #P-hard","From P to #P-hard: ambiguity makes counting hard","Union of two unambiguous grammars: #P-hard"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001768,"raw_usage":{"total_tokens":6877,"prompt_tokens":877,"completion_tokens":6000,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":621,"completion_tokens_details":{"reasoning_tokens":5918}},"tokens_in":621,"tokens_out":6000,"duration_ms":36257,"temperature":1.0,"reasoning_tokens":5918,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T10:48:13.419238+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A brute-force check on small alphabets (e.g., all words over {a,b} up to length 12) comparing the O(n^3|Σ|) circuit-based count with the true count of the two-palindrome language would falsify the algorithm; a direct refutation would be finding one word in that language whose primitive root splits into palindromes in two distinct ways.","supporting_citations":[],"review_version":1}