Ontologies used in databases and configuration systems constantly mix abstract categories ("every employee has a manager") with numbers and dates ("a manager earns more than the people they manage"). Description logics are the formal languages behind such ontologies. They handle the numbers through concrete domains: an external structure such as the rationals with $<$, attached to individuals through features, which are functions mapping an individual to a value such as its salary. Every reasoner and complexity result for concrete domains assumes the model may be infinite. Real data is finite. This proposal starts from an observation that, as far as the research file shows, nobody has written down: adding even the simplest ordered concrete domain to a logic that has the finite model property (every satisfiable statement has a finite satisfying world) can destroy that property. Take the axiom "every $A$ has an $r$-successor that is also an $A$ and has a strictly larger value of $f$". It is satisfiable by an infinite increasing chain. It has no finite model, because the $A$-element with the largest $f$-value would need a successor with a still larger value. A reasoner that ignores finiteness will therefore call ontologies consistent when no finite database could ever satisfy them.
The proposal is to characterize and decide finite satisfiability for description logics with ordered concrete domains. The engineering target is a TBox-completion procedure, meaning one that rewrites the axioms before any reasoning starts. It detects "strict-order cycles", which are places where finiteness forces a chain of individuals to loop back on itself while the concrete constraints force values along the chain to keep increasing. For each such cycle it adds axioms that make the contradiction visible to an ordinary reasoner. The result is a reduction from finite satisfiability to standard satisfiability. Off-the-shelf tools cannot provide this decision. Model finders can only confirm a finite model when one exists. Standard reasoners can only refute statements that have no model of any size. The interesting cases sit between the two: statements with infinite models but no finite ones.
Core Claim
For order-based concrete domains (the rationals or integers with $<$ and $=$, and interval relations built on them), finite satisfiability under general axioms is decidable at the same complexity as unrestricted satisfiability. In the Horn fragment, the logics without disjunction, it reduces to unrestricted satisfiability of a completed TBox. The completion handles two causes of finite-only inconsistency together. The first is abstract: inverse roles combined with functionality force cycles. The second is new: features with strict order constraints rule those cycles out. A side consequence clarifies an open point. The complexity of description logics with concrete domains notes that discrete temporal domains are less understood than dense ones. Under finite semantics with only $<$ and $=$, the two coincide, because every finite strict order embeds into the integers. The distinction reappears only once successor or bounded-range predicates are added, and we will characterize that boundary.
Relation to Prior Work
Two results motivate the proposal by fixing the unrestricted landscape. The complexity of description logics with concrete domains shows that $\mathcal{ALC}$ with point-based and interval-based temporal domains stays EXPTIME-complete even with general TBoxes, while arithmetic domains become undecidable. It treats only unrestricted models. Our example shows that its temporal logics lack the finite model property, so its decision procedures answer a different question from the one databases ask. Description Logics with Concrete Domains and Functional Dependencies and Keys, Nominals, and Concrete Domains come closest to our topic. The first uses quasi-model filtration (collapsing a model into a bounded summary) to obtain NExpTime bounds. The second studies keys over concrete features. Both bound model summaries as a step toward deciding unrestricted satisfiability, and both assume an infinite value domain. Neither asks whether the abstract domain can be finite, which is our whole question.
Two results supply the method. The Complexity of Finite Model Reasoning in Description Logics decides finite satisfiability for $\mathcal{ALCQI}$. It encodes small local model pieces ("mosaics") as variables in a system of integer linear inequalities. Finite Model Reasoning in Horn-SHIQ avoids inequalities entirely by detecting "finmod cycles" and adding reversed axioms. Its Theorem 4 then reduces finite satisfiability to unrestricted satisfiability. We reuse cycle reversion as the backbone, and the mosaic technique for the non-Horn stretch goal. Neither paper has concrete domains. More importantly, both build finite models by duplicating or folding an infinite model, and folding is exactly the operation that a strict order constraint along a cycle forbids. That makes them constraining results as well: their constructions are unsound once our constraints are added.
On the solver side, Constraint solving for finite model finding in SMT solvers finds finite models in CVC4 by bounding the size of uninterpreted sorts (cvc4+fm). It explicitly excludes quantification over integers and reals. Reasoning with Finite Sets and Cardinality Constraints in SMT handles set cardinalities through linear integer arithmetic, but it too leaves finite interpretations of the set sort open. Consequence-based reasoners such as Sequoia: A Consequence Based Reasoner for SROIQ state that they lack datatype support. We therefore build on a tableau/Horn pipeline and do not try to extend Sequoia.
Research Program
The first strand is theory for the Horn case. The logic is Horn-$\mathcal{ALCHIQ}$ extended with an order domain $\mathcal{D}_<$. Concrete constraints are restricted to paths of length at most two, of the form $\exists (f, r f).P$ with $P \in \{<,=\}$, mirroring the restriction under which The complexity of description logics with concrete domains obtains decidability. In the Horn case the canonical model is deterministic. A finite model must fold it by identifying individuals that have the same type, meaning the same set of concepts. We define a strict-order cycle as a cycle in the folded type graph whose edges carry concrete constraints that compose to $f < f$ at some type. Abstract finmod cycles are as in Finite Model Reasoning in Horn-SHIQ. The completion $\mathcal{T}_f$ reverses abstract finmod cycles as before. For strict-order cycles, it adds axioms deriving $\bot$ at every type that is forced onto one. Cycles that compose only to $\le$ are handled differently: they force all values on the cycle to be equal, and the completion adds those equalities. The target theorem is that a concept $C$ is finitely satisfiable with respect to $\mathcal{T}$ if and only if it is satisfiable with respect to $\mathcal{T}_f$. The harder direction is the converse, building a finite model from an unrestricted model of $\mathcal{T}_f$. It requires showing that once strict cycles are removed, the remaining folded graph admits a consistent finite assignment of values. This holds because the constraint graph on a finite set of values is then acyclic modulo the equality classes, and any finite acyclic order embeds into the rationals or integers. We expect EXPTIME membership to follow from the type-graph construction. We will also measure how often the exponential-length cycles flagged in the Horn-SHIQ paper actually occur.
The second strand is the non-Horn case, as a stretch goal. For $\mathcal{ALC}(\mathcal{D}_<)$ and $\mathcal{ALCQI}(\mathcal{D}_<)$, nondeterministic choices of successors mean that no single canonical model exists. We conjecture that finite satisfiability holds exactly when there is a set of types, closed under the required witnesses, together with a choice of witness edges whose strict-constraint subgraph has no cycle. This turns the question into a well-foundedness test on a choice structure, solvable by iterated elimination in exponential time. For $\mathcal{ALCQI}$, the mosaic inequalities of The Complexity of Finite Model Reasoning in Description Logics would be annotated with order types, and acyclicity would be checked on the support of the integer solution. If the conjecture fails, we will report the counterexample and the resulting lower bound.
The third strand marks the boundary. Adding a successor predicate ($f' = f+1$) or bounded integer ranges (ages in $[0,150]$) makes discrete and dense domains diverge under finite semantics. We will determine whether the completion approach survives. Integer constraints of the form $f' \ge f + k$ around a cycle can be detected as positive-weight cycles, so we expect them to survive. With arbitrary addition we expect undecidability to persist, as it does in the unrestricted case.
The fourth strand is an implementation. The completion runs as a preprocessor. Its output goes to an unchanged reasoner that already supports order datatypes, so finite reasoning becomes available without modifying the reasoner. The preprocessor also emits a certificate for each finite inconsistency: the cycle and the chain of constraints along it. Each certificate can be checked independently.
Baselines
The naive reference point is an unrestricted reasoner run unchanged on the original ontology. It answers "satisfiable" on every instance with an infinite model. It is correct on finitely satisfiable inputs and wrong on exactly the inputs we target, so its error rate on our benchmark measures the size of the problem we are solving. The same reasoner, on the same machine, is also the baseline for the overhead question. On the original ontologies, the completion should add little to classification time. Published reference points on unrestricted semantics include HermiT at 651 seconds and MORe at 20.6 seconds on Gazetteer, from MORe: a Modular OWL Reasoner for Ontology Classification. We will rerun the host reasoner ourselves rather than compare across machines.
The strongest existing method for finding finite models is cvc4+fm from Constraint solving for finite model finding in SMT solvers. Since it cannot quantify over integers, we give it the fairest possible encoding. Concrete values become an uninterpreted sort with an axiomatized strict order (irreflexive and transitive), which is sound for finite semantics because every finite strict order embeds into $\mathbb{Q}$. It gets the same ontologies, the same per-instance time limit, and the same hardware. That paper reports no figure for finite satisfiability with concrete domains; it gives only the qualitative claim that cvc4+fm handles benchmarks "with trillions of instances". For this task, no reported result was found on Lacuna for finite satisfiability with concrete domains. Our procedure beats this baseline if it decides finitely unsatisfiable instances that cvc4+fm leaves unresolved. On finitely satisfiable instances it should be no worse than a constant factor slower.
The key ablation is plain Horn-SHIQ cycle reversion, without the strict-order cycle rule, run on the same pipeline. It isolates whether the new concrete-domain cycle detection is what matters. It should succeed on the abstract-only instances and fail on the instances whose finite inconsistency comes from order constraints.
Why not just…?
Why not just encode everything for cvc4+fm with an uninterpreted ordered sort? This is the most serious alternative, and it is the right tool when a finite model exists. Its weakness is structural. It searches cardinalities $1, 2, 3, \dots$. On an input with infinite models but no finite one, it never finds a model and never proves there is none. The authors themselves note that the approach is slower than E-matching on unsatisfiable problems (Constraint solving for finite model finding in SMT solvers). E-matching cannot help either, because an infinite model exists and so there is nothing to refute in the usual sense. The experiment below on the "finite-only inconsistent" family settles this directly. If cvc4+fm somehow terminated there, our contribution would shrink to a speedup.
Why not just discretize values into a few interval concepts and use an abstract finite reasoner? Replacing "$f$ increases along $r$" with membership in fixed buckets discards the strict chain. The example axiom then becomes finitely satisfiable: an $r$-loop that stays inside one bucket satisfies the bucketed version. So discretization is unsound in exactly our cases. It is also costly elsewhere: eager grounding of numerical relations is the state-space explosion that Towards Log-Linear Logics with Concrete Domains avoided with on-demand evaluation. We include a bucketed encoding in the experiments to show the wrong answers concretely.
Why not just extend mosaics and linear inequalities? For the non-Horn theory we do use this. As a practical engine it has a known cost: the system it builds is exponential on every input, which its authors flag (The Complexity of Finite Model Reasoning in Description Logics). That cost led Finite Model Reasoning in Horn-SHIQ to abandon the approach. Integer balancing also says nothing about whether the merged mosaics admit a consistent order on values, so an explicit acyclicity check is needed regardless. For Horn inputs, completion followed by a standard reasoner should dominate. We will check this by running a prototype mosaic encoding on the small synthetic instances.
Why not just use Datalog bounds as in PAGOdA? PAGOdA: Pay-As-You-Go Ontology Query Answering Using a Datalog Reasoner is fast; it reports an average of 12 seconds per query on LUBM, with 22 of 24 queries answered by bounds alone. But its bounds follow unrestricted semantics, so its upper bound will call our target instances satisfiable. It is a speed reference, not a competitor on correctness.
Proposed Experiments
No existing benchmark combines concrete datatypes with finite semantics; the research file lists this as a gap. We therefore build three suites. The first is parameterized synthetic families with known answers by construction, defined by cycle length, number of features, inverse functionality, and the mix of strict and non-strict constraints. The decisive member is the finite-only inconsistent family, typified by the strict-increase example. The second suite consists of ontologies from the Oxford Ontology Repository, the corpus Sequoia evaluated on 777 ontologies (Sequoia: A Consequence Based Reasoner for SROIQ), filtered for numeric or date datatype properties. We will report how many qualify before drawing any conclusion. The third suite takes LUBM-scale data with injected order constraints (for example, rank and salary monotone along the manager role) to measure overhead on data.
The metrics are the correctness of the finite-satisfiability verdict, independent checking of every unsatisfiability certificate, and validation of every satisfiable verdict by a finite model returned from cvc4+fm. We also record runtime against the host reasoner, the number and length of detected cycles, and the fraction of real ontologies whose finite and unrestricted verdicts differ. That last fraction tells us whether the phenomenon matters in practice or only in theory. If it is near zero, we will say so and position the work as a safety check.
Three results would be decisive. Our procedure must terminate with a correct "finitely unsatisfiable" verdict on the finite-only family, where cvc4+fm times out and the unrestricted reasoner answers "satisfiable". The ablation must miss every order-induced instance while matching us on abstract-only ones. And the completion's overhead on unchanged real ontologies must be a small fraction of host classification time.
References
- The complexity of description logics with concrete domains
- Description Logics with Concrete Domains and Functional Dependencies
- Keys, Nominals, and Concrete Domains
- The Complexity of Finite Model Reasoning in Description Logics
- Finite Model Reasoning in Horn-SHIQ
- Constraint solving for finite model finding in SMT solvers
- Reasoning with Finite Sets and Cardinality Constraints in SMT
- Sequoia: A Consequence Based Reasoner for SROIQ
- MORe: a Modular OWL Reasoner for Ontology Classification
- Towards Log-Linear Logics with Concrete Domains
- PAGOdA: Pay-As-You-Go Ontology Query Answering Using a Datalog Reasoner