Search

Fuzzy transition systems offer a robust framework for modeling and analyzing systems with inherent uncertainties and imprecision, which are prevalent in real-world scenarios. As their extension, nondeterministic fuzzy transition systems (NFTSs) have been studied in a considerable number of works. Wu et al. (2018) provided an algorithm for computing the greatest crisp bisimulation of a finite NFTS $\mathcal{S} = \langle S, A, \delta \rangle$, with a time complexity of order $O(|S|^4 \cdot |\delta|^2)$ under the assumption that $|\delta| \geq |S|$. Qiao {\em et al.} (2023) provided an algorithm for computing the greatest fuzzy bisimulation of a finite NFTS $\mathcal{S}$ under the G\"odel semantics, with a time complexity of order $O(|S|^4 \cdot |\delta|^2 \cdot l)$ under the assumption that $|\delta| \geq |S|$, where $l$ is the number of fuzzy values used in $\mathcal{S}$ plus 1. In this work, we provide efficient algorithms for computing the partition corresponding to the greatest crisp bisimulation of a finite NFTS $\mathcal{S}$, as well as the compact fuzzy partition corresponding to the greatest fuzzy bisimulation of $\mathcal{S}$ under the G\"odel semantics. Their time complexities are of the order $O((size(\delta) \log{l} + |S|) \log{(|S| + |\delta|)})$, where $l$ is the number of fuzzy values used in $\mathcal{S}$ plus 2. When $|\delta| \geq |S|$, this order is within $O(|S| \cdot |\delta| \cdot \log^2{|\delta|})$. The reduction of time complexity from $O(|S|^4 \cdot |\delta|^2)$ and $O(|S|^4 \cdot |\delta|^2 \cdot l)$ to $O(|S| \cdot |\delta| \cdot \log^2{|\delta|})$ is a significant contribution of this work. In addition, we introduce nondeterministic fuzzy labeled transition systems, which extend NFTSs with fuzzy state labels, and we define and provide results on simulations and bisimulations between them.

In this paper we introduce a new type of approximate state reductions where the behaviors of the reduced and the original automaton do not have to be identical, but they must match on all words of length less than or equal to some given natural number. We provide four methods for performing such reductions., Comment: In Proceedings AFL 2023, arXiv:2309.01126

Simulations and bisimulations are well-established notions in crisp/fuzzy automata theory and are widely used to compare the behaviors of automata. Their main drawback is that they compare the behaviors of fuzzy automata in a crisp manner. Recently, fuzzy simulations and fuzzy bisimulations have been defined for fuzzy automata as a kind of approximate simulations and approximate bisimulations that compare the behaviors of fuzzy automata in a fuzzy manner. However, they still suffer from serious shortcomings. First, they still cannot correlate all fuzzy automata that are intuitively "more or less" (bi)similar. Second, the currently known algorithms for computing the greatest fuzzy simulation or bisimulation between two finite fuzzy automata have an exponential time complexity when the {\L}ukasiewicz or product structure of fuzzy values is used. This work deals with these problems, providing approximations of fuzzy simulations and fuzzy bisimulations. We define such approximations via a novel notion of decreasing sequences of fuzzy relations whose infima are, under some conditions, fuzzy simulations (respectively, bisimulations). We call such a sequence a depth-bounded fuzzy simulation (respectively, bisimulation), as the $n$th element from the sequence compares the behaviors of fuzzy automata, but only for words with a length bounded by $n$. We further provide a logical characterization of the greatest depth-bounded fuzzy simulation or bisimulation between two fuzzy automata by proving that it satisfies the corresponding Hennessy-Milner property. Finally, we provide polynomial-time algorithms for computing the $n$th component of the greatest depth-bounded fuzzy simulation (respectively, bisimulation) between two finite fuzzy automata.

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.

Simulations and bisimulations between two fuzzy automata over a complete residuated lattice were defined by \'Ciri\'c et al. (2012) as fuzzy relations between the sets of states of the automata. However, they act as a crisp relationship between the automata. In particular, if there exists a (forward) bisimulation between two fuzzy automata, then the fuzzy languages recognized by them are crisply equal. Approximate simulations and bisimulations introduced by Stanimirovi\'c et al. (2020) aim at fuzzifying this phenomenon. However, they are defined only for fuzzy automata over a complete Heyting algebra and do not give the exact relationship between states of the automata. In this article, we introduce and study fuzzy simulations and bisimulations between fuzzy automata over a complete residuated lattice. These notions are novel and have good properties. They are defined for fuzzy automata over any complete residuated lattice. We prove that the fuzzy language recognized by a fuzzy automaton is fuzzily preserved by fuzzy simulations and fuzzily invariant under fuzzy bisimulations. We also prove that the notions of fuzzy simulation and bisimulation have the Hennessy-Milner properties, which are a logical characterization of the greatest fuzzy simulation or bisimulation between two fuzzy automata. In addition, we provide results showing that our notions of fuzzy simulation and bisimulation are more general and refined than the notions of simulation and bisimulation introduced by \'Ciri\'c et al. and the notions of approximate simulation and bisimulation introduced by Stanimirovi\'c et al.

We formulate and prove logical characterizations of crisp simulations and crisp directed simulations between fuzzy labeled transition systems with respect to fuzzy modal logics that use a general t-norm-based semantics. The considered logics are fragments of the fuzzy propositional dynamic logic with the Baaz projection operator. The logical characterizations concern preservation of positive existential (respectively, positive) modal formulas under crisp simulations (respectively, crisp directed simulations), as well as the Hennessy-Milner property of such simulations., Comment: This is a revised and extended version of a FUZZ-IEEE'2021 paper

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.

There are two kinds of bisimulation, namely crisp and fuzzy, between fuzzy structures such as fuzzy automata, fuzzy labeled transition systems, fuzzy Kripke models and fuzzy interpretations in description logics. Fuzzy bisimulations between fuzzy automata over a complete residuated lattice have been introduced by \'Ciri\'c et al. in 2012. Logical characterizations of fuzzy bisimulations between fuzzy Kripke models (respectively, fuzzy interpretations in description logics) over the residuated lattice [0,1] with the G\"odel t-norm have been provided by Fan in 2015 (respectively, Nguyen et al. in 2020). There was the lack of logical characterizations of fuzzy bisimulations between fuzzy graph-based structures over a general residuated lattice, as well as over the residuated lattice [0,1] with the {\L}ukasiewicz or product t-norm. In this article, we provide and prove logical characterizations of fuzzy bisimulations in fuzzy modal logics over residuated lattices. The considered logics are the fuzzy propositional dynamic logic and its fragments. Our logical characterizations concern invariance of formulas under fuzzy bisimulations and the Hennessy-Milner property of fuzzy bisimulations. They can be reformulated for other fuzzy structures such as fuzzy label transition systems and fuzzy interpretations in description logics.

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.

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.

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\"odel 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\"odel 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., Comment: 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 ExpTime (complexity-optimal) tableau decision procedure for checking satisfiability of a knowledge base in the description logic SHOQ, which extends the basic description logic ALC with transitive roles, hierarchies of roles, nominals and quantified number restrictions. The complexity is measured using unary representation for numbers. Our procedure is based on global caching and integer linear feasibility checking., Comment: arXiv admin note: substantial text overlap with arXiv:1205.5838

We study comparisons between interpretations in description logics with respect to "logical consequences" of the form of semi-positive concepts (like semi-positive concept assertions). Such comparisons are characterized by conditions similar to the ones of bisimulations. The simplest among the considered logics is a variant of PDL (propositional dynamic logic). The others extend that logic with inverse roles, nominals, quantified number restrictions, the universal role, and/or the concept constructor for expressing the local reflexivity of a role. The studied problems are: preservation of semi-positive concepts with respect to comparisons, the Hennessy-Milner property for comparisons, and minimization of interpretations that preserves semi-positive concepts., Comment: arXiv admin note: text overlap with arXiv:1104.1964

We give the first ExpTime (complexity-optimal) tableau decision procedure for checking satisfiability of a knowledge base in the description logic SHIQ when numbers are coded in unary. Our procedure is based on global state caching and integer linear feasibility checking.

We formulate query-subquery nets and use them to create the first framework for developing algorithms for evaluating queries to Horn knowledge bases with the properties that: the approach is goal-directed; each subquery is processed only once and each supplement tuple, if desired, is transferred only once; operations are done set-at-a-time; and any control strategy can be used. Our intention is to increase efficiency of query processing by eliminating redundant computation, increasing flexibility and reducing the number of accesses to the secondary storage. The framework forms a generic evaluation method called QSQN. To deal with function symbols, we use a term-depth bound for atoms and substitutions occurring in the computation and propose to use iterative deepening search which iteratively increases the term-depth bound. We prove soundness and completeness of our generic evaluation method and show that, when the term-depth bound is fixed, the method has PTIME data complexity. We also present how tail recursion elimination can be incorporated into our framework and propose two exemplary control strategies, one is to reduce the number of accesses to the secondary storage, while the other is depth-first search., Comment: 24 pages

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

We study bisimulations for useful description logics. The simplest among the considered logics is $\mathcal{ALC}_{reg}$ (a variant of PDL). The others extend that logic with inverse roles, nominals, quantified number restrictions, the universal role, and/or the concept constructor for expressing the local reflexivity of a role. They also allow role axioms. We give results about invariance of concepts, TBoxes and ABoxes, preservation of RBoxes and knowledge bases, and the Hennessy-Milner property w.r.t. bisimulations in the considered description logics. Using the invariance results we compare the expressiveness of the considered description logics w.r.t. concepts, TBoxes and ABoxes. Our results about separating the expressiveness of description logics are naturally extended to the case when instead of $\mathcal{ALC}_{reg}$ we have any sublogic of $\mathcal{ALC}_{reg}$ that extends $\mathcal{ALC}$. We also provide results on the largest auto-bisimulations and quotient interpretations w.r.t. such equivalence relations. Such results are useful for minimizing interpretations and concept learning in description logics. To deal with minimizing interpretations for the case when the considered logic allows quantified number restrictions and/or the constructor for the local reflexivity of a role, we introduce a new notion called QS-interpretation, which is needed for obtaining expected results. By adapting Hopcroft's automaton minimization algorithm and the Paige-Tarjan algorithm, we give efficient algorithms for computing the partition corresponding to the largest auto-bisimulation of a finite interpretation., Comment: 42 pages

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 reformulate Pratt's tableau decision procedure of checking satisfiability of a set of formulas in PDL. Our formulation is simpler and more direct for implementation. Extending the method we give the first EXPTIME (optimal) tableau decision procedure not based on transformation for checking consistency of an ABox w.r.t. a TBox in PDL (here, PDL is treated as a description logic). We also prove the new result that the data complexity of the instance checking problem in PDL is coNP-complete.