Expressive cardinality constraints on ALCSCC concepts

In two previous publications we have, on the one hand, extended the description logic (DL) ALCQ by more expressive number restrictions using numerical and set constraints expressed in the quantifier-free fragment of Boolean Algebra with Presburger Arithmetic (QFBAPA). The resulting DL was called ALCSCC. On the other hand, we have extended the terminological formalism of the well-known description logic ALC from concept inclusions (CIs) to more general cardinality constraints expressed in QFBAPA, which we called extended cardinality constraints. Here, we combine the two extensions, i.e., we consider extended cardinality constraints on ALCSCC concepts. We show that this does not increase the complexity of reasoning, which is NExpTime-complete both for extended cardinality constraints in ALC and ALCSCC. The same is true for a restricted version of such cardinality constraints, where the complexity of reasoning decreases to ExpTime, not just for ALC, but also for ALCSCC.

• Publication year

  2019

• Venue

  ACM Symposium on Applied Computing

• Publication date

  2019-04-08

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/3297280.3297390
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Extending the Description Logic ALC with More Expressive Cardinality Constraints on Concepts

  2017influential reference
• A New Description Logic with Set Constraints and Cardinality Constraints on Role Successors

  2017influential reference
• The role of ontologies in biological and biomedical research: a functional perspective

  2015cited by this paper
• Collections, Cardinalities, and Relations

  2010cited by this paper
• Complexity of modal logics with Presburger constraints

  2010cited by this paper
• Towards Efficient Satisfiability Checking for Boolean Algebra with Presburger Arithmetic

  2007influential reference
• The description logic handbook: theory

  2003cited by this paper
• Complexity results and practical algorithms for logics in knowledge representation

  2001cited by this paper
• The Complexity of Reasoning with Cardinality Restrictions and Nominals in Expressive Description Logics

  2000influential reference
• A PSpace Algorithm for Graded Modal Logic

  1999cited by this paper
• Cardinality Restrictions on Concepts

  1994cited by this paper
• Qualifying Number Restrictions in Concept Languages

  1991influential reference
• A Correspondence Theory for Terminological Logics: Preliminary Report

  1991influential reference
• Subsumption Algorithms for Concept Description Languages

  1990influential reference
• CLASSIC: a structural data model for objects

  1989cited by this paper

• On the Complexity of Convex and Reverse Convex Prequadratic Constraints

  2023cites this paper
• NP Decision Procedure for Monomial and Linear Integer Constraints

  2022cites this paper
• NP Decision Procedure for Monomial and Linear Integer Constraints

  2022cites this paper
• Satisfiability and Query Answering in Description Logics with Global and Local Cardinality Constraints

  2020influential citation
• Description Logics That Count, and What They Can and Cannot Count (Extended Abstract)

  2020cites this paper
• Presburger Concept Cardinality Constraints in Very Expressive Description Logics - Allegro sexagenarioso ma non ritardando

  2019cites this paper
• On the Complexity and Expressiveness of Description Logics with Counting

  2019cites this paper
• On the Expressive Power of Description Logics with Cardinality Constraints on Finite and Infinite Sets

  2019cites this paper
• Satisfiability Checking and Conjunctive Query Answering in Description Logics with Global and Local Cardinality Constraints

  2019cites this paper