{"id":"f721fc90-185d-4d8e-aa9f-ff6eba695380","arxiv_id":"1908.06684","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"In non-positively curved precubical sets, which model mutex-only concurrent programs, two directed paths are homotopic if and only if they are dihomotopic.","lead":"This paper proves that for the geometric models of concurrent programs that use only mutex locks, ordinary homotopy and directed homotopy give the same equivalence relation on execution paths. This means standard topological invariants can be used to study the space of possible executions of such programs.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proof of Theorem 2.29 relies on Proposition 2.24 (every formal 2-cell rewrites to canonical form) and on Lemma 2.25(4)-(5), whose deferred case analyses are the only stated route to eliminating η/ε in Lemma 2.28; if any deferred case fails, homotopy-to-dihomotopy is unsupported.","rationale":"The reader identified the same technical, load-bearing gap that I see: the normalization proof for formal 2-cells and the commutation rules that eliminate the unit and counit 2-cells are the unsecured link in Theorem 2.29. I could not construct a counterexample to the theorem itself; the hollow-cube example actually supports the proof strategy by showing why the cube property is needed. One side observation is that Theorem 2.30, 'the quotient functor is full and faithful,' is not literally correct as stated: for the one-edge npc precubical set, the fundamental groupoid has an extra morphism (the reverse edge) that is not in the image of the fundamental category, so fullness fails. That side statement does not refute Theorem 2.29, but it suggests the categorical packaging should be read as faithfulness for directed morphisms or otherwise corrected. I therefore keep the CONDITIONAL verdict: the proof gap warrants conditionality, while the statement and the surrounding framework remain plausible.","tokens_in":45345,"tokens_out":14639,"duration_ms":146597,"concrete_test":"Implement the string-diagram rewriting system of Section 2.2 (generators γ, η, ε; relations (2.5)-(2.15) plus (2.16)-(2.18); operators G, H, E) and machine-check, in a proof assistant or with an exhaustive rewriting engine, the missing cases: (i) every step of Proposition 2.24's induction for arbitrary nested canonical forms, and (ii) Lemma 2.25(4) and (5) for arbitrary 1-cell contexts. If every left-hand side rewrites to the stated right-hand side and every canonical form of a dipath-endpoint cell is provably H/E-free, the concern is settled.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is Theorem 2.29: in an npc precubical set, two dipaths are homotopic iff they are dihomotopic. The proof decomposes a homotopy 2-cell into slices (Lemma 2.20), rewrites it to a canonical form (Proposition 2.24), and then uses Lemma 2.28 to eliminate every η and ε generator. The two load-bearing steps are not fully proved. Proposition 2.24 ends with 'The case where α = γ can be handled similarly by case analysis,' after treating only restricted subcases for α = ε; the number of context combinations is large because the canonical form may be an arbitrary nested expression in the operators G, H, and E. Lemma 2.25 items (4) and (5), which are the only stated commutations for moving H past G, are asserted with 'can easily be guessed from the figures' and no derivation is supplied. If any missing index or context case fails, a formal 2-cell between dipaths could have a canonical form in which H or E cannot be eliminated, so Lemma 2.28 would not produce a dihomotopy. This is a proof gap rather than evidence of a false statement; the geometric and categorical context independently makes the theorem plausible.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces non-positively curved (npc) precubical sets as an algebraic analogue of CAT(0) cubical complexes, proves that the precubical semantics of mutex-only concurrent programs is npc (Prop 1.29), gives a link-condition characterization (Thm 1.42), and establishes the main result (Thm 2.29/2.30): for npc precubical sets, two dipaths are homotopic if and only if they are dihomotopic, so the fundamental category and fundamental groupoid determine each other for directed paths. The proof strategy is a 2-categorical rewriting system on formal 2-cells, with a canonical form (Prop 2.24) and commutation rules (Lemma 2.25) used to eliminate the η and ε generators. The paper then develops generalized metric spaces and geometric realization, showing that the npc axioms correspond to Gromov's flag condition (Thm 3.79), so that realizations are CAT(0) cubical complexes.","tokens_in":45756,"tokens_out":7271,"duration_ms":73041,"significance":"If the main theorem is established, it is an important bridge: ordinary (undirected) homotopy theory becomes applicable to the directed execution spaces of mutex programs, and the connection to CAT(0) geometry links concurrency semantics to a mature body of geometric group theory. The paper's architectural strengths are its external benchmarks: the npc condition is checked against Gromov's CAT(0) link condition (Thm 3.79), the 2-categorical axioms are related to compact closed categories (Prop 2.33), and the mutex semantics independently yields the cube property (Prop 1.29). The treatment of generalized metric spaces and the identification of directed realizations as CAT(0) cubical complexes is also valuable. However, the proof of the central normalization theorem is not complete as written: two load-bearing steps are deferred to 'similar case analysis' or to figures.","major_comments":[{"comment":"Proposition 2.24 is the normalization lemma on which the proof of Theorem 2.29 rests, but its proof is incomplete. The induction treats only four subcases for α = ε with ψ = G...; it defers 'The cases where ψ = H... and ψ = E... can be handled similarly by case analysis' and 'The case where α = γ can be handled similarly by case analysis.' Since the canonical form can be an arbitrary nested expression in the operators G, H, E, and the slice α can be η, ε, or γ in arbitrary context, these omitted combinations are exactly the ones that require the delicate commutations of Lemma 2.25. Without a complete case analysis, the assertion that every formal 2-cell rewrites to a canonical form is not established.","section":"§2.2.2, Proposition 2.24"},{"comment":"Items (4) and (5) of Lemma 2.25 are asserted with 'can easily be guessed from the figures' and no derivation is supplied. These are the only stated rules for commuting G past H in the nested cases involving two G/H contexts, and Lemma 2.28 uses them to bring an H to the left and to place an E in front of an H-free expression. A missing index or context case would break the elimination of η and ε. The proof should either give complete equational derivations for (4) and (5), or formulate a general commutation lemma with all indices specified.","section":"§2.2.2, Lemma 2.25"},{"comment":"The argument in Lemma 2.28 that a canonical form containing H or E can be rearranged 'up to more rewriting' needs to ensure that each application of Lemma 2.25 preserves the property of being a canonical form and does not reintroduce an operator already eliminated. The text asserts this without proof, and the properties in Lemma 2.27 are stated for canonical forms, not for arbitrary rewrites. A precise induction on the structure of the canonical form is needed.","section":"§2.2.2, Lemma 2.28"}],"minor_comments":[{"comment":"The flag condition for presimplicial sets is stated for 'every integer n > 3', but the proof of Theorem 1.42 applies it with n = 2 in the cube-property direction and with arbitrary n afterwards; the condition should presumably read n > 2 (or n ≥ 3). Please correct the statement and check that it agrees with the standard usage in Definition 3.78.","section":"Definition 1.37"},{"comment":"The section begins 'We omit proofs, they should be detailed in subsequent works'; this explicitly leaves Proposition 2.33 and the convergence conjectures unproved. Since they are not used in the proof of Theorem 2.29 this is acceptable for an extensions section, but the paper should mark them clearly as conjectures or unproved claims rather than presenting them as established results.","section":"Section 2.3"},{"comment":"There is a typo: 'there are height in total' should read 'there are eight in total.'","section":"Remark 1.26"},{"comment":"Some displayed equations, in particular (2.14) and the surrounding lines, have malformed or missing indices on the γ generators; please proofread and restore the full indices.","section":"§2.2.1, equations (2.13)–(2.15)"}],"recommendation":"major_revision","confidential_remarks":"The paper is a strong fit for LMCS and the main theorem is plausible; the issue is a proof gap, not a false statement. I would like to see the omitted case analyses in Proposition 2.24 and Lemma 2.25 supplied, or the affected lemmas replaced by a more systematic argument. I see no grounds for citation or integrity concerns."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. First, the main result — for mutex-only programs, directed and ordinary homotopy coincide on execution dipaths — is genuinely new and, if correct, it changes how we think about concurrency semantics: it says the execution space is non-positively curved in a precise algebraic sense, so classical invariants apply. Second, the proof of that result relies on a normalization argument that is not fully written out. Proposition 2.24 ends with \"similar case analysis\" and Lemma 2.25(4)-(5) says the commutations \"can easily be guessed from the figures.\" Those are exactly the steps that push H and E generators to the right place so Lemma 2.28 can eliminate them. If any of those cases fails for some context, the reduction of homotopy to dihomotopy is unsupported. I don't think it fails — the geometry, the cube property, and the compact-closed-category sanity check all point the same way — but a serious reader cannot verify the central claim from the printed proof alone.\n\nWhat is actually new: the paper introduces npc precubical sets, proves that mutex semantics are npc, and proves that geometric realization turns npc precubical sets into CAT(0) cubical complexes. That gives a clean triangle: programs, combinatorics, metric geometry. The paper is unusually honest about its debts — it cites Winskel, Chepoi, Gromov, and others carefully, and uses them as benchmarks rather than fitting definitions to force the conclusion. The 2-categorical rewriting setup is elegant.\n\nThe soft spots are contained and real. Theorem 1.42 (link characterization) is proved in full. The gap is localized to the normalization and exchange lemmas. Proposition 2.24 explicitly defers many cases; Lemma 2.25(4)-(5) has no derivation at all. This is load-bearing, so \"conditional\" is the right verdict. It is a proof gap, not a statement gap.\n\nWho should read this: anyone working on directed algebraic topology, concurrency semantics, or CAT(0) cube complexes. It deserves serious referee time. I would ask the authors for an expanded proof, ideally a machine-checked version of the rewriting lemmas, before I rely on the theorem. The paper is significant and the gap looks fixable.","headline":"This is the real bridge between directed algebraic topology and CAT(0) geometry; the main theorem is well-motivated and likely correct, but the rewriting proof has a genuine gap that should be fixed or formalized.","tokens_in":46227,"tokens_out":2740,"would_cite":true,"duration_ms":32300,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q85","18D05","55U10"],"pacs":[],"model":"deepseek-v4-flash","headline":"For mutex-only programs, homotopy and directed homotopy coincide.","keywords":["precubical sets","directed homotopy","dihomotopy","non-positive curvature","CAT(0) spaces","concurrent programs","mutex synchronization","cube property"],"falsifier":"Run an exhaustive computer search over small non-positively curved precubical sets for a pair of homotopic directed paths whose homotopy, written as a formal 2-cell, cannot be rewritten to square-swap form; finding such a pair would refute Theorem 2.29, while checking all finite index cases of the deferred rewriting lemmas would confirm the missing subcases.","tokens_in":45124,"feed_emoji":"📐","tokens_out":10975,"duration_ms":105193,"temperature":0.7,"pith_summary":"This paper studies the spaces of possible executions of concurrent programs that synchronize only with mutexes, the lock primitive that at most one thread can hold at a time. It introduces a combinatorial notion of non-positive curvature for precubical sets, the shapes used to model these execution spaces, and proves that the semantics of every mutex-only program satisfies it. The central result is that in such a space two directed paths are homotopic in the ordinary, undirected sense exactly when they are dihomotopic, meaning one can be deformed into the other while keeping time directed. This says that the fundamental groupoid of an execution space already carries all the information in its fundamental category, so standard algebraic topology can be used to analyse execution traces of mutex-only programs. The same curvature condition is then shown to match the classical CAT(0) condition after geometric realization, connecting program semantics to non-positive curvature geometry.","feed_headline":"In mutex-only programs, ordinary homotopy equals directed homotopy","feed_subtitle":"Execution traces of such programs become ordinary topological paths, so standard invariants apply.","key_machinery":"The load-bearing mechanism is the cube property, the requirement that whenever a precubical set contains one half of the boundary of a 3-cube it also contains the other half; together with geometricity and unique filling of higher cube boundaries, it defines non-positive curvature for precubical sets. To compare homotopy with dihomotopy, the paper constructs the fundamental 2-category $\\vec{\\Pi}_2(C)$ and fundamental 2-groupoid $\\Pi_2(C)$ of a precubical set, whose 2-cells are formal homotopies generated by square swaps $\\gamma_{a,b}^{b',a'}$, by units $\\eta_a$ (inserting $a\\cdot\\bar a$), and by counits $\\varepsilon_a$ (cancelling $\\bar a\\cdot a$). A rewriting system over these 2-cells, with the exchange law and the cube property ensuring that every rewrite stays well-defined, brings every formal 2-cell between two dipaths to a canonical form built only from square swaps; that canonical form is exactly a dihomotopy. In the geometric part, the link of each vertex, with its flagness condition, is the discrete counterpart of the classical link condition characterizing non-positive curvature.","core_discovery":"Let $C$ be a non-positively curved precubical set: geometric, satisfying the cube property, and filling $n$-cube boundaries uniquely for $n\\ge 3$. Theorem 2.29 of the paper asserts that two dipaths in $C$ are homotopic if and only if they are dihomotopic, and Theorem 2.30 restates this as the fullness and faithfulness of the quotient functor from the fundamental category $\\vec{\\Pi}_1(C)$ to the fundamental groupoid $\\Pi_1(C)$. Since Proposition 1.29 shows that the precubical semantics of a mutex-only program is such a set, directed paths in the execution space are classified by ordinary homotopy: the orientation of time is immaterial at the level of homotopy classes. The paper also establishes that this discrete notion of non-positive curvature is the algebraic shadow of the standard geometric one: the geometric realization of an npc precubical set is a CAT(0) cubical complex.","pith_inferences":["One natural next step the paper does not take is to prove the same collapse one dimension higher, so that the fundamental 2-category embeds into the fundamental 2-groupoid; the canonical-form rewriting suggests this could hold, but that is an inference, not a theorem proved here.","Since curvature is local, deciding whether two dipaths are dihomotopic in these program spaces could be reduced to an ordinary homotopy problem on the 2-skeleton, a more tractable algorithmic formulation than searching the full path space.","The generalized-metric realization encodes duration as well as direction, so if the curvature argument carries over, timed concurrent models might inherit the same collapse of directed to ordinary homotopy, an extension the paper leaves open."],"forward_implications":["For any mutex-only program, the fundamental category of its execution space embeds fully faithfully into the fundamental groupoid, so homotopy classes of directed paths are faithfully reflected by ordinary homotopy classes.","Ordinary topological invariants, such as components, fundamental group, and homology, can be used to study the execution traces of these programs without building separate directed invariants.","After directed geometric realization, dipaths between realizations of vertices in an npc precubical set are homotopic exactly when they are dihomotopic, transferring the theorem from combinatorics to metric spaces.","Geometric realizations of mutex-only program semantics are CAT(0) cubical complexes, hence locally uniquely geodesic with contractible universal covers.","The cube property is equivalent to a local flagness condition on links, so the curvature of an execution space can be checked vertex by vertex."],"supporting_citations":[{"why":"It supplies the 2-dimensional rewriting techniques for monoidal categories that the canonical-form argument for homotopies is built on.","marker":"[36]"},{"why":"It provides the background development of 2-dimensional rewriting used in the proof of Theorem 2.29.","marker":"[41]"},{"why":"It extends the rewriting framework with structure on formal 2-cells that supports the axiomatization of the fundamental 2-categories.","marker":"[42]"},{"why":"It gives the correspondence between algebraic and geometric (di)homotopy classes of dipaths in cubical complexes, used to transfer Theorem 2.29 to directed geometric realization.","marker":"[14]"},{"why":"It originates the link condition that characterizes non-positive curvature of cubical complexes, which the paper equates with its cube property.","marker":"[26]"},{"why":"It supplies standard results on CAT(0) spaces, geodesic length spaces, and cubical complexes used in the geometric realization part.","marker":"[6]"},{"why":"It supplies the geometric semantics of concurrent programs and the language model for mutexes that the precubical semantics formalizes.","marker":"[15]"}],"fun_headline_variants":["Mutex-only programs: directed homotopy equals ordinary homotopy","In mutex-only code, directed paths are ordinary homotopy classes","Non-positive curvature forces directed homotopy to be ordinary","For mutex-only programs, time orientation doesn't change homotopy","Directed vs ordinary homotopy: same for mutex-only programs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The main proof relies on the normalization claim that every formal homotopy written in the fundamental 2-groupoid can be rewritten into a canonical form, and the written proof defers several subcases to 'similar case analysis' or to figures; if any of those deferred cases fails, the reduction of homotopy to dihomotopy is unsupported.","fun_headline_variants_meta":{"raw":{"variants":["Mutex-only programs: directed homotopy equals ordinary homotopy","In mutex-only code, directed paths are ordinary homotopy classes","Non-positive curvature forces directed homotopy to be ordinary","For mutex-only programs, time orientation doesn't change homotopy","Directed vs ordinary homotopy: same for mutex-only programs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000403,"raw_usage":{"total_tokens":2091,"prompt_tokens":929,"completion_tokens":1162,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":545,"completion_tokens_details":{"reasoning_tokens":1070}},"tokens_in":545,"tokens_out":1162,"duration_ms":10960,"temperature":1.0,"reasoning_tokens":1070,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:38:22.600431+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an exhaustive computer search over small non-positively curved precubical sets for a pair of homotopic directed paths whose homotopy, written as a formal 2-cell, cannot be rewritten to square-swap form; finding such a pair would refute Theorem 2.29, while checking all finite index cases of the deferred rewriting lemmas would confirm the missing subcases.","supporting_citations":[{"cited_title":"Mimram.Sémantique des jeux asynchrones et réécriture 2-dimensionnelle","cited_arxiv_id":null,"evidence_quote":"It provides the background development of 2-dimensional rewriting used in the proof of Theorem 2.29."},{"cited_title":"Mathematical Structures in Computer Science, 21(01):65– 110, 2011","cited_arxiv_id":null,"evidence_quote":"It extends the rewriting framework with structure on formal 2-cells that supports the axiomatization of the fundamental 2-categories."},{"cited_title":"Fajstrup","cited_arxiv_id":null,"evidence_quote":"It gives the correspondence between algebraic and geometric (di)homotopy classes of dipaths in cubical complexes, used to transfer Theorem 2.29 to directed geometric realization."},{"cited_title":"Gromov.Hyperbolic groups","cited_arxiv_id":null,"evidence_quote":"It originates the link condition that characterizes non-positive curvature of cubical complexes, which the paper equates with its cube property."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It supplies standard results on CAT(0) spaces, geodesic length spaces, and cubical complexes used in the geometric realization part."},{"cited_title":"Fajstrup, É","cited_arxiv_id":null,"evidence_quote":"It supplies the geometric semantics of concurrent programs and the language model for mutexes that the precubical semantics formalizes."}],"review_version":1}