{"id":"535835e7-c607-4bde-b974-7c125b6aa993","arxiv_id":"2508.05350","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Pure minimal model satisfiability is undecidable for EL and ExpSpace-hard for DL-Lite_horn.","lead":"This paper studies the complexity of reasoning with minimal models in description logics. It shows that pure minimal model satisfiability is undecidable even for the lightweight logic EL, and ExpSpace-hard for DL-Lite_horn.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Undecidability proof's reduction is not inspectable; minimal-model semantics and encoding may harbor hidden assumptions.","rationale":"The reader's weakest-assumption correctly identified the reduction as the most fragile step. My independent reading echoes this but adds that the semantics of 'pure minimal models' is itself a source of ambiguity: the abstract does not specify whether the domain is fixed or variable, and this choice materially affects whether the stated problem is even well-defined. Since only the abstract is available, no technical proof can be checked; therefore the verdict should remain UNVERDICTED (the reader's current verdict) and my concern does not shift it. I agree with the reader that the central claim is plausible and significant, but unverified without the full technical construction.","tokens_in":706,"tokens_out":5860,"duration_ms":67563,"concrete_test":"Obtain the full proof and verify the main reduction lemma. Extract the TBox used for the undecidability proof and check that every axiom is expressible in EL (e.g., no role inverses, nominals, or complex role inclusions). Then independently re-derive the equivalence: for an instance of the source problem, a model M satisfies the target concept and is minimal under the stated semantics iff the instance has a solution. As a sanity test, take a small solvable and a small unsolvable tiling instance, encode them according to the reduction, and use a finite-model enumerator (with a suitable minimality check) to confirm that the solvable one has at least one minimal model and the unsolvable one has none. If the lemma breaks on such concrete examples, the undecidability claim is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The headline claim—concept satisfiability in minimal models is undecidable already for EL—rests on a reduction from an undecidable problem (e.g., tiling or Minsky halting) to EL minimal-model satisfiability. The abstract does not define the exact 'pure' minimal-model semantics: is the domain fixed or variable? Are all predicate extensions minimized component-wise, and are minimal models guaranteed to exist? This is load-bearing because if the domain is allowed to vary, minimization can yield trivial or missing minimal models, making 'satisfiable in a minimal model' ill-defined; if the domain is fixed, the reduction must ensure that every model of the encoded TBox and concept contains a copy of the computation, and that the minimality pre-order selects exactly the valid computations. EL's existential restrictions force the existence of successors, so the encoding must prevent spurious elements without using expressive power beyond EL (no role inverses, nominals, or disjunction). The abstract gives no evidence that the reduction preserves satisfiability. Without inspecting the construction, a subtle flaw—such as an encoding that accidentally creates unintended minimal models or fails on boundary instances—cannot be dismissed. Thus the central claim is plausible but unverified.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies 'pure' minimal model reasoning in Description Logics, where the extensions of all predicates are required to be minimal. Based on the abstract, the main claims are: (1) concept satisfiability in minimal models is undecidable already for the lightweight DL EL; (2) undecidability extends to a very restricted fragment of tuple-generating dependencies; (3) acyclicity conditions on the TBox bring worst-case complexity below double exponential time and connect the setting to pointwise circumscription; (4) for DL-Lite_horn, minimal-model concept satisfiability is ExpSpace-hard, in contrast to a known positive result for DL-Lite_core. The abstract contains no formal definitions, theorem statements, or proof sketches; the full text was not available for review.","tokens_in":982,"tokens_out":2196,"duration_ms":23082,"significance":"If the results are correct, they are significant. They would close a natural open direction for 'pure' minimal-model reasoning in a prominent lightweight DL, showing that this form of minimization is much harder than the underlying EL reasoning. The extension to TGDs and the DL-Lite_horn lower bound also map the boundary of tractability. The claimed connection to pointwise circumscription and the acyclicity conditions could provide a useful route to decidable fragments. The paper appears to be a pure theoretical contribution without empirical fitting, so there is no evident circularity. However, because the full text is unavailable, none of these claims can be verified from the submitted material.","major_comments":[{"comment":"The notion of minimal model is not defined. Key questions include: are all predicates minimized component-wise, and is the domain fixed or allowed to vary? Is the minimization pre-order inclusion on extensions? Most importantly, are minimal models guaranteed to exist for every satisfiable input? If the domain can vary, minimization may produce models with no minimal element, making 'satisfiable in a minimal model' ill-defined. These choices are load-bearing for the undecidability and hardness claims and must be specified in the full text.","section":"Abstract"},{"comment":"The central claim — undecidability of concept satisfiability in minimal models for EL — rests on a reduction that is not visible. A convincing proof must exhibit an encoding of an undecidable problem (e.g., tiling or Minsky machines) into an EL TBox and a concept such that satisfiability in a minimal model exactly encodes a valid computation. In particular, the encoding must rule out spurious infinite or cyclic models using only EL's limited expressivity (existential restrictions, conjunctions, no inverses/nominals/disjunction), and the minimality pre-order must select exactly the intended models. Without the construction, this claim cannot be assessed.","section":"Abstract"},{"comment":"The ExpSpace-hardness claim for DL-Lite_horn is presented as a second main result, but no proof strategy is given. Since DL-Lite_horn is closely tied to first-order rewritability, the lower bound likely relies on a careful encoding of an ExpSpace-hard problem into a DL-Lite_horn TBox and a minimal-model satisfiability query. The full paper must provide the reduction and its correctness proof; the abstract alone does not substantiate the claim.","section":"Abstract"}],"minor_comments":[{"comment":"The phrase 'below double exponential time' is imprecise. Please state the exact complexity class (e.g., in 2-EXPTIME, or in co-N2EXP) and the matching lower bound, if applicable.","section":"Abstract"},{"comment":"The 'acyclicity conditions' on the TBox are not described. A short explanation or reference to the relevant definitions would help readers understand the scope of the decidability result.","section":"Abstract"},{"comment":"The 'data complexity' result is mentioned without a concrete statement. Please specify the complexity class and whether it applies to all the DLs considered.","section":"Abstract"},{"comment":"The connection to 'pointwise circumscription' is stated as a conclusion but not elaborated. A sentence describing the relationship would make the abstract more self-contained.","section":"Abstract"}],"recommendation":"uncertain","confidential_remarks":"This is an abstract-only submission; the full text was not supplied. I cannot verify any of the formal claims. The topic is timely and the results would be significant if correct, but the absence of proofs is an insurmountable barrier to acceptance. I recommend requesting the full manuscript before proceeding with a substantive review. No concerns about circularity or improper empirical practices are apparent from the abstract."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things. First, this abstract claims a genuine gap-closer: concept satisfiability in pure minimal models is undecidable already for EL, and ExpSpace-hard for DL-Lite_horn. If the proofs hold, that's a real result for the DL community. Second, this is an abstract-only submission. No proofs, no definitions, no construction. I can assess the framing but not the math.\n\nWhat's new and good: the abstract explicitly targets pure minimal models, which the authors rightly say have been largely uncharted next to circumscription-style minimization of selected predicates. The claimed EL undecidability is a natural but stronger result than the known high complexity for circumscriptive DLs. The connection to tuple-generating dependencies and the acyclicity conditions that restore decidability below double exponential time are also plausible and would be useful context. The final note about DL-Lite_horn extends the known positive DL-Lite_core result in the right direction.\n\nWhere I can't fully sign on: the load-bearing reduction is invisible. The stress-test note is on target. I need to see whether the domain is fixed or variable, whether all predicates are minimized component-wise, and how EL's existential restrictions are prevented from creating spurious witnesses that break minimality. The abstract gives no evidence that the reduction preserves satisfiability. That is not a strike against the authors—it's the nature of an abstract—but it means the central claim is plausible rather than verified. A subtle flaw in the reduction would not show up here.\n\nI give the paper credit for being a pure theorem result with no empirical fitting, so there is no circularity concern. The claims are crisp and falsifiable by inspecting the proofs. The title is cheeky but accurate: this is a negative result that says don't try to get cheap minimal-model reasoning in EL.\n\nWho is this for? Researchers working on nonmonotonic reasoning in description logics, complexity of DLs, and the relation to TGDs. It deserves a serious referee. The abstract is enough to justify peer review; the complete manuscript with the reduction should be read before anyone cites it. My recommendation: send it out, and if the reduction is clean, it's a solid contribution.","headline":"Plausible and potentially significant negative results for EL and DL-Lite_horn, but abstract-only means the core reduction is unverifiable from this text.","tokens_in":1379,"tokens_out":1366,"would_cite":false,"duration_ms":16478,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68T27","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"Pure minimal-model satisfiability is undecidable already for the description logic EL.","keywords":["minimal models","description logics","EL","DL-Lite_horn","circumscription","undecidability","computational complexity","tuple-generating dependencies"],"falsifier":"The most direct way to test the claim is to inspect the announced reduction. A reader could look for an $\\mathcal{EL}$ TBox and concept arising from the reduction where the concept is minimally satisfiable even though the encoded source instance is not a positive instance, or, conversely, a case where every model satisfying the encoding is automatically non-minimal, which would mean the reduction encodes an empty problem rather than the intended undecidable one.","tokens_in":677,"feed_emoji":"🧩","tokens_out":4640,"duration_ms":49583,"temperature":0.7,"pith_summary":"The paper tries to chart the complexity of pure minimal-model reasoning in Description Logics, where 'minimal' means every predicate's extension is minimized simultaneously. It claims this is not merely hard but undecidable: concept satisfiability under this semantics is undecidable already for $\\mathcal{EL}$, one of the most widely used lightweight DLs. This matters because minimal models are a standard formal backbone of nonmonotonic knowledge representation; if pure minimality makes a simple logic undecidable, automated reasoning services based on it cannot be built without further restrictions. The paper also shows ExpSpace-hardness for DL-Lite$_{\\text{horn}}$, and identifies acyclicity conditions that restore decidability below double-exponential time.","feed_headline":"Minimal-model reasoning is undecidable even for EL","feed_subtitle":"Even the lightweight EL logic cannot decide satisfiability when all predicates must be minimal.","key_machinery":"The central object is the pure minimal model: a model in which the extension of every predicate is minimal under set inclusion, with no predicates left free to vary. The argument turns on a reduction that encodes an undecidable source problem into $\\mathcal{EL}$ concept satisfiability, arranged so that the existence of a minimal model exactly mirrors a valid computation. The paper additionally uses acyclicity restrictions on the TBox as a structural condition that breaks the encoding and restores decidability; the connection to pointwise circumscription provides a bridge to existing complexity results.","core_discovery":"The paper establishes that checking whether a concept has a satisfiable pure minimal model—one in which the extension of every predicate is simultaneously minimal—is undecidable for the description logic $\\mathcal{EL}$. In the same setting, it obtains ExpSpace-hardness for DL-Lite$_{\\text{horn}}$, extending earlier positive decidability results known for DL-Lite$_{\\text{core}}$. To regain decidability, the paper proposes acyclicity conditions on the TBox, bringing the worst-case complexity below double-exponential time and drawing a connection to pointwise circumscription. The undecidability also transfers to a very restricted fragment of tuple-generating dependencies.","pith_inferences":["A practical consequence the authors leave implicit: any implemented reasoner for minimal-model semantics must either impose acyclicity, minimize only selected predicates as in circumscription, or settle for incomplete algorithms.","The gap between decidable DL-Lite$_{\\text{core}}$ and ExpSpace-hard DL-Lite$_{\\text{horn}}$ suggests a sharp boundary; a natural next test is whether a single Horn axiom is enough to trigger the hardness.","If pure minimality is undecidable in $\\mathcal{EL}$, then ontology-mediated query answering under minimal-model semantics likely faces a similar barrier for queries that must inspect the minimal model itself.","The acyclicity conditions that restore decidability may transfer to other lightweight DLs, but whether they are necessary rather than merely sufficient remains open."],"forward_implications":["For unrestricted $\\mathcal{EL}$ TBoxes, there is no general algorithm that decides pure minimal-model concept satisfiability.","The undecidability barrier is not an artifact of DL syntax, since it extends to a very restricted fragment of tuple-generating dependencies.","Acyclicity conditions on the TBox yield decidable fragments with worst-case complexity below double-exponential time.","DL-Lite$_{\\text{horn}}$ minimal-model satisfiability is ExpSpace-hard, so the positive result for DL-Lite$_{\\text{core}}$ does not extend to the Horn extension.","The paper's data-complexity results complete the complexity picture for reasoning when only the data, not the ontology, varies."],"supporting_citations":[],"fun_headline_variants":["Minimal-model satisfiability undecidable even in EL","Pure minimal models: undecidable for EL logic","EL minimal-model reasoning is undecidable","Even EL can't decide pure minimal models","DL-Lite_horn minimal models: ExpSpace-hard"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The load-bearing premise is that the reduction from an undecidable problem to $\\mathcal{EL}$ minimal-model satisfiability faithfully encodes the source problem; if the encoding needs auxiliary predicates or constraints that $\\mathcal{EL}$ cannot force to be minimal or fixed, the undecidability proof collapses.","fun_headline_variants_meta":{"raw":{"variants":["Minimal-model satisfiability undecidable even in EL","Pure minimal models: undecidable for EL logic","EL minimal-model reasoning is undecidable","Even EL can't decide pure minimal models","DL-Lite_horn minimal models: ExpSpace-hard"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000288,"raw_usage":{"total_tokens":1517,"prompt_tokens":729,"completion_tokens":788,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":473,"completion_tokens_details":{"reasoning_tokens":714}},"tokens_in":473,"tokens_out":788,"duration_ms":7788,"temperature":1.0,"reasoning_tokens":714,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T23:22:49.082160+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The most direct way to test the claim is to inspect the announced reduction. A reader could look for an $\\mathcal{EL}$ TBox and concept arising from the reduction where the concept is minimally satisfiable even though the encoded source instance is not a positive instance, or, conversely, a case where every model satisfying the encoding is automatically non-minimal, which would mean the reduction encodes an empty problem rather than the intended undecidable one.","supporting_citations":[],"review_version":1}