Reasoning in Fuzzy Description Logics using Automata

Automata-based methods have been successfully employed to prove tight complexity bounds for reasoning in many classical logics, and in particular in Description Logics (DLs). Very recently, the ideas behind these automata-based approaches were adapted for reasoning also in fuzzy extensions of DLs, with semantics based either on finitely many truth degrees or the Godel t-norm over the interval[0, 1]. Clearly, due to the different semantics in these logics, the construction of the automata for fuzzy DLs is more involved than for the classical case. In this paper we provide an overview of the existing automata-based methods for reasoning in fuzzy DLs, with a special emphasis on explaining the ideas and the requirements behind them. The methods vary from deciding emptiness of automata on infinite trees to inclusions between automata on finite words. Overall, we provide a comprehensive perspective on the automata-based methods currently in use, and the many complexity results obtained through them. (c) 2015 Elsevier B.V. All rights reserved.