Computing with words via Turing machines: a formal approach

Computing with words (CW) as a methodology, means computing and reasoning by the use of words in place of numbers or symbols, which may conform more to humans' perception when describing real-world problems. In this paper, as a continuation of a previous paper, we aim to develop and deepen a formal aspect of CW. According to the previous paper, the basic point of departure is that CW treats certain formal modes of computation with strings of fuzzy subsets instead of symbols as their inputs. Specifically, 1) we elaborate on CW via Turing machine (TM) models, showing the time complexity is at least exponential if the inputs are strings of words; 2) a negative result of (6) not holding is verified which indicates that the extension principle for CW via TMs needs to be re-examined; 3) we discuss CW via context- free grammars and regular grammars and the extension principles for CW via these formal grammars are set up; 4) some equivalences between fuzzy pushdown automata (respectively, fuzzy finite-state automata) fuzzy context-free grammars (respectively, fuzzy regular grammars) are demonstrated in the sense that the inputs are instead strings of words; 5) some instances are described in detail. Summarily formal aspect of CW is more systematically established more deeply dealt with while some new problems also emerge.     

Retraction and Generalized Extension of Computing With Words

Fuzzy automata, whose input alphabet is a set of numbers or symbols, are a formal model of computing with values. Motivated by Zadeh's paradigm of computing with words rather than numbers, Ying proposed a kind of fuzzy automata, whose input alphabet consists of all fuzzy subsets of a set of symbols, as a formal model of computing with all words. In this paper, we introduce a somewhat general formal model of computing with (some special) words. The new features of the model are that the input alphabet only comprises some (not necessarily all) fuzzy subsets of a set of symbols and the fuzzy transition function can be specified arbitrarily. By employing the methodology of fuzzy control, we establish a retraction principle from computing with words to computing with values for handling crisp inputs and a generalized extension principle from computing with words to computing with all words for handling fuzzy inputs. These principles show that computing with values and computing with all words can be respectively implemented by computing with words. Some algebraic properties of retractions and generalized extensions are addressed as well.     

广义区间二型模糊集合的词计算

普通的模糊集合是点值为二维的一型模糊集合,二型模糊集合(Type-2 fuzzy sets, T2 FS)是点值为三维的模糊集合, T2 FS比相应的一型难以理解和计算. 为了让人们更好地理解T2 FS并推广其应用, 本文提出了广义区间二型模糊集合(Generalized interval type-2 fuzzy sets, GIT2 FS)的定义, 并将其分成三类:离散型、半离散型及连续型,分别给出相应的数学表达式与扩展原理公式,并得到了GIT2 FS在两种不同的模糊逻辑算子下的词计算.     

离散型和连续型改进Karnik-Mendel算法在高阶模糊系统降型中的关系研究

降型是广义二型模糊逻辑系统的核心模块。比较和分析了离散改进Karnik-Mendel（EKM）算法中求和运算和连续EKM(CEKM)算法中求积分运算,基于广义二型模糊集的α-平面表达理论,扩展EKM算法计算完成广义二型模糊逻辑系统质心降型。当计算广义二型模糊逻辑系统的质心降型集和质心解模糊化值时,用2个仿真实验说明了当适当增加广义二型模糊集主变量采样个数时,离散EKM算法的计算结果可以准确地逼近CEKM算法。     

A formal model of computing with words

Classical automata are formal models of computing with values. Fuzzy automata are generalizations of classical automata where the knowledge about the system's next state is vague or uncertain. It is worth noting that like classical automata, fuzzy automata can only process strings of input symbols. Therefore, such fuzzy automata are still (abstract) devices for computing with values, although a certain vagueness or uncertainty are involved in the process of computation. We introduce a new kind of fuzzy automata whose inputs are instead strings of fuzzy subsets of the input alphabet. These new fuzzy automata may serve as formal models of computing with words. We establish an extension principle from computing with values to computing with words. This principle indicates that computing with words can be implemented with computing with values with the price of a big amount of extra computations.     

关于二型模糊集合的一些基本问题

采用集合论的方法给出了单位模糊集合和二型模糊集合及其在一点的限制等定义,使得二型模糊集合更易于理解.通过定义嵌入单位模糊集合来描述一般二型模糊集合,并给出离散、半连通二型模糊集合的表达式.根据论域、主隶属度及隶属函数的特性将二型模糊集合分为四种类型:离散、半连通、连通及复合型,并根据连通的特点将连通二型模糊集合分为单连通及多连通两类.利用支集的闭包（Closure of support,CoS）划分法表述主隶属度及区间二型模糊集合.提出了CoS二、三次划分法分别来表述单、复连通二型模糊集合,并使每一个子区域的上下边界及次隶属函数在该子区域上的限制分别具有相同的解析表述式.最后,探讨了二型模糊集合在一点的限制、主隶属度、支集、嵌入单位模糊集合之间的关系.     

A Fuzzy Linguistic Methodology to Deal With Unbalanced Linguistic Term Sets

Many real problems dealing with qualitative aspects use linguistic approaches to assess such aspects. In most of these problems, a uniform and symmetrical distribution of the linguistic term sets for linguistic modeling is assumed. However, there exist problems whose assessments need to be represented by means of unbalanced linguistic term sets, i.e., using term sets that are not uniformly and symmetrically distributed. The use of linguistic variables implies processes of computing with words (CW). Different computational approaches can be found in the literature to accomplish those processes. The 2-tuple fuzzy linguistic representation introduces a computational model that allows the possibility of dealing with linguistic terms in a precise way whenever the linguistic term set is uniformly and symmetrically distributed. In this paper, we present a fuzzy linguistic methodology in order to deal with unbalanced linguistic term sets. To do so, we first develop a representation model for unbalanced linguistic information that uses the concept of linguistic hierarchy as representation basis and afterwards an unbalanced linguistic computational model that uses the 2-tuple fuzzy linguistic computational model to accomplish processes of CW with unbalanced term sets in a precise way and without loss of information.     

Aggregation Using the Linguistic Weighted Average and Interval Type-2 Fuzzy Sets

The focus of this paper is the linguistic weighted average (LWA), where the weights are always words modeled as interval type-2 fuzzy sets (IT2 FSs), and the attributes may also (but do not have to) be words modeled as IT2 FSs; consequently, the output of the LWA is an IT2 FS. The LWA can be viewed as a generalization of the fuzzy weighted average (FWA) where the type-1 fuzzy inputs are replaced by IT2 FSs. This paper presents the theory, algorithms, and an application of the LWA. It is shown that finding the LWA can be decomposed into finding two FWAs. Since the LWA can model more uncertainties, it should have wide applications in distributed and hierarchical decision-making.     

A comparative study of ranking methods, similarity measures and uncertainty measures for interval type-2 fuzzy sets

Ranking methods, similarity measures and uncertainty measures are very important concepts for interval type-2 fuzzy sets (IT2 FSs). So far, there is only one ranking method for such sets, whereas there are many similarity and uncertainty measures. A new ranking method and a new similarity measure for IT2 FSs are proposed in this paper. All these ranking methods, similarity measures and uncertainty measures are compared based on real survey data and then the most suitable ranking method, similarity measure and uncertainty measure that can be used in the computing with words paradigm are suggested. The results are useful in understanding the uncertainties associated with linguistic terms and hence how to use them effectively in survey design and linguistic information processing.     

Uncertainty measures for interval type-2 fuzzy sets

Fuzziness (entropy) is a commonly used measure of uncertainty for type-1 fuzzy sets. For interval type-2 fuzzy sets (IT2 FSs), centroid, cardinality, fuzziness, variance and skewness are all measures of uncertainties. The centroid of an IT2 FS has been defined by Karnik and Mendel. In this paper, the other four concepts are defined. All definitions use a Representation Theorem for IT2 FSs. Formulas for computing the cardinality, fuzziness, variance and skewness of an IT2 FS are derived. These definitions should be useful in IT2 fuzzy logic systems design using the principles of uncertainty, and in measuring the similarity between two IT2 FSs.     

Interval type-2 fuzzy membership function generation methods for pattern recognition

Type-2 fuzzy sets (T2 FSs) have been shown to manage uncertainty more effectively than T1 fuzzy sets (T1 FSs) in several areas of engineering [4], [6], [7], [8], [9], [10], [11], [12], [15], [16], [17], [18], [21], [22], [23], [24], [25], [26], [27] and [30]. However, computing with T2 FSs can require undesirably large amount of computations since it involves numerous embedded T2 FSs. To reduce the complexity, interval type-2 fuzzy sets (IT2 FSs) can be used, since the secondary memberships are all equal to one [21]. In this paper, three novel interval type-2 fuzzy membership function (IT2 FMF) generation methods are proposed. The methods are based on heuristics, histograms, and interval type-2 fuzzy C-means. The performance of the methods is evaluated by applying them to back-propagation neural networks (BPNNs). Experimental results for several data sets are given to show the effectiveness of the proposed membership assignments.     

计算科学的新领域：DNA计算（Ⅱ）

DNA计算是应用分子生物技术进行计算的新方法。从理论上研究DNA计算方法，有利于推动理论计算科学的发展。本系列文章应用形式语言及自动机理论技术，系统地探讨了DNA分子的可计算性及其计算能力。本文主要介绍DNA分子粘接计算模型的文法结构和计算方法，探讨了不同粘接计算模型的计算能力，并证明了DNA有穷自动机与正规文法的等价性。     

Uncertainty measures for general Type-2 fuzzy sets

Five uncertainty measures have previously been defined for interval Type-2 fuzzy sets (IT2 FSs), namely centroid, cardinality, fuzziness, variance and skewness. Based on a recently developed α-plane representation for a general T2 FS, this paper generalizes these definitions to such T2 FSs and, more importantly, derives a unified strategy for computing all different uncertainty measures with low complexity. The uncertainty measures of T2 FSs with different shaped Footprints of Uncertainty and different kinds of secondary membership functions (MFs) are computed and are given as examples. Observations and summaries are made for these examples, and a Summary Interval Uncertainty Measure for a general T2 FS is proposed to simplify the interpretations. Comparative studies of uncertainty measures for Quasi-Type-2 (QT2), IT2 and T2 FSs are also performed to examine the feasibility of approximating T2 FSs using QT2 or even IT2 FSs.     

Industrial applications of type-2 fuzzy sets and systems: A concise review

Data, as being the vital input of system modelling, contain dissimilar level of imprecision that necessitates different modelling approaches for proper analysis of the systems. Numbers, words and perceptions are the forms of data that has varying levels of imprecision. Existing approaches in the literature indicate that, computation of different data forms are closely linked with the level of imprecision, which the data already have. Traditional mathematical modelling techniques have been used to compute the numbers that have the least imprecision. Type-1 fuzzy sets have been used for words and type-2 fuzzy sets have been employed for perceptions where the level of imprecision is relatively high. However, in many cases it has not been easy to decide whether a solution requires a traditional approach, i.e., type-1 fuzzy approach or type-2 fuzzy approach. It has been a difficult matter to decide what types of problems really require modelling and solution either with type-1 or type-2 fuzzy approach. It is certain that, without properly distinguishing differences between the two approaches, application of type-1 and type-2 fuzzy sets and systems would probably fail to develop robust and reliable solutions for the problems of industry. In this respect, a review of the industrial applications of type-2 fuzzy sets, which are relatively novel to model imprecision has been considered in this work. The fundamental focus of the work has been based on the basic reasons of the need for type-2 fuzzy sets for the existing studies. With this purpose in mind, type-2 fuzzy sets articles have been selected from the literature using the online databases of ISI-Web of Science, ScienceDirect, SpringerLink, Informaworld, Engineering Village, Emerald and IEEE Xplore. Both the terms “type-2 fuzzy” and “application” have been searched as the main keywords in the topics of the studies to retrieve the relevant works. The analysis on the industrial applications of type-2 fuzzy sets/systems (FSs) in different topics allowed us to summarize the existing research areas and therefore it is expected be useful to prioritize future research topics. This review shows that there are still many opportunities for application of type-2 FSs for several different problem domains. Shortcomings of type-1 FSs can also be considered as an opportunity for the application of type-2 FSs in order to provide a better solution approach for industrial problems.     

A perceptual computing-based method to prioritize failure modes in failure mode and effect analysis and its application to edible bird nest farming

A failure mode and effect analysis (FMEA) procedure that incorporates a novel Perceptual Computing (Per-C)–based Risk Priority Number (RPN) model is proposed in this paper. The proposed model considers linguistic uncertainties and vagueness of words, because it is more natural to use words, instead of numerals, for an FMEA user to express his/her knowledge when he/she provides an assessment. Therefore, it is important to consider the inherited uncertainties in words used by humans for assessment as an additional risk factor in the entire FMEA reasoning process. As such, we propose to use Per-C to analyze the uncertainties in words provided by different FMEA users. There are three potential sources of risks. Firstly, the risk factors of Severity (S), Occurrence (O), and Detection (D) are graded using words by each FMEA user, and indicated as interval type-2 fuzzy sets (IT2FSs). Secondly, the relative importance of S, O, and D are reflected by the weights given by each FMEA user in words, which are indicated as IT2FSs. Thirdly, the expertise level of each FMEA user is reflected by words, which are expressed as IT2FSs too. The proposed Per-C-RPN model allows these three sources of risks from each FMEA user to be considered and combined in terms of IT2FSs. A case study related to edible bird nest farming in Borneo Island is reported. The results indicate the effectiveness of the proposed model. In summary, this paper contributes to a new Per-C-RPN model that utilizes imprecise assessment grades pertaining to group decision making in FMEA.     

Fuzzy Interval TSK Type‐2 Modeling with Parameterized Conjunctors

In this study, a novel approach is described to the design of an interval type‐2 fuzzy neural system (IT2 FNS). It differs from the classical IT2 FNS in its use of parameterized conjunctors. In the optimization of the IT2 FNS, the membership functions are kept fixed and only the parameters of the conjunctors and the parameters in the consequent are tuned. In this study, the gradient based learning algorithm is used. The approach is tested for the modeling of a benchmark nonlinear function and for the wheel slip control of a quarter car model (QCM). In the stated applications, in the absence of any expert knowledge, some knowledge about the system is gained by the use of the interval type‐2 fuzzy c‐means (IT2 FCM) clustering algorithm. Nevertheless, this requires the number of classes to be known beforehand. To alleviate this problem, some validity indices that have been suggested in the literature and a novel validity index that carries less computational burden are considered to determine the number of classes and the number of fuzzy rules. Simulation studies are presented and compared with the results from the literature.     

Conceptual design evaluation using interval type-2 fuzzy information axiom

Concept selection is the most critical part of the design process as it determines the direction of subsequent design stages. In addition, it is a difficult task because available information for decision-making at this stage is imprecise and subjective. This necessitates the need for fuzzy decision models for selecting the best conceptual design among a set of alternatives. Although ordinary fuzzy sets cover uncertainties of linguistic words to some extent, it is recommended to use interval type-2 fuzzy sets (IT2FS) to capture potential uncertainties of words. This paper presents a new concept selection methodology that extends the fuzzy information axiom (FIA) approach to incorporate IT2FSs. The proposed methodology is called interval-type-2 fuzzy information axiom (IT2-FIA). IT2-FIA method is also enriched by using ordered weighted geometric aggregation operator to include the decision maker's attitude during the aggregation process. A case study is given to demonstrate the potential of the methodology.     

Data-driven modeling and optimization of thermal comfort and energy consumption using type-2 fuzzy method

In the research domain of intelligent buildings and smart home, modeling and optimization of the thermal comfort and energy consumption are important issues. This paper presents a type-2 fuzzy method based data-driven strategy for the modeling and optimization of thermal comfort words and energy consumption. First, we propose a methodology to convert the interval survey data on thermal comfort words to the interval type-2 fuzzy sets (IT2 FSs) which can reflect the inter-personal and intra-personal uncertainties contained in the intervals. This data-driven strategy includes three steps: survey data collection and pre-processing, ambiguity-preserved conversion of the survey intervals to their representative type-1 fuzzy sets (T1 FSs), IT2 FS modeling. Then, using the IT2 FS models of thermal comfort words as antecedent parts, an evolving type-2 fuzzy model is constructed to reflect the online observed energy consumption data. Finally, a multiobjective optimization model is presented to recommend a reasonable temperature range that can give comfortable feeling while reducing energy consumption. The proposed method can be used to realize comfortable but energy-saving environment in smart home or intelligent buildings.