{"id":"bc55b320-d78b-45ba-bfae-19653b4ebbd3","arxiv_id":"1908.06550","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors introduce relaxed congruence formats for stability-respecting branching bisimilarity and prove, via a new oracle-based lifting framework, that these formats also cover weakly divergence-preserving and divergence-preserving variants.","lead":"This paper proves new congruence formats for process equivalences that respect stability or divergence, extending the modal decomposition method from earlier work. It shows the priority operator fits the relaxed stability format and gives a general lifting method for divergence-aware semantics.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The explicit omission of the ⟨ε⟩(φ1⟨a⟩φ2) subcase in Proposition 31 leaves the key modal-preservation lemma unverified; until that case is written out, Theorems 32 and 33 rest on an unproved adaptation.","rationale":"The reader's weakest assumption identifies the same omitted case in Proposition 31, and that is also the most load-bearing concern I find. The rest of the paper's correctness arguments are technical but are either written out in detail or explicitly delegated to earlier published results; the only place where a proof case is openly skipped is in the heart of the modal-preservation lemma on which the main congruence theorems 32 and 33 depend. The relaxation in condition 4a is precisely what makes the a-labelled subcase non-importable from [15]: new configurations with multiple positive premises and negative premises are admitted, and the written proof shows how to handle them only for the ⟨ˆτ⟩ variant. The divergence-lifting framework in Section 5 is also intricate, but its key steps are present: the abstraction-free transformation, the oracle construction, and Propositions 54 and 63 are all argued in the text. Thus I do not see a reason to move the verdict to REJECT or UNVERDICTED; rather, the conditional verdict is the right one, contingent on completing the omitted adaptation. If the written-out case confirms the stated equivalence, the central claim is likely sound; if it does not, the relaxed format may be unsound for the a-labelled formulas.","tokens_in":43841,"tokens_out":34915,"duration_ms":369891,"concrete_test":"Write out the omitted subcase for ϕ = ⟨ε⟩(ϕ1⟨a⟩ϕ2) in Proposition 31, considering both clause 4a and clause 4b of Definition 17, and both ℵ-liquid and ℵ-frozen occurrences of x. In the ℵ-liquid case, for a ruloid H with more than one positive premise or with negative premises, use condition 4a of Definition 20 to obtain x⁄τ→ ∈ H, and verify that the decomposed formula ψ(x) is logically equivalent to ⟨ε⟩(¬⟨τ⟩⊤∧φ′) for some φ′∈Os_rb, by absorbing each additional ⟨b⟩ξ(y) and ¬⟨c⟩⊤ conjunct into φ′; in the single-positive-premise case verify that ψ(x) has the shape ⟨ε⟩(φ′⟨a⟩φ″) or ⟨ε⟩(φ′⟨ˆτ⟩φ″). If every configuration yields ψ(x)∈Os≡b, the concern is resolved; if any configuration yields a conjunct outside Os_rb, Theorems 32 and 33 would be unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing point is the omitted subcase in the proof of Proposition 31, claim 1. After Case 2.2 the text says: 'The proof of the case ϕ = ⟨ε⟩(ϕ1⟨a⟩ϕ2) in Ob from [15, Prop. 3] needs to be adapted in a similar fashion as the case ϕ = ⟨ε⟩(ϕ1⟨ˆτ⟩ϕ2). We take the liberty to omit this adaptation here.' This matters because condition 4a of Definition 20 deliberately relaxes the branching-bisimulation safety condition: a ruloid H may now contain more than one positive premise involving x, or negative premises, provided H also contains a premise x⁄τ→. The written proof shows how this relaxation is absorbed for the ⟨ˆτ⟩ modality, by rewriting the decomposition as ⟨ε⟩(¬⟨τ⟩⊤∧φ′) with φ′∈Os_rb. The analogous argument for the a-labelled modality is exactly the case where the same relaxed ruloids can occur, but with the extra positive premises carrying arbitrary labels and the formula already containing a distinguished ⟨a⟩ step. If, in that case, the extra conjuncts cannot be rearranged into an Os_rb formula together with the a-labelled conjunct, then ψ(x) may fall outside Os≡b, and the modal-preservation step fails. Since Proposition 31 is the sole bridge from the syntactic format to the congruence theorems 32 and 33, an unverified gap there is a genuine correctness risk; the paper provides no independent check of this omitted case.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper extends the modal-decomposition method for deriving congruence formats to stability-respecting branching bisimilarity and its rooted and divergence-preserving variants. It relaxes the earlier rooted branching bisimulation format by allowing rules such as the priority operator's rule to contain multiple positive or negative premises involving a variable, provided a premise that the variable cannot perform τ is present, and it proves in Theorems 32 and 33 that complete standard TSSs in this format make stability-respecting and rooted stability-respecting branching bisimilarity congruences. A second part introduces a general oracle-based lifting theorem (Theorem 36) and instantiates it in four ways to show that the same formats are also congruence formats for weakly divergence-preserving and divergence-preserving branching bisimilarity and their rooted variants (Theorems 58, 60, 66, 68). The paper includes applications to the priority operator and a sequencing operator, and it motivates the abstraction-free transformation with concrete examples.","tokens_in":44184,"tokens_out":29658,"duration_ms":289931,"significance":"If the main theorems are correct, the paper is a substantial addition to the divide-and-congruence programme. It shows how the modal-decomposition framework can be extended beyond weak semantics that ignore stability, and it provides a novel oracle construction that avoids a direct inductive treatment of the divergence modality. The relaxation of the format is genuinely useful: it brings the priority operator into the stability-respecting branching bisimulation format, which was previously out of scope. The parametric lifting theorem in Section 5.1 is cleanly stated and gives a reusable framework for transferring congruence formats to finer equivalences. The paper is also honest about its limitations, including the explicit note that convergent weak semantics remain outside the method. However, the technical presentation currently leaves some load-bearing proof obligations to the reader, and at least one key case is explicitly omitted.","major_comments":[{"comment":"The proof explicitly omits the case φ = ⟨ε⟩(φ1⟨a⟩φ2), with the sentence 'We take the liberty to omit this adaptation here.' This case is load-bearing: Proposition 31 is the sole bridge from the syntactic format to Theorems 32 and 33. The adaptation is not a purely mechanical copy of the ⟨τ⟩-hat case, because the ruloid used in Definition 17.3 has a conclusion labelled a rather than τ, and condition 4b of Definition 20 interacts with a-labelled conclusions differently: a rule with a positive τ-premise under an ℵ-liquid variable can only satisfy condition 4b if it is a patience rule, which is impossible for a non-τ conclusion. The omitted case must show in full that when condition 4a is triggered — multiple positive premises or negative premises, together with the forced premise x⁄τ→ — the resulting decomposition ψ(x) can be rewritten as a formula of the form ⟨ε⟩(¬⟨τ⟩⊤∧φ′) with φ′ in O_s^rb, taking into account that the a-modality is consumed by the ruloid and does not appear as a conjunct in ψ(x). Until this case is written out, the modal-preservation lemma, and hence the two main congruence theorems for stability-respecting branching bisimilarity, rest on an unverified claim.","section":"Section 5.3, requirement 2 of Theorem 36"},{"comment":"The preservation of the (rooted) stability-respecting branching bisimulation format under the AFO transformation is asserted as 'straightforward to check' and justified only by a brief heuristic. This property is load-bearing for Theorems 58, 60, 66 and 68, because it is what allows Theorem 36 to conclude that ≈_{AFO(P)} is a congruence. A complete proof should verify each condition of Definition 20 for each of the six steps of Definition 37. In particular, the new oracle rules of step 6 must be checked against condition 4a when the argument is Γ-liquid; the rules produced in steps 1–3 must be checked to ensure that no new positive τ-premises are created, so that condition 4b is preserved; and the added negative ι-premises of step 3 must be shown to satisfy condition 4a together with the retained τ-premises. The two-sentence sketch in Section 5.3 does not provide this verification, and the reader is left to reconstruct a substantial technical argument.","section":"Section 5.3, paragraph before Sect. 5.3.1"}],"minor_comments":[{"comment":"In the last sentence of Case 2.2, 'by induction ξ(y) ∈ O_s^b' should read 'by induction χ(y) ∈ O_s^b'; the variable ξ is not introduced in that case.","section":"Section 4.2, proof of Proposition 31, Case 2.2"},{"comment":"The sentence 'This gives rise to a ξ ∈ h^{-1}(x) such that ξ(x) = ¬⟨τ⟩⊤' appears to have the negation in the wrong place: the patience ruloid gives ξ(x) = ⟨τ⟩⊤, so that the conjunct ¬ξ(x) contributes ¬⟨τ⟩⊤ as needed.","section":"Section 4.2, proof of Proposition 31, Case 1.1 for φ = ⟨ε⟩(¬⟨τ⟩⊤∧φ)"},{"comment":"The sentence 'Then p↔b q, but p;r↔ p⁄↔b r↔ q;r' appears garbled; it should be rewritten to say clearly that p;r and q;r are not branching bisimilar.","section":"Section 4.1, Example 24"},{"comment":"It would help to state explicitly that when Definitions 1 and 2 are applied to AFO(P) and K, the set A is taken to be the enlarged set of non-τ actions, including O and ι, so that oracle and ι transitions are treated as ordinary observable labels in the bisimulation clauses and in the modal characterisation. Without this clarification, the use of branching bisimulation for Δ⊤-transitions in Proposition 54 is under-specified.","section":"Section 5.2, Definition 37 and following"},{"comment":"The phrase 'Rooted F' should be replaced by something like 'the rooted format F' for readability.","section":"Section 5.3.2, Corollary 59"}],"recommendation":"major_revision","confidential_remarks":"The central results are likely correct, but the paper is not yet in publishable form because the explicitly omitted case in Proposition 31 is load-bearing and the preservation of the format under AFO is only sketched. Both gaps are repairable within the scope of the paper, so I recommend major revision rather than rejection; the authors should be asked to write out the omitted case and to provide a complete preservation proof for Definition 37."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, this is a genuine advance in the divide-and-congruence program: the stability-respecting relaxation of the branching bisimulation format (Def. 20 condition 4a) brings operators like priority into scope, and the oracle-based lifting framework in Section 5 is a new way to transfer congruence from stability-respecting to divergence-preserving semantics. Second, the proof of the main preservation lemma has an explicit hole. Proposition 31, claim 1, omits the adaptation for phi = <epsilon>(phi1<a>phi2), and that case is exactly where the relaxed condition 4a interacts with observable labels. The stress-test note is right: the text says the adaptation is omitted, so this is not a phantom concern.\n\nWhat is good: the stability clause <epsilon>(not<tau>T /\\ phi) is a clean addition to the modal characterisation, and the paper shows convincingly how it absorbs negative premises for the hat-tau case. The lifting theorem (Thm 36) is a useful abstraction; the AFO construction with oracle transitions is original. The congruence results for the divergence-preserving variants (Theorems 58, 60, 66, 68) are new and fit the known examples, including sequencing and priority.\n\nThe soft spots, in proportion: the omitted subcase is the main barrier. A referee should demand that the adaptation be written out, not trusted as 'similar'. Several other checks are asserted rather than shown: preservation of the format under AFO, requirement 5 for the rooted cases, and some 'straightforward' inductions in Section 5.2. These look fillable, but they are part of the paper's verification burden. The heavy reliance on [15] is acceptable, but it concentrates the work in cross-checking the earlier proof.\n\nWho this is for: readers working on SOS congruence formats for weak semantics. With the gap closed, it will be a standard reference. It deserves a serious referee even now: the contribution is important and the machinery is promising. My recommendation: send to review, ask for a careful revision that fills the omitted case and expands the sketched checks. This is not a desk reject.","headline":"A real extension of the divide-and-congruence framework with a clever oracle-lifting proof; the key preservation lemma has an explicitly omitted subcase that must be supplied before the congruence theorems are fully established.","tokens_in":44656,"tokens_out":4572,"would_cite":true,"duration_ms":43666,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q85","03B70"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that a single syntactic format for transition rules — the (rooted) stability-respecting branching bisimulation format — makes stability-respecting, weakly divergence-preserving, and divergence-preserving branching…","keywords":["Structural Operational Semantics","Weak Semantics","Modal Logic","congruence formats","branching bisimilarity","stability","divergence","modal decomposition"],"falsifier":"Construct a complete standard TSS satisfying Definition 20 and a closed term in it for which the omitted $\\langle\\varepsilon\\rangle(\\phi_1\\langle a\\rangle\\phi_2)$ case of Proposition 31 yields a decomposition mapping whose value at some variable is not equivalent to any formula of $\\mathcal{O}^s_b$; equivalently, exhibit two stability-respecting branching bisimilar closed terms $p,q$ and a function symbol $f$ allowed by the format for which $f(p)$ and $f(q)$ are not stability-respecting branching bisimilar.","tokens_in":43633,"feed_emoji":"🧩","tokens_out":10512,"duration_ms":93367,"temperature":0.7,"pith_summary":"This paper extends a modal-decomposition method for deriving congruence formats to weak process semantics that respect stability — the absence of $\\tau$-transitions — or preserve divergence. It defines a syntactic format for transition rules, the (rooted) stability-respecting branching bisimulation format, and claims that every complete standard transition system specification in this format makes (rooted) stability-respecting branching bisimilarity a congruence. The same format, via a separate lifting theorem, is then claimed to guarantee congruence also for weakly divergence-preserving and divergence-preserving branching bisimilarity, in both rooted and unrooted forms. The relaxation matters in practice because it admits transition rules with negative premises, such as the priority operator, which earlier congruence formats rejected.","feed_headline":"One format proves congruence for six branching semantics","feed_subtitle":"Stability and divergence-respecting branching bisimilarities all become congruences under the same relaxed rule format.","key_machinery":"The load-bearing object is a syntactic format for transition rules — the rooted stability-respecting branching bisimulation format (Definitions 20–21) — whose safety conditions relax the earlier branching bisimulation format. A rule is safe if right-hand sides of positive premises occur only $\\Lambda$-liquid in the target; if a variable occurring only $\\Lambda$-liquid in the source stays $\\Lambda$-liquid throughout the rule; if a variable that is $\\aleph$-frozen in the source stays $\\aleph$-frozen in the premises; and the novel clause: a variable with exactly one $\\aleph\\cap\\Lambda$-liquid occurrence in the source may occur in several positive premises or in negative premises, provided a premise $v\\not\\!\\xrightarrow{\\tau}$ is also present. This last clause is what admits the priority operator. The argument runs on two machines. First, modal decomposition (Definition 17): with every term $t$ and formula $\\phi$ it associates decomposition mappings $\\psi$ so that $\\rho(t)\\models\\phi$ holds exactly when some $\\psi$ has $\\rho(x)\\models\\psi(x)$ for all variables $x$; the congruence proof reduces to showing that formulas of $\\mathcal{O}^s_b$ and $\\mathcal{O}^s_{rb}$ always decompose into formulas of the same class, which is Proposition 31. Second, the abstraction-free transformation $\\mathrm{AFO}$ (Definition 37) with its oracle rules and the decoding map $\\mathrm{dec}$: the lifting theorem (Theorem 36) uses these to transfer congruence from stability-respecting to divergence-preserving semantics by making $\\sim$ and $\\approx$ coincide on the transformed TSS.","core_discovery":"On the paper's own terms, the central discovery is that the modal characterisation of stability-respecting branching bisimilarity — the logic $\\mathcal{O}^s_b$, which adds the clause $\\langle\\varepsilon\\rangle(\\neg\\langle\\tau\\rangle\\top\\wedge\\phi)$ to the branching-bisimulation logic $\\mathcal{O}_b$ — decomposes into itself under the syntactic restrictions of the (rooted) stability-respecting branching bisimulation format. That preservation result (Proposition 31) yields the congruence theorems for $\\leftrightarrow^s_b$ and $\\leftrightarrow^s_{rb}$ on every complete standard TSS in the format. Divergence cannot be handled inductively, so the paper proves a general lifting theorem (Theorem 36) with a transformation $\\mathrm{AFO}$ that makes a TSS abstraction-free — only patience rules carry $\\tau$ in their conclusions — and adds oracle transitions that certify divergence or equivalence-class membership. On the transformed TSS the finer and coarser equivalences coincide, and decoding back into the original system is compositional, so any format that is a congruence format for the coarser equivalence and is preserved by $\\mathrm{AFO}$ is also a congruence format for the finer one. Instantiating the lifting to weakly divergence-preserving and divergence-preserving branching bisimilarity, rooted and unrooted, gives Theorems 58, 60, 66 and 68.","pith_inferences":["Because the omitted $\\langle\\varepsilon\\rangle(\\phi_1\\langle a\\rangle\\phi_2)$ case is structurally analogous to the written $\\langle\\varepsilon\\rangle(\\phi_1\\langle\\hat\\tau\\rangle\\phi_2)$ case, a likely repair is to absorb any negative premises through the conjunct $\\neg\\langle\\tau\\rangle\\top$ that the format's condition 4a forces to be present; verifying that single adaptation would settle the un","The oracle-transition technique is not specific to branching bisimilarity: it should transfer to any pair of weak equivalences where the finer one is obtained from the coarser one by adding divergence or convergence information, such as $\\eta$-, delay, or weak bisimulation with their divergence-preserving variants.","The relaxation principle behind condition 4a — negative premises are harmless as long as every problematic variable can be shown not to have a $\\tau$-transition — looks like a general recipe for relaxing congruence formats for any $\\tau$-based semantics whose modal logic contains a stability clause $\\langle\\varepsilon\\rangle(\\neg\\langle\\tau\\rangle\\top\\wedge\\phi)$.","If the omitted adaptation turned out to be impossible, Theorem 32 would fail on a rule with negative premises and an $a$-labelled conclusion; a search for counterexamples should therefore start with operators that combine negative premises on 'a' with a $\\tau$-negative premise requirement, exactly the shape of the priority operator."],"forward_implications":["Any complete standard TSS in the (rooted) stability-respecting branching bisimulation format makes six equivalences congruences at once: stability-respecting, weakly divergence-preserving, and divergence-preserving branching bisimilarity, in rooted and unrooted forms.","The priority operator, whose rule has negative premises, falls inside the relaxed format, so all six semantics become congruences for it whenever the action ordering satisfies the paper's condition ($\\tau$ above every $\\beta > \\alpha$).","The rooted stability-respecting format also covers sequencing (the paper's Corollary 25), though the unrooted format does not, by the paper's own counterexample.","Congruence proofs for divergence-preserving variants no longer need to be repeated from scratch: the lifting theorem shows they follow automatically from the stability-respecting case.","The lifting framework (Theorem 36) applies to any behavioural equivalences $\\sim\\subseteq\\approx$ containing strong bisimilarity, so the same machinery can be reused for other pairs of weak semantics."],"supporting_citations":[{"why":"Supplies the modal decomposition method, the branching bisimulation format that this paper relaxes, and the preservation propositions that Proposition 31 extends.","marker":"[15]"},{"why":"Introduces the decomposition of Hennessy-Milner logic formulas and the transformation to ruloids that underpin Definition 17 and Theorem 18.","marker":"[6]"},{"why":"Provides the modal characterisations of weak semantics, including $\\mathcal{O}^s_b$ and $\\mathcal{O}^s_{rb}$, from which the paper's Theorem 8 is taken.","marker":"[16]"},{"why":"Defines well-supported proofs and complete TSSs, the consistency and completeness machinery used throughout.","marker":"[17]"},{"why":"Supplies Lemmas 61 and 62 on divergence-preserving branching bisimilarity, used in the proof of Proposition 63.","marker":"[18]"},{"why":"Defines branching bisimilarity and its divergence-preserving variants, the semantics whose congruence properties are at issue.","marker":"[20]"},{"why":"Introduces the priority operator, the motivating example showing why the relaxation to negative premises matters.","marker":"[1]"},{"why":"Reduces ntyft/ntyxt rules to ntree rules, used in the construction of $P^+$ and the ruloid transformation.","marker":"[10]"}],"fun_headline_variants":["Relaxed format yields stability-respecting branching bisimilarity congruence","Divergence folded in via lifting to coarser equivalence","One rule format covers stability and divergence semantics","Decomposition method tames stability and divergence"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The congruence theorems rest on Proposition 31, whose simultaneous induction leaves one case — the decomposition of formulas $\\langle\\varepsilon\\rangle(\\phi_1\\langle a\\rangle\\phi_2)$ — unexpanded, with the paper saying only that the adaptation from the $\\tau$-case is omitted; if that adaptation cannot be supplied, the claim that the format preserves the modal characterisation, and with it Theorems 32 and 33, would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Relaxed format yields stability-respecting branching bisimilarity congruence","Divergence folded in via lifting to coarser equivalence","One rule format covers stability and divergence semantics","Decomposition method tames stability and divergence"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000311,"raw_usage":{"total_tokens":1801,"prompt_tokens":1004,"completion_tokens":797,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":620,"completion_tokens_details":{"reasoning_tokens":734}},"tokens_in":620,"tokens_out":797,"duration_ms":7883,"temperature":1.0,"reasoning_tokens":734,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:41:12.846277+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a complete standard TSS satisfying Definition 20 and a closed term in it for which the omitted $\\langle\\varepsilon\\rangle(\\phi_1\\langle a\\rangle\\phi_2)$ case of Proposition 31 yields a decomposition mapping whose value at some variable is not equivalent to any formula of $\\mathcal{O}^s_b$; equivalently, exhibit two stability-respecting branching bisimilar closed terms $p,q$ and a function symbol $f$ allowed by the format for which $f(p)$ and $f(q)$ are not stability-respecting branching bisimilar.","supporting_citations":[{"cited_title":"F OKKINK , R.J","cited_arxiv_id":null,"evidence_quote":"Supplies the modal decomposition method, the branching bisimulation format that this paper relaxes, and the preservation propositions that Proposition 31 extends."},{"cited_title":"B LOOM , W.J","cited_arxiv_id":null,"evidence_quote":"Introduces the decomposition of Hennessy-Milner logic formulas and the transformation to ruloids that underpin Definition 17 and Theorem 18."},{"cited_title":"VAN GLABBEEK (1993): The linear time-branching time spectrum II: The semantics of sequential systems with silent moves","cited_arxiv_id":null,"evidence_quote":"Provides the modal characterisations of weak semantics, including $\\mathcal{O}^s_b$ and $\\mathcal{O}^s_{rb}$, from which the paper's Theorem 8 is taken."},{"cited_title":"VAN GLABBEEK (2004): The meaning of negative premises in transition system specifications II","cited_arxiv_id":null,"evidence_quote":"Defines well-supported proofs and complete TSSs, the consistency and completeness machinery used throughout."},{"cited_title":"VAN GLABBEEK , B","cited_arxiv_id":null,"evidence_quote":"Supplies Lemmas 61 and 62 on divergence-preserving branching bisimilarity, used in the proof of Proposition 63."},{"cited_title":"VAN GLABBEEK & W.P","cited_arxiv_id":null,"evidence_quote":"Defines branching bisimilarity and its divergence-preserving variants, the semantics whose congruence properties are at issue."},{"cited_title":"B AETEN , J.A","cited_arxiv_id":null,"evidence_quote":"Introduces the priority operator, the motivating example showing why the relaxation to negative premises matters."},{"cited_title":"F OKKINK & R.J","cited_arxiv_id":null,"evidence_quote":"Reduces ntyft/ntyxt rules to ntree rules, used in the construction of $P^+$ and the ruloid transformation."}],"review_version":1}