Name
Abstract | ||
|---|---|---|
The standard reasoning problem, concept satisfiability, in the basic description logic ALC is PSPACE-complete, and it is EXPTIME-complete in the presence of unrestricted axioms. Several fragments of ALC, notably logics in the FL, EL, and DL-Lite families, have an easier satisfiability problem; sometimes it is even tractable. We classify the complexity of the standard satisfiability problems for all possible Boolean and quantifier fragments of ALC in the presence of general axioms. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.tcs.2013.02.009 | theory and applications of models of computation |
Keywords | DocType | Volume |
satisfiability problem,basic description logic,generalized satisfiability,description logic alc,general axiom,easier satisfiability problem,general concept inclusion,dl-lite family,possible boolean,standard satisfiability problem,quantifier fragment,polynomial time,concept satisfiability,standard reasoning problem,unrestricted axiom,standard variant,description logic,satisfiability | Journal | 505, |
ISSN | Citations | PageRank |
0304-3975 | 2 | 0.37 |
References | Authors | |
30 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arne Meier | 1 | 126 | 19.00 |
| Thomas Schneider | 2 | 36 | 2.91 |