01083nas a2200145 4500008004100000245009400041210006900135260009600204300001200300520052400312100002300836700002100859700002000880856003700900 2008 eng d00aDescription Logic Reasoning with Decision Diagrams: Compiling SHIQ to Disjunctive Datalog0 aDescription Logic Reasoning with Decision Diagrams Compiling SHI aKarlsruhe, GermanybThe Semantic Web - ISWC 2008, 7th International Semantic Web Conference a435-4503 aWe propose a novel method for reasoning in the description logic SHIQ. After a satisfiability preserving transformation from SHIQ to the description logic ALCIb, the obtained ALCIb Tbox T is converted into an ordered binary decision diagram (OBDD) which represents a canonical model for T. This OBDD is turned into a disjunctive datalog program that can be used for Abox reasoning. The algorithm is worst-case optimal w.r.t. data complexity, and admits easy extensions with DL-safe rules and ground conjunctive queries.1 aRudolph, Sebastian1 aKrotzsch, Markus1 aHitzler, Pascal uhttp://www.knoesis.org/node/1248