Search

The problem of minimizing finite fuzzy interpretations in fuzzy description logics (FDLs) is worth studying. For example, the structure of a fuzzy/weighted social network can be treated as a fuzzy interpretation in FDLs, where actors are individuals and actions are roles. Minimizing the structure of a fuzzy/weighted social network makes it more compact, thus making network analysis tasks more efficient. In this work, we study the problem of minimizing a finite fuzzy interpretation in a FDL by using the largest crisp auto-bisimulation. The considered FDLs use the Baaz projection operator and their semantics is specified using an abstract algebra of fuzzy truth values, which can be any linear and complete residuated lattice. We provide an efficient algorithm with a complexity of $O((m \log{l} + n) \log{n})$ for minimizing a given finite fuzzy interpretation $\mathcal{I}$, where $n$ is the size of the domain of $\mathcal{I}$, $m$ is number of nonzero instances of atomic roles of $\mathcal{I}$ and $l$ is the number of different fuzzy values used for instances of atomic roles of $\mathcal{I}$. We prove that the fuzzy interpretation returned by the algorithm is minimal among the ones that preserve fuzzy TBoxes and ABoxes under certain conditions.

Fuzzy graph-based structures such as fuzzy automata, fuzzy labeled transition systems, fuzzy Kripke models, fuzzy social networks and fuzzy interpretations in fuzzy description logics are useful in various applications. Given two states, two actors or two individuals $x$ and $x'$ in such structures $G$ and $G'$, respectively, the similarity degree between them can be defined to be $Z(x,x')$, where $Z$ is the greatest fuzzy bisimulation between $G$ and $G'$ w.r.t. some t-norm-based fuzzy logic. Such a similarity measure has the Hennessy-Milner property of fuzzy bisimulations as a strong logical foundation. A fuzzy bisimulation between a fuzzy structure $G$ and itself is called a fuzzy auto-bisimulation of $G$. The greatest fuzzy auto-bisimulation of an image-finite fuzzy graph-based structure is a fuzzy equivalence relation. It is useful for classification and clustering. In this paper, we design an efficient algorithm with the complexity $O((m\log{l} + n)\log{n})$ for computing the fuzzy partition corresponding to the greatest fuzzy auto-bisimulation of a finite fuzzy labeled graph $G$ under the G\"odel semantics, where $n$, $m$ and $l$ are the number of vertices, the number of non-zero edges and the number of different fuzzy degrees of edges of $G$, respectively. Our notion of fuzzy partition is novel, defined only for finite sets with respect to the G\"odel t-norm, with the aim to facilitate the computation of the greatest fuzzy auto-bisimulation. By using that algorithm, we also provide an algorithm with the complexity $O(m\cdot\log{l}\cdot\log{n} + n^2)$ for computing the greatest fuzzy bisimulation between two finite fuzzy labeled graphs under the G\"odel semantics. This latter algorithm is better (has a lower complexity order) than the previously known algorithms for the considered problem. Our algorithms can be restated for the other mentioned fuzzy graph-based structures.

Fuzzy structures such as fuzzy automata, fuzzy transition systems, weighted social networks and fuzzy interpretations in fuzzy description logics have been widely studied. For such structures, bisimulation is a natural notion for characterizing indiscernibility between states or individuals. There are two kinds of bisimulations for fuzzy structures: crisp bisimulations and fuzzy bisimulations. While the latter fits to the fuzzy paradigm, the former has also attracted attention due to the application of crisp equivalence relations, for example, in minimizing structures. Bisimulations can be formulated for fuzzy labeled graphs and then adapted to other fuzzy structures. In this article, we present an efficient algorithm for computing the partition corresponding to the largest crisp bisimulation of a given finite fuzzy labeled graph. Its complexity is of order $O((m\log{l} + n)\log{n})$, where $n$, $m$ and $l$ are the number of vertices, the number of nonzero edges and the number of different fuzzy degrees of edges of the input graph, respectively. We also study a similar problem for the setting with counting successors, which corresponds to the case with qualified number restrictions in description logics and graded modalities in modal logics. In particular, we provide an efficient algorithm with the complexity $O((m\log{m} + n)\log{n})$ for the considered problem in that setting.

Like bisimulations, simulations and directed simulations are used for analyzing graph-based structures such as automata, labeled transition systems, linked data networks, Kripke models and interpretations in description logic. Simulations characterize the class of existential modal formulas, whereas directed simulations characterize the class of positive modal formulas. These notions are worth studying. For example, one may be interested in checking whether a given finite automaton simulates another or whether an object in a linked data network has all positive properties that another object has. To deal with vagueness and uncertainty, fuzzy graph-based structures are used instead of crisp ones. In this article, we design efficient algorithms with the complexity $O((m+n)n)$ for computing the largest crisp simulation and the largest crisp directed simulation between two finite fuzzy labeled graphs, where $n$ is the number of vertices and $m$ is the number of nonzero edges of the input fuzzy graphs. We also adapt them to computing the largest crisp simulation and the largest crisp directed simulation between two finite fuzzy automata.

Description logics (DLs) are a suitable formalism for representing knowledge about domains in which objects are described not only by attributes but also by binary relations between objects. Fuzzy extensions of DLs can be used for such domains when data and knowledge about them are vague and imprecise. One of the possible ways to specify classes of objects in such domains is to use concepts in fuzzy DLs. As DLs are variants of modal logics, indiscernibility in DLs is characterized by bisimilarity. The bisimilarity relation of an interpretation is the largest auto-bisimulation of that interpretation. In DLs and their fuzzy extensions, such equivalence relations can be used for concept learning. In this paper, we define and study fuzzy bisimulation and bisimilarity for fuzzy DLs under the G��del semantics, as well as crisp bisimulation and strong bisimilarity for such logics extended with involutive negation. The considered logics are fuzzy extensions of the DL $\mathcal{ALC}_{reg}$ (a variant of PDL) with additional features among inverse roles, nominals, (qualified or unqualified) number restrictions, the universal role, local reflexivity of a role and involutive negation. We formulate and prove results on invariance of concepts under fuzzy (resp. crisp) bisimulation, conditional invariance of fuzzy TBoxex/ABoxes under bisimilarity (resp. strong bisimilarity), and the Hennessy-Milner property of fuzzy (resp. crisp) bisimulation for fuzzy DLs without (resp. with) involutive negation under the G��del semantics. Apart from these fundamental results, we also provide results on using fuzzy bisimulation to separate the expressive powers of fuzzy DLs, as well as results on using strong bisimilarity to minimize fuzzy interpretations., This is a revised and corrected version of the publication "Bisimulation and bisimilarity for fuzzy description logics under the G\"odel semantics", Fuzzy Sets and Systems 388: 146-178 (2020)

We present the first direct tableau decision procedure with the ExpTime complexity for HPDL (Hybrid Propositional Dynamic Logic). It checks whether a given ABox (a finite set of assertions) in HPDL is satisfiable. Technically, it combines global caching with checking fulfillment of eventualities and dealing with nominals. Our procedure contains enough details for direct implementation and has been implemented for the TGC2 (Tableaux with Global Caching) system. As HPDL can be used as a description logic for representing and reasoning about terminological knowledge, our procedure is useful for practical applications.

We give the first cut-free ExpTime (optimal) tableau decision procedure for the logic CPDLreg, which extends Converse-PDL with regular inclusion axioms characterized by finite automata. The logic CPDLreg is the combination of Converse-PDL and regular grammar logic with converse. Our tableau decision procedure uses global state caching and has been designed to increase efficiency and allow various optimization techniques, including on-the-fly propagation of local and global (in)consistency.

We give the first cut-free ExpTime (optimal) tableau decision procedure for checking satisfiability of a knowledge base in the description logic SHI, which extends the description logic ALC with transitive roles, inverse roles and role hierarchies., Comment: a long version of the paper "Linh Anh Nguyen. A Cut-Free ExpTime Tableau Decision Procedure for the Description Logic SHI. In Proceedings of ICCCI'2011, LNAI 6922, pages 572-581, Springer-Verlag, 2011", 27 pages