{"id":"e6a3fdfa-1e5d-402e-b51e-a21b8528c739","arxiv_id":"2505.09963","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Anonymity and uniformity of parameterized probabilistic systems can be verified automatically by synthesizing regular bisimulation relations via automata learning and checking them in the decidable theory of regular structures.","lead":"This paper presents a logical framework that verifies probabilistic bisimulation for parameterized systems, that is, infinite families of finite-state probabilistic models, by encoding systems and proofs in the decidable first-order theory of regular structures.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4 is unsound as written: the label sums in Eq. (6) can equate different R-classes, so a non-bisimulation can satisfy Phi.","rationale":"The reader's weakest assumption was the minimal-deviation encoding in Sections II-A and V-C-b. That is a legitimate scope concern, but it is not the most load-bearing issue. The presented Theorem 4 is internally unsound: the bisimulation verification condition in Eq. (6) does not enforce that labels name the same equivalence classes on both sides of the pair (s,s'). My two-state-successor counterexample shows a non-bisimulation that satisfies Phi, so the central characterization and the teacher's equivalence query in Algorithm 2 are both invalid as written. This concern trumps the encoding question because it affects even the simplest finite, natural-weight WTS. The fix is straightforward: add a cross-compatibility conjunct forcing alpha_i = beta_j exactly when R(u_i,v_j), after which the proof strategy goes through. I therefore recommend keeping a CONDITIONAL verdict, but for a more fundamental reason than the reader gave: acceptance should require correcting Eq. (6) and re-checking that the case-study verdicts still follow from the repaired formula.","tokens_in":29485,"tokens_out":9997,"duration_ms":116617,"concrete_test":"Instantiate the sentence Phi of Theorem 4 on the finite WTS with S={s,s',x,y}, a single action a, delta(s,a,x)=delta(s',a,y)=1, and R with equivalence classes {s,s'}, {x}, {y}. Hand-evaluate Eq. (6), or run the formula through MONA: with n=1, the formula returns valid because the labels for x and y can be chosen equal, whereas condition (1) fails for the class {x}. If the formula accepts this non-bisimulation, the theorem's iff claim is refuted.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central iff characterization in Theorem 4 fails because the formula lambda in Eq. (6) labels the successors of s and s' independently. compat(u,alpha) only constrains labels within the u-tuple, and compat(v,beta) only within the v-tuple; no condition links alpha_i with beta_j. Therefore the equality of sums over labels can compare masses of different R-equivalence classes. Concrete counterexample: take a one-action WTS with states {s,s',x,y}, transitions s-a->x and s'-a->y with weight 1 and all other weights 0, and let R be the equivalence relation with classes {s,s'}, {x}, {y}. The branching bound is n=1. R is not a bisimulation: for the class {x}, the mass from s through a is 1, while the mass from s' through a is 0. Yet choosing u=x, v=y, and alpha=beta=(1) makes succ and compat hold vacuously, and the label-1 sums are both 1 while all other label sums are 0. Thus S_R satisfies Phi, contradicting the claimed 'only if' direction. This makes Algorithm 2's equivalence query unsound: it can certify a relation that is not a bisimulation. The flaw is independent of the minimal-deviation assumption and of tool availability; it concerns the main theorem itself. The theorem can be repaired by adding cross-compatibility, e.g. requiring for all i,j that R(u_i,v_j) iff alpha_i=beta_j, but the formula as printed does not include this.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a first-order logical framework, based on the decidable theory of regular structures (FOreg), for verifying probabilistic bisimulation in parameterized systems. The central technical claim is Theorem 4: for every bounded-branching weighted transition system S and binary relation R, there is a fixed FO sentence Φ with S_R |= Φ iff R is a probabilistic bisimulation over S. This theorem is then used to justify an active-automata-learning procedure that synthesizes regular bisimulation relations, which are applied to verify anonymity and uniformity properties of parameterized probabilistic systems. The paper reports a prototype tool and case studies covering dining cryptographers, crowds, grades, random walks and sums, two random number generators, and the ballot theorem.","tokens_in":29806,"tokens_out":8001,"duration_ms":89679,"significance":"If Theorem 4 is correct and the framework is sound, this is a valuable contribution: it gives a unified, decidable proof rule for a class of infinite-state probabilistic verification problems, connects bisimulation proofs with automata learning, and provides automated verification for parameterized protocols and randomized algorithms beyond finite-state model checking. The paper is careful to state undecidability of the general problem and to present the learning procedure as a heuristic with independent verification of candidates. The choice of verification conditions in FOreg and the integration with MONA/TAPAS are concrete and reproducible in principle. However, the central characterization in Theorem 4 is unsound as printed, which invalidates the equivalence-query mechanism in Algorithm 2 and therefore the soundness of the verification procedure as stated.","major_comments":[{"comment":"The formula λ(s,a,s′) labels the successors of s and s′ independently: compat(u,α) constrains only pairs within u, and compat(v,β) constrains only pairs within v. There is no conjunct of the form R(u_i,v_j) ⇔ α_i = β_j, so equality of label sums can compare masses of different R-equivalence classes. Concretely, take the one-action WTS with states {s,s′,x,y}, transitions s→a x and s′→a y with weight 1, and (to make it a Markov chain) x→a x, y→a y with weight 1. Let R have classes {s,s′}, {x}, {y}; the branching bound is n=1. R is not a bisimulation because the mass from s to class {x} is 1 while the mass from s′ to {x} is 0. Yet the formula is satisfied by choosing u=x, v=y, α=β=(1): both succ conditions hold, compat is vacuous, and the label-1 sums are both 1 while all other label sums are 0. Thus S_R |= Φ holds for a non-bisimulation, contradicting the claimed iff. This makes Algorithm 2's equivalence query unsound, since it can certify a relation that is not a bisimulation. The theorem can be repaired by adding a cross-compatibility conjunct, for example ∧_{i,j}(R(u_i,v_j) ⇔ α_i = β_j), and then re-proving both directions; the formula as printed must be corrected before the paper's verification claims can be accepted.","section":"Theorem 4, Eq. (6)"},{"comment":"The extension to parametric probabilities is only sketched: the text defines a set Q of probability parameters, adds an addition operator over Q∪P, and posits axioms such as commutativity, but it gives no formal statement or proof that the resulting proof rule is sound and complete for bisimulation with parametric weights. This is not a cosmetic gap because Section VI-b reports verification of the Crowds protocol, whose transition probabilities involve a parameter p, and says 'We illustrate this extension in our evaluation.' If the crowds result depends on this unproved extension, the case study is not supported by Theorem 4. Please provide a precise definition of the parametric WTS semantics and a correctness theorem for the parametric bisimulation rule, or state explicitly how crowds is handled under the fixed-probability encoding.","section":"Section V-C-b and Section VI-b"},{"comment":"The proof of Theorem 4 requires that, for every state and action, the formula can choose n distinct configurations u_1,…,u_n containing all successors. If the state space has fewer than n distinct elements, no such tuple exists, even though the branching bound n may exceed the state count of a finite instance. The authors should either assume the universe has at least n elements, take n as min(branching bound, |S|), or otherwise handle finite universes explicitly. This is a repairable detail, but it should be stated because the parameterized instances in Section VI are finite.","section":"Theorem 4 proof, succ construction"}],"minor_comments":[{"comment":"Condition (ii), 's0 is bisimilar only to itself with respect to R,' should be written as [s0]_R = {s0} to remove ambiguity; the proof does use this condition to justify the base case p_0(u)=p_0(v).","section":"Theorem 16"},{"comment":"Theorem 4 states decidability 'when both S and R are regular' without repeating the minimal-deviation assumption introduced in Section II-A. Since the encoding of the addition operation + and of probability weights in FOreg depends on that assumption, the theorem statement should explicitly say 'under the minimal-deviation assumption' or 'when + is regular-presentable.'","section":"Section II-A and Theorem 4"},{"comment":"The display of the pPDA rules is garbled in places (for example the line 'dX 0.5 −−→bXX dX 0.5 −−→d b X 1 − →dXX cY 1 − →cXX'). Please reformat the rule notation for readability.","section":"Example 3 / Figure 1"},{"comment":"The box 'Isw∈L(˜R|w|)?' in Figure 2 is unclear, and Algorithm 2's written description of the counterexample case would benefit from an explicit statement that the returned word is v⊗u, matching the symmetric-difference notation used in the learning algorithm.","section":"Algorithm 2 / Figure 2"}],"recommendation":"major_revision","confidential_remarks":"The unsoundness in Theorem 4 is substantial but appears repairable by adding the missing cross-compatibility conjunct and re-proving the two directions. I would ask the authors to make that fix and to re-examine whether Algorithm 2 and the crowds case study are then fully supported; I would not recommend rejection if the repaired theorem and proof are supplied. The parametric-probabilities extension also needs a formal correctness statement before the crowds experiment can be considered evidence."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe one thing to know about arXiv:2505.09963 is that its central theorem, Theorem 4, is unsound as written. The first-order formula Φ that is supposed to characterize probabilistic bisimulation can be satisfied by a non-bisimulation. The stress-test note is correct: in Eq. (6), the labelings α and β are chosen independently for the two sides, and no cross-condition links α_i to β_j. So the equality of label sums can compare masses of different R-equivalence classes. The counterexample works: a one-action WTS with s→x and s'→y, weights 1, R-classes {s,s'}, {x}, {y}, and n=1. Choosing u=x, v=y, α=β=(1) satisfies Φ even though s and s' put different masses on class {x}. That is not a minor gap; Algorithm 2's equivalence query uses Φ to certify bisimulations, so the learning procedure can return a false positive.\n\nWhat is genuinely new is the uniformity verification via bisimulation on the reversed transition system (Theorem 16), the parametric probability sketch, and a creditable set of case studies (dining cryptographers, crowds, grades, random walks, random sums, Knuth-Yao and naive RNGs, ballot theorem) that go beyond the CAV'19 paper. The FOreg encoding idea is attractive, the writing is clear, and Theorems 14 and 16 appear sound on their own, given a genuine bisimulation.\n\nThe soft spots beyond the unsound theorem: no tool is released, so the case-study numbers are not independently checkable; the parametric probability extension is only a sketch; and the minimal deviation assumption is load-bearing, though acknowledged. The reader's take scored soundness 6; I'd put it lower until the main theorem is fixed. The reader's other caveats (tool availability, scoping against [27]) are fair but secondary.\n\nWho is this for? Researchers in probabilistic parameterized verification will want to read it, but as submitted the paper needs major revision. A likely repair is to add a cross-compatibility condition along the lines of R(u_i,v_j) iff α_i=β_j, so label sums compare the same equivalence classes. I'd still send it to a serious referee: the framework is significant and the flaw is identifiable and likely fixable. I would not cite it in the next year, but I'd keep an eye on a revised version.","headline":"Theorem 4 is unsound as printed; the central verification condition can accept non-bisimulations, but the framework and case studies are worth a careful look.","tokens_in":30297,"tokens_out":6326,"would_cite":false,"duration_ms":60388,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q60","68Q45","03B70"],"pacs":[],"model":"deepseek-v4-flash","headline":"A fixed first-order sentence characterizes probabilistic bisimulation on regular weighted transition systems, making anonymity and uniformity of parameterized systems automatically checkable.","keywords":["probabilistic bisimulation","parameterized systems","regular structures","anonymity","uniformity","active automata learning","Markov decision processes","minimal deviation assumption"],"falsifier":"The central claim would fail if there existed a regular weighted transition system and a regular relation such that the extended structure satisfies the fixed sentence but the relation is not a bisimulation, or vice versa. Concretely, take two states with outgoing probability masses to one equivalence class of 0.4 plus 0.1 on one side and 0.5 on the other; the sentence must reject this relation. Running the automata-based check on that two-state example and inspecting the verdict would settle whether the iterated-addition encoding inside the sentence is sound.","tokens_in":29319,"feed_emoji":"🎲","tokens_out":7499,"duration_ms":77568,"temperature":0.7,"pith_summary":"This paper sets out to show that probabilistic bisimulation can be checked automatically for entire infinite families of finite-state systems, not just one instance at a time. Its central theorem gives a fixed first-order sentence such that a binary relation is a bisimulation on a weighted transition system exactly when the system extended with that relation satisfies the sentence, and the check is decidable whenever both are regular. Because anonymity and uniformity can both be expressed as the existence of a bisimulation between a system and a reference system or over a reversed chain, the same sentence covers both properties. The paper backs the theory with an active-learning procedure that synthesizes regular bisimulation relations automatically, reporting push-button verification of dining cryptographers, crowds, grades, random walks, random sums, Knuth-Yao and naive random number generators, and the ballot theorem. A sympathetic reader would care because this offers one unified route to properties that previously required distinct, often manual techniques in the parameterized setting.","feed_headline":"One logical sentence decides bisimulation for all sizes","feed_subtitle":"Anonymity and uniform randomness reduce to synthesizing regular relations; a prototype checks them automatically.","key_machinery":"The load-bearing object is the first-order theory of regular structures, in which universes are regular languages and all relations are regular, so formulas are effectively reducible to automata and decidable. Inside this theory, the paper defines regular weighted transition systems, normalizing probabilities to natural-number weights under the minimal-deviation assumption, and encodes the probabilistic bisimulation condition as a fixed first-order sentence. A second mechanism is active automata learning in the style of L-star, which synthesizes a regular candidate bisimulation by asking membership queries on finite instances and equivalence queries that check the bisimulation sentence. The two mechanisms work together: the theory supplies the verification condition, and the learner supplies the proof.","core_discovery":"At the paper's core is the claim that bisimulation on a weighted transition system is a first-order property of the system plus the relation. Theorem 4 constructs a fixed sentence expressing that the relation is an equivalence and that, for every action and every equivalence class, the total outgoing probability mass to that class is the same from any two related states. The sentence works by existentially guessing the bounded list of successors and a labeling that names their equivalence classes, then using a definable iterated addition to compare the class-wise probability sums. When the system and relation have regular presentations over finite words, satisfaction of the sentence is decidable by automata-theoretic means. The paper then shows that anonymity of a Markov decision process follows from a bisimulation between the process and a reference system, and that uniformity of a probabilistic program's output distribution follows from a bisimulation on the reversed chain whose final states are all equivalent.","pith_inferences":["Because bisimulation compares sums of path probabilities rather than one-to-one path couplings, this approach can prove uniform-output facts that coupling arguments cannot, while probability independence that requires self-composition lies outside its scope; a combined proof calculus is a natural next step.","The minimal-deviation assumption is likely the main boundary of the method: extending the sentence to parametric transition probabilities would require a correctness proof for the sketched addition axioms, and instantiating the crowds protocol with a symbolic forwarding probability would be a direct test of that extension.","An approximate analogue is visible from the same machinery: replacing equality of probability masses with epsilon-bisimilarity or bisimulation metrics could yield decidable checks of near-anonymity for cryptographic protocols, although the paper only lists this as future work.","One could try to recover completeness by alternating the learner with an enumerative synthesis procedure, since the learning algorithm alone may fail to find a regular bisimulation even when one exists."],"forward_implications":["Any regular weighted transition system and regular relation can be certified as bisimulation or not by a single automata check, so parameterized anonymity and uniformity become proof-synthesis problems rather than per-instance model checks.","Protocols with unbounded participant numbers, such as dining cryptographers, crowds, and grades, get one proof covering every size parameter instead of a separate finite check for each n.","Randomized algorithms can be certified to sample uniformly without fixing the range parameter, as demonstrated for Knuth-Yao random number generation and the ballot theorem.","Because the same bisimulation sentence handles both anonymity and uniformity, tools, proofs, and learning procedures transfer between the two property classes.","Whenever the greatest bisimulation is regular, the active-learning procedure is guaranteed to terminate and to produce a correct answer, giving a termination guarantee for the proof search in that case."],"supporting_citations":[{"why":"Supplies the theory of automatic and regular presentations, which underlies the encoding of systems as regular structures.","marker":"[37]"},{"why":"Shows that regular relations reduce to weak monadic second-order logic with one successor, the decidability mechanism behind checking the bisimulation sentence.","marker":"[38]"},{"why":"Introduces the minimal-deviation assumption and the probabilistic bisimulation definition that the central sentence formalizes.","marker":"[56]"},{"why":"Defines L-star active learning, the query model used to synthesize candidate bisimulation relations.","marker":"[59]"},{"why":"Provides the improved L-star algorithm with query bounds used in the learning procedure.","marker":"[60]"},{"why":"Gives the probabilistic modal logic characterization of bisimulation used to recognize non-bisimilar pairs in the decision procedure.","marker":"[63]"},{"why":"Shows how parameterized Markov decision processes are encoded as regular structures, supporting the padding and invariant optimizations.","marker":"[48]"}],"fun_headline_variants":["Bisimulation as a single logical sentence for all sizes","Automated anonymity and uniformity via regular bisimulation","One fixed formula verifies probabilistic bisimulation","Parameterized probabilistic verification: bisimulation in one sentence","Decidable bisimulation for infinite families of probabilistic systems"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method assumes every transition probability in the family is an integer multiple of a single epsilon greater than zero, so that probabilities can be normalized into a regular natural-number-weight encoding; the parametric-probability extension is only sketched and not proved.","fun_headline_variants_meta":{"raw":{"variants":["Bisimulation as a single logical sentence for all sizes","Automated anonymity and uniformity via regular bisimulation","One fixed formula verifies probabilistic bisimulation","Parameterized probabilistic verification: bisimulation in one sentence","Decidable bisimulation for infinite families of probabilistic systems"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00016,"raw_usage":{"total_tokens":1187,"prompt_tokens":853,"completion_tokens":334,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":469,"completion_tokens_details":{"reasoning_tokens":260}},"tokens_in":469,"tokens_out":334,"duration_ms":3664,"temperature":1.0,"reasoning_tokens":260,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:20:43.350699+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The central claim would fail if there existed a regular weighted transition system and a regular relation such that the extended structure satisfies the fixed sentence but the relation is not a bisimulation, or vice versa. Concretely, take two states with outgoing probability masses to one equivalence class of 0.4 plus 0.1 on one side and 0.5 on the other; the sentence must reject this relation. Running the automata-based check on that two-state example and inspecting the verdict would settle whether the iterated-addition encoding inside the sentence is sound.","supporting_citations":[{"cited_title":"Finite presentations of infinite struc- tures: Automata and interpretations,","cited_arxiv_id":null,"evidence_quote":"Supplies the theory of automatic and regular presentations, which underlies the encoding of systems as regular structures."},{"cited_title":"Transforming structures by set interpre- tations,","cited_arxiv_id":null,"evidence_quote":"Shows that regular relations reduce to weak monadic second-order logic with one successor, the decidability mechanism behind checking the bisimulation sentence."},{"cited_title":"Bisimulation through probabilistic testing,","cited_arxiv_id":null,"evidence_quote":"Introduces the minimal-deviation assumption and the probabilistic bisimulation definition that the central sentence formalizes."},{"cited_title":"Learning regular sets from queries and counterexamples,","cited_arxiv_id":null,"evidence_quote":"Defines L-star active learning, the query model used to synthesize candidate bisimulation relations."},{"cited_title":"Inference of finite automata using homing sequences,","cited_arxiv_id":null,"evidence_quote":"Provides the improved L-star algorithm with query bounds used in the learning procedure."},{"cited_title":"Model checking of probabilistic and nondeterministic systems,","cited_arxiv_id":null,"evidence_quote":"Gives the probabilistic modal logic characterization of bisimulation used to recognize non-bisimilar pairs in the decision procedure."},{"cited_title":"Liveness of randomised parameterised systems under arbitrary schedulers,","cited_arxiv_id":null,"evidence_quote":"Shows how parameterized Markov decision processes are encoded as regular structures, supporting the padding and invariant optimizations."}],"review_version":1}