The Experts below are selected from a list of 1107 Experts worldwide ranked by ideXlab platform
Daowen Qiu - One of the best experts on this subject based on the ideXlab platform.
-
automata theory based on complete Residuated Lattice valued logic turing machines
Fuzzy Sets and Systems, 2012Co-Authors: Daowen Qiu, Hongyan XingAbstract:Automata theory based on complete Residuated Lattice-valued logic, called L-valued finite automata (L-VFAs), has been established by the second author in 2001. In view of the importance of Turing machines, in this paper, we establish a theory of Turing machines based on complete Residuated Lattice-valued logic, which is a continuation of L-VFAs. First, we give the definition of L-valued nondeterministic Turing machines (L-NTMs), and observe that the multitape L-NTMs have the same language-recognizing power as the single-tape L-NTMs. We give some related properties of L-valued Turing machines, and discuss computing with fuzzy letters via L-valued Turing machines. Second, we introduce the concepts of L-valued recursively enumerable languages and L-valued recursive languages, and obtain some equivalent relations. Some results concerning the characterization of n-recursively enumerable sets are given, and the super-computing power of L-valued Turing machines is investigated. We also prove that L-valued deterministic Turing machines and L-NTMs are not equivalent in the sense of recognizing or deciding languages. Finally, we show that there is no universal L-valued Turing machine. However, a universal L-valued Turing machine exists if the membership degrees of L-valued sets are restricted to a finite complete Residuated Lattice with universal bounds 0 and 1.
-
automata theory based on complete Residuated Lattice valued logic reduction and minimization
Fuzzy Sets and Systems, 2010Co-Authors: Daowen QiuAbstract:Automata theory based on complete Residuated Lattice-valued logic, called L-valued finite automata (L-VFAs), has been established by Qiu recently. In this paper, we define a kind of Mealy type of L-VFAs (MLFAs), a generalization of L-VFAs. Two kinds of statewise equivalence relations are introduced, and a minimal form is defined. We study the existence of the minimal form of an MLFA. Then, we show that any two states can be distinguished by some word with finite length. Also, a minimization algorithm of the MLFAs is presented. In addition, we obtain a minimization algorithm for L-VFAs as well. Finally, we define L-valued languages (L-VLs) and L-valued regular languages (L-VRLs) recognized by L-VFAs, and provide some properties of L-VRLs.
-
automata theory based on complete Residuated Lattice valued logic a categorical approach
Fuzzy Sets and Systems, 2009Co-Authors: Hongyan Xing, Daowen QiuAbstract:Automata theory based on complete Residuated Lattice-valued logic, called L-valued automata (L-VAs), has been primarily established by Qiu in 2001 and 2002. In this paper, we consider the L-VAs that have L-valued initial and final states. We study the categorical issue of L-VAs. The main technical contributions include: (1) We investigate the relationship between the category of L-VAs and the category of non-deterministic automata (NDAs); also, we study the relationship between the category of generalized L-VAs and the category of NDAs. (2) We prove the existence of isomorphisms between the category of L-VAs and the subcategory of generalized L-VAs and between the category of L-VAs and the category of sets of NDAs. (3) Finally, we further investigate some specific relationships between the output L-valued subsets of generalized L-VAs and the output L-valued subsets of NDAs.
-
pumping lemma in context free grammar theory based on complete Residuated Lattice valued logic
Fuzzy Sets and Systems, 2009Co-Authors: Hongyan Xing, Daowen QiuAbstract:Residuated Lattices are important algebras and have close links with various important algebras. Automata theory based on complete Residuated Lattice-valued logic, called L-valued automata, has been established by the second author in 2001 and 2002. As a continuation of automata theory based on complete Residuated Lattice-valued logic, in this paper, we mainly deal with the problem concerning pumping lemma in L-valued context-free languages (L-CFLs). As a generalization of the notion in the theory of formal grammars, the definition of L-valued context-free grammars (L-CFGs) is introduced. We also discuss a special case of L-CFGs, L-right (or left)-linear grammars, and show the equivalence between L-linear grammars and L-regular grammars. This result shows that we generalize the pumping lemma in L-valued regular languages (L-RLs) more recently established by the second author.
-
automata theory based on complete Residuated Lattice valued logic pushdown automata
Fuzzy Sets and Systems, 2009Co-Authors: Hongyan Xing, Daowen Qiu, Fuchun LiuAbstract:Automata theory based on complete Residuated Lattice-valued logic, called L-valued automata, has been proposed by Qiu [Automata theory based on complete Residuated Latticed-valued logic, Sci. China (Ser. F) 44 (6) (2001) 419-429; Automata theory based on complete Residuated Latticed-valued logic (II), Sci. China (Ser. F) 45 (6) (2002) 442-452]. In this paper, we discuss some properties of L-valued context-free grammars, languages, and pushdown automata. We show that, for such grammars, Chomsky and Greibach Normal Forms can be equivalently constructed, and we also prove that the languages accepted by final states and by empty stack in L-valued pushdown automata are equivalent. In particular, we prove the equivalence between L-valued context-free grammars and L-valued pushdown automata.
Hongyan Xing - One of the best experts on this subject based on the ideXlab platform.
-
automata theory based on complete Residuated Lattice valued logic turing machines
Fuzzy Sets and Systems, 2012Co-Authors: Daowen Qiu, Hongyan XingAbstract:Automata theory based on complete Residuated Lattice-valued logic, called L-valued finite automata (L-VFAs), has been established by the second author in 2001. In view of the importance of Turing machines, in this paper, we establish a theory of Turing machines based on complete Residuated Lattice-valued logic, which is a continuation of L-VFAs. First, we give the definition of L-valued nondeterministic Turing machines (L-NTMs), and observe that the multitape L-NTMs have the same language-recognizing power as the single-tape L-NTMs. We give some related properties of L-valued Turing machines, and discuss computing with fuzzy letters via L-valued Turing machines. Second, we introduce the concepts of L-valued recursively enumerable languages and L-valued recursive languages, and obtain some equivalent relations. Some results concerning the characterization of n-recursively enumerable sets are given, and the super-computing power of L-valued Turing machines is investigated. We also prove that L-valued deterministic Turing machines and L-NTMs are not equivalent in the sense of recognizing or deciding languages. Finally, we show that there is no universal L-valued Turing machine. However, a universal L-valued Turing machine exists if the membership degrees of L-valued sets are restricted to a finite complete Residuated Lattice with universal bounds 0 and 1.
-
automata theory based on complete Residuated Lattice valued logic a categorical approach
Fuzzy Sets and Systems, 2009Co-Authors: Hongyan Xing, Daowen QiuAbstract:Automata theory based on complete Residuated Lattice-valued logic, called L-valued automata (L-VAs), has been primarily established by Qiu in 2001 and 2002. In this paper, we consider the L-VAs that have L-valued initial and final states. We study the categorical issue of L-VAs. The main technical contributions include: (1) We investigate the relationship between the category of L-VAs and the category of non-deterministic automata (NDAs); also, we study the relationship between the category of generalized L-VAs and the category of NDAs. (2) We prove the existence of isomorphisms between the category of L-VAs and the subcategory of generalized L-VAs and between the category of L-VAs and the category of sets of NDAs. (3) Finally, we further investigate some specific relationships between the output L-valued subsets of generalized L-VAs and the output L-valued subsets of NDAs.
-
pumping lemma in context free grammar theory based on complete Residuated Lattice valued logic
Fuzzy Sets and Systems, 2009Co-Authors: Hongyan Xing, Daowen QiuAbstract:Residuated Lattices are important algebras and have close links with various important algebras. Automata theory based on complete Residuated Lattice-valued logic, called L-valued automata, has been established by the second author in 2001 and 2002. As a continuation of automata theory based on complete Residuated Lattice-valued logic, in this paper, we mainly deal with the problem concerning pumping lemma in L-valued context-free languages (L-CFLs). As a generalization of the notion in the theory of formal grammars, the definition of L-valued context-free grammars (L-CFGs) is introduced. We also discuss a special case of L-CFGs, L-right (or left)-linear grammars, and show the equivalence between L-linear grammars and L-regular grammars. This result shows that we generalize the pumping lemma in L-valued regular languages (L-RLs) more recently established by the second author.
-
automata theory based on complete Residuated Lattice valued logic pushdown automata
Fuzzy Sets and Systems, 2009Co-Authors: Hongyan Xing, Daowen Qiu, Fuchun LiuAbstract:Automata theory based on complete Residuated Lattice-valued logic, called L-valued automata, has been proposed by Qiu [Automata theory based on complete Residuated Latticed-valued logic, Sci. China (Ser. F) 44 (6) (2001) 419-429; Automata theory based on complete Residuated Latticed-valued logic (II), Sci. China (Ser. F) 45 (6) (2002) 442-452]. In this paper, we discuss some properties of L-valued context-free grammars, languages, and pushdown automata. We show that, for such grammars, Chomsky and Greibach Normal Forms can be equivalently constructed, and we also prove that the languages accepted by final states and by empty stack in L-valued pushdown automata are equivalent. In particular, we prove the equivalence between L-valued context-free grammars and L-valued pushdown automata.
-
equivalence in automata theory based on complete Residuated Lattice valued logic
Fuzzy Sets and Systems, 2007Co-Authors: Hongyan Xing, Daowen Qiu, Fuchun Liu, Zhujun FanAbstract:Automata theory based on complete Residuated Lattice-valued logic, called L-valued finite automata (abbr. L-VFAs), was introduced by the second author in 2001. In this paper we deal with the problems of equivalence between L-valued sequential machines (abbr. L-VSMs) and L-VFAs. We define L-VSMs, and particularly present a method for deciding the equivalence between L-VSMs as well. An algorithm procedure for deciding the equivalence between L-VSMs is constructed. We analyze the complexity and efficiency of the algorithm procedure and obtain the relative results to L-VFAs. Moreover, the definitions of L-valued languages (abbr. L-VLs), and L-valued regular languages (abbr. L-VRLs) recognized by L-VFAs are given, and some related properties are also discussed. We show an equivalent relation between L-VRLs and conventional regular languages. By using L-valued pumping lemma, we get a necessary and sufficient condition for an L-VL to be nonconstant.
Fuchun Liu - One of the best experts on this subject based on the ideXlab platform.
-
automata theory based on complete Residuated Lattice valued logic pushdown automata
Fuzzy Sets and Systems, 2009Co-Authors: Hongyan Xing, Daowen Qiu, Fuchun LiuAbstract:Automata theory based on complete Residuated Lattice-valued logic, called L-valued automata, has been proposed by Qiu [Automata theory based on complete Residuated Latticed-valued logic, Sci. China (Ser. F) 44 (6) (2001) 419-429; Automata theory based on complete Residuated Latticed-valued logic (II), Sci. China (Ser. F) 45 (6) (2002) 442-452]. In this paper, we discuss some properties of L-valued context-free grammars, languages, and pushdown automata. We show that, for such grammars, Chomsky and Greibach Normal Forms can be equivalently constructed, and we also prove that the languages accepted by final states and by empty stack in L-valued pushdown automata are equivalent. In particular, we prove the equivalence between L-valued context-free grammars and L-valued pushdown automata.
-
equivalence in automata theory based on complete Residuated Lattice valued logic
Fuzzy Sets and Systems, 2007Co-Authors: Hongyan Xing, Daowen Qiu, Fuchun Liu, Zhujun FanAbstract:Automata theory based on complete Residuated Lattice-valued logic, called L-valued finite automata (abbr. L-VFAs), was introduced by the second author in 2001. In this paper we deal with the problems of equivalence between L-valued sequential machines (abbr. L-VSMs) and L-VFAs. We define L-VSMs, and particularly present a method for deciding the equivalence between L-VSMs as well. An algorithm procedure for deciding the equivalence between L-VSMs is constructed. We analyze the complexity and efficiency of the algorithm procedure and obtain the relative results to L-VFAs. Moreover, the definitions of L-valued languages (abbr. L-VLs), and L-valued regular languages (abbr. L-VRLs) recognized by L-VFAs are given, and some related properties are also discussed. We show an equivalent relation between L-VRLs and conventional regular languages. By using L-valued pumping lemma, we get a necessary and sufficient condition for an L-VL to be nonconstant.
Mingsheng Ying - One of the best experts on this subject based on the ideXlab platform.
-
fuzzifying topology based on complete Residuated Lattice valued logic i
Fuzzy Sets and Systems, 1993Co-Authors: Mingsheng YingAbstract:Abstract We greatly extend fuzzifying topology by introducing a unary fuzzy predicate interpreted as the property to be fuzzifying topological spaces on the class of all so-called fuzzifying pretopological spaces and by adopting the semantic method of complete Residuated Lattice-valued logic.
Maryam Ghorani - One of the best experts on this subject based on the ideXlab platform.
-
tree automata based on complete Residuated Lattice valued logic reduction algorithm and decision problems
Iranian Journal of Fuzzy Systems, 2018Co-Authors: Maryam GhoraniAbstract:In this paper, at first we define the concepts of response function and accessible states of a complete Residuated Lattice-valued (for simplicity we write $mathcal{L}$-valued) tree automaton with a threshold $c.$ Then, related to these concepts, we prove some lemmas and theorems that are applied in considering some decision problems such as finiteness-value and emptiness-value of recognizable tree languages. Moreover, we propose a reduction algorithm for $mathcal{L}$-valued tree automata with a threshold $c.$ The goal of reducing an $ mathcal{L}$-valued tree automaton is to obtain an $mathcal{L}$-valued tree automaton with reduced number of states%that all of its states are accessible all of which are accessible, in addition it recognizes the same language as the first one given. We compare our algorithm with some other algorithms in the literature. Finally, utilizing the obtained results, we consider some fundamental decision problems for $mathcal{L}$-valued tree automata including the membership-value, the emptiness-value, the finiteness-value, the intersection-value and the equivalence-value problems.
-
State hyperstructures of tree automata based on Lattice-valued logic
'EDP Sciences', 2018Co-Authors: Maryam GhoraniAbstract:In this paper, an association is organized between the theory of tree automata on one hand and the hyperstructures on the other hand, over complete Residuated Lattices. To this end, the concept of order of the states of a complete Residuated Lattice-valued tree automaton (simply L-valued tree automaton) is introduced along with several equivalence relations in the set of the states of an L-valued tree automaton. We obtain two main results from this study: one of the relations can lead to the creation of Kleene’s theorem for L-valued tree automata, and the other one leads to the creation of a minimal v-valued tree automaton that accepts the same language as the given one
-
algebraic properties of complete Residuated Lattice valued tree automata
Soft Computing, 2012Co-Authors: Maryam Ghorani, M M Zahedi, Reza AmeriAbstract:This paper investigates tree automata based on complete Residuated Lattice valued (referred to as L-valued) logic. First, we define the notions of L-valued set of pure subsystems and L-valued set of strong pure subsystems, as well as, their relation is considered. Also, L-valued n-tuple operator consist of n successors is defined, some of its properties are examined and its relation with pure subsystem is analyzed. Furthermore, we investigate some concepts such as L-valued set of (strong) homomorphisms, L-valued set of (strong) isomorphisms, and L-valued set of admissible relations. Moreover, we discuss bifuzzy topological characterization of L-valued tree automata. Finally, the relations of homomorphisms between the L-valued tree automata to continuous mappings and open mappings is examined.
-
characterizations of complete Residuated Lattice valued finite tree automata
Fuzzy Sets and Systems, 2012Co-Authors: Maryam Ghorani, M M ZahediAbstract:This paper deals with the concept of complete Residuated Lattice-valued (referred to as L-valued) finite tree automata. In this regard, we first define an L-valued regular tree language, and then we prove a necessary and sufficient condition for the regularity of an L-valued tree language. Furthermore, we generalize the pumping lemma for L-valued finite tree automata (L-FTA). Afterwards, the behavior of L-FTA is addressed and some theorems are provided. Moreover, the existence of the minimal form of an L-FTA is considered. Finally, a minimization algorithm of the L-FTA is presented and its time complexity is analyzed.
