We present and discuss some novel and somewhat surprising complexity results for a basic but significant fuzzy description logic (DL) which extends the classical language. In particular we show that checking the consistency of a concept or a KB in fuzzy DLs has a complexity which jumps from linear-time to EXPTIME-complete, while the subsumption problem is always (at least) as hard as in crisp DLs.
Some complexity results on fuzzy description logics / P.A. Bonatti, A.G.B. Tettamanzi (LECTURE NOTES IN ARTIFICIAL INTELLIGENCE). - In: Fuzzy logic and applications / [a cura di] Vito Di Gesù, Francesco Masulli, Alfredo Petrosino. - Berlin : Springer, 2006. - ISBN 3-540-31019-3. - pp. 19-24 (( Intervento presentato al 5. convegno International Workshop on Fuzzy Logic and Applications (WILF) tenutosi a Napoli nel 2003 [10.1007/10983652].
Some complexity results on fuzzy description logics
A.G.B. Tettamanzi
2006
Abstract
We present and discuss some novel and somewhat surprising complexity results for a basic but significant fuzzy description logic (DL) which extends the classical language. In particular we show that checking the consistency of a concept or a KB in fuzzy DLs has a complexity which jumps from linear-time to EXPTIME-complete, while the subsumption problem is always (at least) as hard as in crisp DLs.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
