The Experts below are selected from a list of 21495 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.
Zhujun Fan - One of the best experts on this subject based on the ideXlab platform.
-
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.
Venkatesh Rajagopalan - One of the best experts on this subject based on the ideXlab platform.
-
symbolic time series analysis for anomaly detection a comparative evaluation
Signal Processing, 2005Co-Authors: Shin C Chin, Asok Ray, Venkatesh RajagopalanAbstract:Recent literature has reported a novel method for anomaly detection in complex dynamical systems, which relies on symbolic time series analysis and is built upon the principles of Automata Theory and pattern recognition. This paper compares the performance of this symbolic-dynamics-based method with that of other existing pattern recognition techniques from the perspectives of early detection of small anomalies. Time series data of observed process variables on the fast time-scale of dynamical systems are analyzed at slow time-scale epochs of (possible) anomalies. The results are derived from experiments on a nonlinear electronic system with a slowly varying dissipation parameter.
