Robustness of Constraint Automata for Description Logics with Concrete Domains

Stéphane Demri, Tianwen Gu · 2026

Read Robustness of Constraint Automata for Description Logics with Concrete Domains by Stéphane Demri, Tianwen Gu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-19644.txt.

Description

Stéphane Demri and Tianwen Gu work on the logic used to describe structured knowledge. Description logics power ontologies, formal maps of concepts and relations. Adding concrete domains lets an ontology talk about real objects, like numbers and strings, with fixed relations on them. A basic question is whether a description is consistent, and how hard that is to decide.

Earlier work answered with tableau methods or type elimination. The authors take an automata-based route instead. They enrich the automaton's transitions with symbolic constraints. Their method reaches the optimal upper bound on complexity for the problem. Automata give a clean, reusable machinery for reasoning tasks. The result strengthens the theory behind ontology tools.

Catalog record

CREATORStéphane Demri, Tianwen Gu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE190 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-19644

Browse the full library · About the Tower of Babel