{"id":"fa8b932d-d804-4a9a-ac1b-b3ea553cffb7","arxiv_id":"1908.09477","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":3.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper defines a conversion from non-clausal ALC connection proofs to ALC sequent proofs, using a formula tree, position substitutions, and a reduction order.","lead":"This paper proposes a way to turn proofs from the ALC connection method, an efficient automated-reasoning style, into sequent-style proofs that are easier to read. The goal is to let ontology reasoners one day explain their inferences in natural language.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Definition 21's admissibility condition is under-specified and unproven to enforce the eigenvariable conditions, so the conversion's correctness is not established.","rationale":"The reader's weakest assumption already identifies Definition 21 as the load-bearing premise and notes that no proof is given that every connection proof yields an admissible sigmaFinal. My stress-test agrees with that diagnosis but sharpens it in two ways. First, the reduction order ◁ itself is not well-defined because ⊏β′ is introduced in Definition 20 without any definition; this is an internal gap, not merely a missing proof. Second, even if one supplies the missing definition, non-reflexivity is a weaker condition than the eigenvariable/freshness condition required by the δ rules of the target sequent calculus. A dependency order can be acyclic while a δ rule is attempted when its eigenvariable appears elsewhere in the sequent, which would make the purported sequent proof invalid. This matters because the paper's headline claim is that matricial proofs generated by the ALC connection method can be converted into ALC sequent proofs; the only stated guard on that claim is Definition 21, and that guard is neither formally defined nor proven sufficient. The concern is therefore load-bearing, but it is not a demonstrated counterexample. The paper is a workshop contribution whose main algorithms live in a cited thesis, so the right verdict is conditional rather than rejection: the claim may be true, but the submitted text does not contain the evidence needed to accept it. The concrete test would either expose a counterexample to Definition 21's sufficiency or force the authors to provide the missing lemma. Since the reader already assigned CONDITIONAL for the same broad reason, the verdict should remain unchanged.","tokens_in":14948,"tokens_out":15448,"duration_ms":176926,"concrete_test":"Fix the missing definition by setting v⊏β′u iff σβ′(u)=p and v occurs in p, then implement Steps 3–4 of Section 5.2 and run them on (i) the paper's Example 1 and (ii) a minimal valid ALC query whose connection proof forces σδ to map an outer γ node to an inner δ node. For each run, check whether ◁ is reflexive and whether every l∃/r∀ step satisfies the eigenvariable condition: the eigenvariable of the rule must not occur in the lower sequent. A reflexive case in (ii) would show the method is incomplete; an eigenvariable violation with acyclic ◁ would show Definition 21's admissibility is insufficient.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central correctness gate is Definition 21: a sigmaFinal substitution is admissible when the reduction order ◁ is not reflexive, and \"in this case, it is possible to construct a sequent proof.\" This is the only condition separating convertible from non-convertible matrix proofs, yet it is never proved sufficient. Three concrete gaps attach to it. (1) ◁ is defined in Definition 20 as the transitive closure of ≺, ⊏δ, and ⊏β′, but ⊏β′ is never defined; Definition 16 defines σβ′ but not an induced ordering, so the admissibility predicate is not actually checkable from the text. (2) Even if ⊏β′ is reconstructed by analogy with ⊏δ, non-reflexivity only rules out dependency cycles; it says nothing about the eigenvariable condition for the δ rules (r∀, l∃, l¬∀, r¬∃). A node order can be acyclic while a δ rule is applied when its eigenvariable already occurs in an unrelated formula of the lower sequent, which would be an invalid sequent inference. (3) No lemma shows every non-clausal ALCθ-connection proof admits a sigmaFinal that makes ◁ acyclic while respecting the calculus's homologous-quantifier side condition (Section 4). Since the full algorithms are relegated to thesis [10], the paper as submitted does not establish that its method converts the connection proofs it claims to convert.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a method for converting proofs produced by the non-clausal ALCθ-connection calculus [5,8] into proofs in the ALC sequent calculus of Borgida et al. [4]. The conversion proceeds in four steps: (1) building a formula tree with positions, polarities, and node types; (2) assigning matrix elements to leaf positions; (3) constructing a partial sequent proof structure from connections and a reduction order; (4) completing the sequent proof. The central claim is that if the final substitution σFinal is admissible in the sense that the induced reduction order ◁ is non-reflexive, then a sequent proof can be constructed (Definition 21). The paper illustrates the method on a single nontrivial ontology query and gives a brief complexity overview.","tokens_in":15282,"tokens_out":3702,"duration_ms":37620,"significance":"If the conversion were fully established, it would provide a useful bridge between efficient connection-method reasoning for ALC and readable sequent-style proofs, with potential applications to explanation generation and user interaction with description logic reasoners. The paper has clear strengths: it targets a concrete and relevant proof calculus, it includes a detailed worked example, it explicitly defines the target sequent calculus, and it states a concrete polynomial complexity claim (O(n^4) for the search-connections algorithm). The idea of using σδ and σβ′ substitutions to manage the order of quantifier reductions is promising. However, as submitted, the central correctness claim is not established: Definition 21 is stated without proof, the reduction order is not fully defined (⊏β′ is missing), and the crucial Steps 3 and 4 of Section 5.2 are described only informally via the example. The paper also defers the actual algorithms to the author's thesis [10], so the complexity claims cannot be checked from the text.","major_comments":[{"comment":"The admissibility criterion for σFinal—non-reflexivity of the reduction order ◁—is stated to be sufficient for constructing a sequent proof, but no proof or lemma is provided that (a) every connection proof produced by the calculus of Figure 1 yields an admissible σFinal, or (b) the resulting reduction order respects the eigenvariable condition of the δ-rules (r∀, l∃, l¬∀, r¬∃) of Section 4. Non-reflexivity merely rules out cycles in ◁; it does not prevent a δ-rule from being applied when its eigenvariable already occurs elsewhere in the lower sequent, which is the actual side condition of the target sequent calculus. This is the central correctness gate of the paper, and it is not demonstrated.","section":"Section 5, Definition 21"},{"comment":"The ordering ⊏β′ is used in Definition 20 to define the reduction order ◁ as the transitive closure of ≺, ⊏δ, and ⊏β′, but Definition 16 defines only the substitution σβ′ and never defines an induced ordering ⊏β′. Without this ordering, the expression (≺∪⊏δ∪⊏β′)+ is not well-defined, and the admissibility predicate of Definition 21 cannot be checked from the text. This under-specification affects the main claim and the running example, where reduction orders involving β′ nodes are asserted without the missing definition.","section":"Section 5, Definitions 16 and 20"},{"comment":"The construction of the partial sequent proof structure is described only informally through the example. In Step 3, connections are 'analyzed' and the text states, for instance, that 'the second connection was only reached in the tree after the third connection,' but no algorithm or invariant specifies the order in which connections are processed or how paths between leaf nodes are combined into a reduction order. Step 4 is similarly informal: it says the partial structure is 'traversed,' but gives no rule for how the traversal yields the final sequent proof. Without a formal description, the conversion cannot be checked, implemented, or verified from the paper alone.","section":"Section 5.2, Steps 3 and 4"},{"comment":"The complexity claims are made about algorithms that are only named, with the statement 'All the algorithms are demonstrated in [10]'. Since the conversion procedure is not fully specified in this paper—particularly Steps 3 and 4 of Section 5.2—the polynomial complexity claim cannot be verified from the manuscript, and the correctness of the method remains dependent on an external thesis that is not available to the reader.","section":"Section 6"}],"minor_comments":[{"comment":"The axiom rule labelled (l⊤) has ⊤ on the right of the sequent, so the label should be (r⊤).","section":"Section 4, Figure 3"},{"comment":"There are several typos: 'th following formulae' in Section 2, 'eingevariable' in Section 5.1, and 'sequent poof' in Definition 20; these should be corrected.","section":"Section 2 and Section 5.1"},{"comment":"The sentence 'y was θ-substituted by y (i.e., θ(y) = a)' is confusing and appears to contain a typo; it should state which variable is substituted by a. Also, in Example 1 the FOL rendering of the second axiom contains a free variable z in the conjunct ∀k(hasPet(z,k)→Cat(k)).","section":"Example 6"},{"comment":"Several entries in Table 3 are empty (e.g., for ∃0, ∀1, ⊑0 under 'Typeδ'/'Typeγ'), which could be interpreted as missing rules; a brief note explaining that some node polarities/types have no directly corresponding rule in the target calculus would improve clarity.","section":"Table 3"},{"comment":"The running example is difficult to follow because branch names a, b, c, d are introduced without a figure showing their positions in the formula tree; a version of Figure 7 with branch annotations would substantially improve readability.","section":"Section 5.2, Step 3 example"}],"recommendation":"major_revision","confidential_remarks":"The paper is essentially a summary of the author's thesis [10], and the central proof obligations are deferred to that thesis and to informal descriptions. This may be acceptable for a workshop paper, but for this venue the conversion must be defined precisely and a correctness theorem must be proved, including the eigenvariable conditions. I would encourage the editors to request a full version with the missing definitions (notably ⊏β′), a formal specification of Steps 3 and 4, and a proof of the admissibility criterion. The topic is relevant and the worked example is valuable, but the current version does not establish the main claim."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper describes a method for converting non-clausal ALC connection proofs into ALC sequent proofs, motivated by the poor readability of connection proofs. The basic idea is sound: build a formula tree from the input query, use the connection proof to determine a reduction order, and then construct a sequent proof. The non-clausal presentation is a genuine extension of the authors' earlier clausal work, and the detailed worked example in Section 5 shows how the pieces fit together. The paper also gives a useful overview of the algorithms' polynomial complexity.\n\nWhat is actually new is the non-clausal adaptation and the explicit correspondence between connection steps and sequent rules. The central conversion itself is already claimed in the cited thesis [10], so a reader expecting the full technical development here will be disappointed. The paper is essentially a condensed exposition, which is fine for a workshop, but it means the correctness of the method rests on the thesis rather than on anything proved in this document.\n\nWhere the paper is genuinely soft is in Definition 21 and the surrounding construction. Definition 21 asserts that a sigmaFinal substitution is admissible if the reduction order is not reflexive, and that in this case a sequent proof can be constructed. This is the load-bearing step, and no proof is given. Worse, the reduction order uses a relation ⋏β′ that is never actually defined; Definition 16 defines a substitution σβ′ but not the induced ordering. And even if that relation were filled in, non-reflexivity alone does not enforce the eigenvariable condition for the δ rules. An acyclic order can still allow a δ rule to be applied when its eigenvariable occurs in an unrelated formula of the lower sequent, which would be invalid. This is not a minor typo—it blocks the main theorem as stated.\n\nSteps 3 and 4 of Section 5.2 are also described informally, with enough detail to follow the example but not enough to verify a general construction. The full algorithms are relegated to the thesis, so the paper is not self-contained. There is no machine-checked proof, no code, and no independent artifact to lean on.\n\nThe reader's and stress-test concerns land. This is a believable workshop contribution with a plausible idea and a good worked example, but the central claim—that every non-clausal ALC connection proof can be converted—is not established in this text. The paper is worth reading if you work on proof transformations or explainable DL reasoning, and it deserves referee time because an editor should ask the authors to supply the missing definitions and a real proof. But the current version should not be accepted as a correctness result.\n\nMy recommendation: send it to peer review with a clear request for a complete definition of the reduction order and a proof of the admissibility condition. If those are supplied, the paper could be solid; until then, treat it as an extended abstract.","headline":"A plausible conversion method from ALC connection proofs to sequent proofs, but the central correctness claim is not proved and the key admissibility condition is under-specified.","tokens_in":15753,"tokens_out":2487,"would_cite":false,"duration_ms":26558,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["03B35","68T15"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that non-clausal ALC connection proofs can be converted into ALC sequent proofs, preserving the original formula structure and making the proofs readable.","keywords":["connection method","description logic ALC","sequent calculus","proof conversion","proof readability","non-clausal matrix","reduction order","automated theorem proving"],"falsifier":"Exhibit one non-clausal ALC connection proof whose $\\sigma_{\\mathrm{Final}}$ substitution induces a reflexive reduction order, or run the conversion procedure on proofs emitted by a connection-based ALC reasoner and find any proof that terminates without an admissible substitution; either observation would refute the claim that all such proofs can be converted.","tokens_in":14798,"feed_emoji":"🧩","tokens_out":11696,"duration_ms":94998,"temperature":0.7,"pith_summary":"The paper tries to establish that the compact, machine-oriented proofs produced by the non-clausal ALC connection method can be converted into ALC sequent proofs, which read as structured logical arguments and translate more easily into natural language. The conversion works directly on the original formula, avoiding the disjunctive-normal-form translation that obscures the structure of a query. It proceeds in four steps: build a formula tree, assign matrix literals to tree positions, construct a partial sequent proof structure from the connections, and complete the sequent proof using a correspondence between node types and sequent rules. If the construction succeeds, a valid ALC query that a connection prover certifies can be replayed as a sequent proof whose auxiliary algorithms are polynomial, with connection search the most expensive step at $O(n^4)$. The practical payoff is that ontology reasoners built on the connection method could justify their inferences in a human-readable form.","feed_headline":"ALC connection proofs become readable sequent proofs","feed_subtitle":"A four-step conversion preserves the original query, so ontology reasoners can explain inferences.","key_machinery":"The central object is the formula tree, a syntactic tree of the input ALC formula whose nodes are labelled with positions, polarities, and types $\\alpha$, $\\alpha'$, $\\beta$, $\\beta'$, $\\gamma$, and $\\delta$; the type of a node determines which sequent rule applies, for example an $\\sqcap$-node with polarity 1 becomes $l\\sqcap$ and a $\\beta'$-node is reduced by the cut rule. The argument runs on the reduction order $\\triangleleft$, defined as the transitive closure of $(\\prec \\cup \\sqsubset_\\delta \\cup \\sqsubset_{\\beta'})^+$: $\\prec$ is the tree ordering, $\\sqsubset_\\delta$ records that a type-$\\delta$ node must be reduced before a type-$\\gamma$ node whose position it replaces, and $\\sqsubset_{\\beta'}$ records instantiations of $\\beta'$/ $\\gamma$/ $\\delta$ positions. The machinery works because the reduction order turns the spatial, path-checking information of a matrix proof into a linear schedule of sequent inferences, and the $\\sigma_{\\mathrm{Final}}$ substitution keeps track of which universal and existential positions are identified and which variables are instantiated. Admissibility of $\\sigma_{\\mathrm{Final}}$---non-reflexivity of $\\triangleleft$---is the condition that the schedule is acyclic and hence executable as a sequent proof.","core_discovery":"On the paper's own terms, the central claim is a constructive translation theorem: given an ALC query and a non-clausal $\\theta$-connection proof of it, the procedure of Section 5.2 produces a proof in the ALC sequent calculus. The bridge is the $\\sigma_{\\mathrm{Final}}$ substitution, made of a position substitution $\\sigma_\\delta$ that maps type-$\\gamma$ universal positions to type-$\\delta$ existential positions and a second substitution $\\sigma_{\\beta'}$ that maps $\\beta'$, $\\gamma$, and $\\delta$ positions to instances or $\\beta'$ positions. Connections in the matrix proof become $\\sigma_{\\mathrm{Final}}$-complementary pairs of leaf nodes, and the transitive closure of the tree ordering with the relations induced by $\\sigma_\\delta$ and $\\sigma_{\\beta'}$ yields a reduction order $\\triangleleft$ that schedules sequent rule applications. Definition 21 states that when $\\triangleleft$ is not reflexive, $\\sigma_{\\mathrm{Final}}$ is admissible and a sequent proof can be constructed; the worked example of an ontology query about old ladies, cats, and cat owners shows each connection closing a branch of the sequent proof, with $\\beta'$ nodes triggering cut rules. The conversion therefore gives a way to view the entire connection proof as a readable sequent derivation rather than a set of complementary pairs.","pith_inferences":["This suggests a practical test: instrument a connection-method prover for ALC to output $\\sigma_{\\mathrm{Final}}$ together with each proof, then check how often the reduction order is non-reflexive; if reflexive orders occur in real ontologies, the conversion would need a fallback for those cases.","One could formalize Definition 21 in a proof assistant and prove that admissibility of $\\sigma_{\\mathrm{Final}}$ is not only sufficient but also necessary for the existence of a sequent proof respecting the eigenvariable conditions, which the paper states but does not fully demonstrate.","Because the converted proofs use the cut rule for $\\beta'$ nodes, a natural next step is to study whether cut elimination applied after conversion yields a cut-free ALC sequent proof, which would connect this work to standard proof normalization.","The same tree-ordering-and-substitution recipe may extend to other non-clausal connection calculi or other description logics, since the position machinery is not specific to ALC connectives."],"forward_implications":["A connection-method proof for an ALC query no longer has to be read through the lens of clause-form transformations; the converted sequent proof operates on the original formula structure.","Each connection in the matrix proof corresponds to closing a branch of the sequent proof, with the reduction order $\\triangleleft$ fixing the order of rule applications, so the translation is deterministic once the formula tree and substitutions are fixed.","Because the main algorithms run in polynomial time, with the most expensive step at $O(n^4)$ for connection search, the conversion is practically feasible for proofs produced by connection-based ALC reasoners.","The resulting sequent proofs are better suited to automatic translation into natural-language justifications, as the paper demonstrates on the old-lady/cat-owner example.","The correspondence table between node types and sequent rules gives a direct recipe for assigning a sequent inference to every reduction step in the connection proof."],"supporting_citations":[{"why":"Supplies the ALC sequent calculus for subsumption that the converted proofs are written in.","marker":"[4]"},{"why":"Introduces the ALC theta-connection calculus, the source calculus whose proofs are converted.","marker":"[5]"},{"why":"Describes the connection-based ALC reasoner whose proofs motivate the conversion.","marker":"[8]"},{"why":"Provides the non-clausal connection calculus and decomposition/extension ideas the ALC non-clausal calculus builds on.","marker":"[9]"},{"why":"Contains the detailed algorithms and complexity analysis for the conversion procedure.","marker":"[10]"},{"why":"Establishes the connection-method framework and the readability problem caused by clause-form translation.","marker":"[3]"},{"why":"Supplies the cut-elimination theorem used in the sequent calculus setting.","marker":"[6]"}],"fun_headline_variants":["ALC connection proofs get a readable sequent form","New method turns ALC connection proofs into sequents","From matrix to sequent: readable ALC proofs","Untangling ALC proofs into clear sequent derivations","Sequent conversion explains ALC connection proofs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that every non-clausal ALC connection proof yields an admissible $\\sigma_{\\mathrm{Final}}$ substitution---that is, one whose reduction order is not reflexive---because the paper asserts but does not prove this for all connection proofs.","fun_headline_variants_meta":{"raw":{"variants":["ALC connection proofs get a readable sequent form","New method turns ALC connection proofs into sequents","From matrix to sequent: readable ALC proofs","Untangling ALC proofs into clear sequent derivations","Sequent conversion explains ALC connection proofs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000204,"raw_usage":{"total_tokens":1403,"prompt_tokens":973,"completion_tokens":430,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":589,"completion_tokens_details":{"reasoning_tokens":355}},"tokens_in":589,"tokens_out":430,"duration_ms":4894,"temperature":1.0,"reasoning_tokens":355,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:10:56.007872+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit one non-clausal ALC connection proof whose $\\sigma_{\\mathrm{Final}}$ substitution induces a reflexive reduction order, or run the conversion procedure on proofs emitted by a connection-based ALC reasoner and find any proof that terminates without an admissible substitution; either observation would refute the claim that all such proofs can be converted.","supporting_citations":[{"cited_title":"Borgida, E","cited_arxiv_id":null,"evidence_quote":"Supplies the ALC sequent calculus for subsumption that the converted proofs are written in."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Describes the connection-based ALC reasoner whose proofs motivate the conversion."},{"cited_title":"Otten (2011): A Non-clausal Connection Calculus","cited_arxiv_id":null,"evidence_quote":"Provides the non-clausal connection calculus and decomposition/extension ideas the ALC non-clausal calculus builds on."},{"cited_title":"Palmeira (2017): Conversion of Proof in Description LogicALC Generated by Connection Method into Sequents","cited_arxiv_id":null,"evidence_quote":"Contains the detailed algorithms and complexity analysis for the conversion procedure."},{"cited_title":"Bibel (1993): Deduction - automated logic","cited_arxiv_id":null,"evidence_quote":"Establishes the connection-method framework and the readability problem caused by clause-form translation."},{"cited_title":"Cambridge University Press","cited_arxiv_id":null,"evidence_quote":"Supplies the cut-elimination theorem used in the sequent calculus setting."}],"review_version":1}