Name
Abstract | ||
|---|---|---|
We examine the complexity and expressivity of the combination of the Description Logic ALCQI with a terminological formalism based on cardinality restrictions on concepts. This combination can naturally be embedded into c2, the two variable fragment of predicate logic with counting quantifiers. We prove that ALCQI has the same complexity as c2 but does not reach its expressive power. |
Year | Venue | Keywords |
|---|---|---|
1999 | A NEXPTIME complete Description Logic Strictly Contained in C2 | variable fragment,description logic alcqi,complete description logic strictly,counting,cardinality restriction,expressivity,complexity,. description logic,expressive power,nexptime-complete description logic strictly,terminological formalism,predicate logic,description logic |
Field | DocType | Volume |
NEXPTIME,Discrete mathematics,Predicate variable,Computer science,Description logic,Cardinality,Turing machine,Modal logic,Predicate logic,Higher-order logic | Conference | 1683 |
ISSN | Citations | PageRank |
0302-9743 | 5 | 0.59 |
References | Authors | |
18 | 1 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stephan Tobies | 1 | 1599 | 158.86 |