Noname manuscript No. (will be inserted by the editor) The Complexity of Lattice-Based Fuzzy Description Logics

the date of receipt and acceptance should be inserted later Abstract We study the complexity of reasoning in fuzzy description logics with semantics based on finite residuated lattices. For the logic SHI, we show that deciding satisfia-bility and subsumption of concepts, with or without a TBox, are EXPTIME-complete problems. InALCHI and a variant of SI, these decision problems become PSPACE-complete when restricted to acyclic TBoxes. This matches the known complexity bounds for reasoning in crisp description logics between ALC and SHI