Using model theory to find decidable and tractable description logics with concrete domains
From MaRDI portal
Publication:2090131
DOI10.1007/s10817-022-09626-2OpenAlexW4225389498MaRDI QIDQ2090131
Publication date: 24 October 2022
Published in: Journal of Automated Reasoning (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10817-022-09626-2
convexityhomogeneitydecidabilitydescription logicconstraint satisfactiontractability\(\omega\)-categoricityconcrete domainsfinite boundedness\(\omega\)-admissibilityGCIsP-admissibility
Cites Work
- Maintaining knowledge about temporal intervals
- Reducts of the random partial order
- An automata-theoretic approach to constraint LTL
- A tableau algorithm for description logics with concrete domains and general TBoxes
- Maximal infinite-valued constraint languages
- Universal graphs with forbidden subgraphs and algebraic closure
- Datalog and constraint satisfaction with infinite templates
- An algebraic view on p-admissible concrete domains for lightweight description logics
- Description logics with concrete domains and general concept inclusions revisited
- ASNP: a tame fragment of existential second-order logic
- Relation algebras of intervals
- A survey of homogeneous structures
- Satisfiability of \(\mathrm{ECTL}^*\) with local tree constraints
- On undecidability bounds for matrix decision problems
- On the Complexity of MMSNP
- On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction
- An Introduction to Description Logic
- Constraint Satisfaction with Countable Homogeneous Templates
- The complexity of temporal constraint satisfaction problems
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Discrete Temporal Constraint Satisfaction Problems
- Homomorphism and embedding universal structures for restricted classes
- Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction
- A complexity dichotomy for poset constraint satisfaction
- A Dichotomy for First-Order Reducts of Unary Structures
- Equations in oligomorphic clones and the constraint satisfaction problem for ω-categorical structures
- A universal-algebraic proof of the complexity dichotomy for Monotone Monadic SNP
- Constraint Satisfaction Problems for Reducts of Homogeneous Graphs
- The Complexity of Phylogeny Constraint Satisfaction Problems
- Countable homogeneous relational structures and ℵ0-categorical theories
- STACS 2005
- A family of countable homogeneous graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
