An improved algorithm for determinization of weighted and fuzzy automata

For a given weighted finite automaton over a strong bimonoid we construct its reduced Nerode automaton, which is crisp-deterministic and equivalent to the original weighted automaton with respect to the initial algebra semantics. We show that the reduced Nerode automaton is even smaller than the Nerode automaton, which was previously used in determinization related to this semantics. We determine necessary and sufficient conditions under which the reduced Nerode automaton is finite and provide an efficient algorithm which computes the reduced Nerode automaton whenever it is finite. In determinization of weighted finite automata over semirings and fuzzy finite automata over lattice-ordered monoids this algorithm gives smaller crisp-deterministic automata than any other known determinization algorithm.     

Intuitionistic fuzzy recognizers and intuitionistic fuzzy finite automata

Intuitionistic fuzzy recognizers and intuitionistic fuzzy finite automata are discussed. The notions of intuitionistic fuzzy recognizer, complete accessible intuitionistic fuzzy recognizer, intuitionistic fuzzy finite automata, deterministic intuitionistic fuzzy finite automata, and intuitionistic fuzzy language are introduced. It is shown that the languages recognized by intuitionistic fuzzy recognizer are regular, and the intuitionistic fuzzy languages recognized by the intuitionistic fuzzy finite automaton and the intuitionistic fuzzy languages recognized by deterministic intuitionistic fuzzy finite automaton are equivalent. This work is supported by National Science Foundation of China (Grant No.10571112), “TRAPOYT” of China and National 973 Foundation Research Program(Grant No.2002CB312200).     

The relationships among several types of fuzzy automata

We discuss the relationships among several types of fuzzy automata in which all fuzzy sets are defined by membership functions whose codomains are a lattice-ordered monoid L. These automata include nondeterministic L-valued finite automata with Λ-move, nondeterministic L-valued finite automata, deterministic L-valued finite automata, and L-valued finite-state automata. We consider all that come with fuzzy initial states and fuzzy final states or with crisp initial states or crisp final states. Some comparative results concerning the power of fuzzy automata used in the existing literature to recognize fuzzy languages are given systematically.     

Formal power series and regular operations on fuzzy languages

In this paper we study formal power series over a quantale with coefficients in the algebra of all languages over a given alphabet, and representation of fuzzy languages by these formal power series. This representation generalizes the well-known representation of fuzzy languages by their cut and kernel languages. We show that regular operations on fuzzy languages can be represented by regular operations on power series which are defined by means of operations on ordinary languages. We use power series in study of fuzzy languages which are recognized by fuzzy finite automata and deterministic finite automata, and we study closure properties of the set of polynomials and the set of polynomials with regular coefficients under regular operations on power series.     

GENERALIZED FUZZY RELATIONAL INEQUALITIES AND RELATED PROBLEMS

Various authors investigated fuzzy relational equalities constructed on the basic of the classical max-min extension principle (Czogala, E.. Drewniak. J. and Pedrycz. W. (1982) Fuzzy Sets and Systems, 7,89-101; Sanchez, E. (1976) Information andComrol, 30, 38-48). In this contribution, generalized fuzzy relational inequalities constructed by making use of compensatory operators or t-norms are studied (for the introduction of these concepts (Schwcizer and Sklar, A. (I960) Pacific J. Math., 10,313-334; (Clement, E.P.. Mesiar. R. and Pap, A. (1994) Preprint). Fuzzy relations considered here have a finite support. Solvability of generalized fuzzy relational inequalities is investigated.     

Multi-objective inventory models of deteriorating items with some constraints in a fuzzy environment

In this paper, multi-item inventory models of deteriorating items with stock-dependent demand are developed in a fuzzy environment. Here, the objectives of maximizing the profit and minimizing the wastage cost are fuzzy in nature. Total average cost, warehouse space, inventory costs, purchasing and selling prices are also assumed to be vague and imprecise. The impreciseness in the above objective and constraint goals have been expressed by fuzzy linear membership functions and that in inventory costs and prices by triangular fuzzy numbers (TFN). Models have been solved by the fuzzy non-linear programming (FNLP) method based on Zimmerman [Zimmermann, H.-J., Fuzzy linear programming with several objective functions. Fuzzy Sets and Systems, 1978, 1, 46-55] and Lee and Li [Lee, E. S. and Li, R. J., Fuzzy multiple objective programming and compromise programming with Pareto optima. Fuzzy Sets and Systems, 1993, 53, 275-288]. These are illustrated with numerical examples and results of one model are compared with those obtained by the fuzzy additive goal programming (FAGP) [Tiwari, R. N., Dharmar, S. and Rao, J. R., Fuzzy goal programming: an additive model. Fuzzy Sets and Systems, 1987, 24, 27-34] method.     

Non-commutative fuzzy Galois connections

 Fuzzy Galois connections were introduced by Bělohlávek in [4]. The structure considered there for the set of truth values is a complete residuated lattice, which places the discussion in a “commutative fuzzy world”. What we are doing in this paper is dropping down the commutativity, getting the corresponding notion of Galois connection and generalizing some results obtained by Bělohlávek in [4] and [7]. The lack of the commutative law in the structure of truth values makes it appropriate for dealing with a sentences conjunction where the order between the terms of the conjunction counts, gaining thus a temporal dimension for the statements. In this “non-commutative world”, we have not one, but two implications ([15]). As a consequence, a Galois connection will not be a pair, but a quadruple of functions, which is in fact two pairs of functions, each function being in a symmetric situation to his pair. Stating that these two pairs are compatible in some sense, we get the notion of strong L-Galois connection, a more operative and prolific notion, repairing the “damage” done by non-commutativity. Dedicated to Prof. Ján Jakubík on the occasion of his 80th birthday.     

The concept of duality for automata over a changing alphabet and generation of a free group by such automata

In the paper, we deal with the notion of an automaton over a changing alphabet, which generalizes the concept of a Mealy-type automaton. We modify the methods based on the idea of a dual automaton and its action used by B. Steinberg et al. (2011) and M. Vorobets and Ya. Vorobets (2007, 2010) [16], [17] and [18] and adapt them to automata over a changing alphabet. We show that this modification provides some naturally defined automaton representations of a free nonabelian group by a 2-state automaton over a changing alphabet.     

模糊有限自动机的最小化算法优化

现有的模糊自动机最小化算法没有涉及到对模糊自动机状态的隶属度迁移和变化的讨论,优化的模糊自动机最小化算法弥补了这类算法的不足之处。该算法将模糊有限自动机首先转化为单个初始状态的模糊自动机,然后再将转化后的模糊自动机化简为最小模糊自动机,算法在转化过程中单独讨论了模糊自动机状态隶属度的转化方式,使得算法更加严谨和简化。     

Decomposing a kind of weakly invertible finite automata with delay 2

Some properties of a finite automaton composed of two weakly invertible finite automata with delay 1 are given,where each of those two automata has the output set of each state with the same size.And for a weakly invertible finite automaton M with delay 2 satisfying the properties mentioned in this paper,two weakly invertible finite automata with delay 1 are constructed such that M is equivalent to a sub-finite-automaton of the composition of those two.So a method to decompose this a kind of weakly invertible finite automate with delay 2 is presented.     

Approximation of fuzzy context-free grammars

Fuzzy context-free max- grammar (or FCFG, for short), as a straightforward extension of context-free grammar, has been introduced to express uncertainty, imprecision, and vagueness in natural language fragments. Li recently proposed the approximation of fuzzy finite automata, which may effectively deal with the practical problems of fuzziness, impreciseness and vagueness. In this paper, we further develop the approximation of fuzzy context-free grammars. In particular, we show that a fuzzy context-free grammar under max- compositional inference can be approximated by some fuzzy context-free grammar under max-min compositional inference with any given accuracy. In addition, some related properties of fuzzy context-free grammars and fuzzy languages generated by them are studied. Finally, the sensitivity of fuzzy context-free grammars is also discussed.     

汉字模糊有穷自动机的研究

汉字的计算机输入是中文信息处理的关键问题之一,而汉字计算机输入的数学模型对汉字的计算机输入的研究有重要的意义。对汉字输入数学模型的分类进行了研究。研究了一般汉字有穷自动机,在此基础上把模糊有穷自动机的概念引入输入模型,并给出汉字模糊有穷自动机的概念。新的模型是以前给出的汉字自动机模型的推广,较之以前的数学模型,能刻画出汉字智能输入、词句输入,表达能力进一步增强,为汉字的智能处理提供了数学模型。     

Compact and fast algorithms for safe regular expression search

This article describes an improvement of the brute force determinization algorithm in the case of homogeneous nondeterministic finite automata (NFAs), as well as its application to pattern matching. Brute force determinization with limited memory may provide a partially determinized automaton, but its bounded complexity makes it a safe procedure contrary to the classical subset construction. Actually, our algorithm is inspired by both recent results of Champarnaud concerning the subset automaton of a homogeneous NFA and the algorithm recently designed by Navarro and Raffinot to implement the brute force determinization of the Glushkov NFA of a regular pattern. Our algorithm significantly improves Navarro–Raffinot's one since it has an average exponentially smaller memory requirement for a given level of determinization, which, considering a bounded memory, implies a quadratically smaller parsing time. This algorithm has been implemented in CCP software (http://www.univ-rouen.fr/LIFAR/aia/ccp.html). Tests have been carried out in the field of text processing and biology. Experimental results are reported.     

Determinization of weighted finite automata over strong bimonoids

We consider weighted finite automata over strong bimonoids, where these weight structures can be considered as semirings which might lack distributivity. Then, in general, the well-known run semantics, initial algebra semantics, and transition semantics of an automaton are different. We prove an algebraic characterization for the initial algebra semantics in terms of stable finitely generated submonoids. Moreover, for a given weighted finite automaton we construct the Nerode automaton and Myhill automaton, both being crisp-deterministic, which are equivalent to the original automaton with respect to the initial algebra semantics, respectively, the transition semantics. We prove necessary and sufficient conditions under which the Nerode automaton and the Myhill automaton are finite, and we provide efficient algorithms for their construction. Also, for a given weighted finite automaton, we show sufficient conditions under which a given weighted finite automaton can be determinized preserving its run semantics.     

Theory of general linear automata

Linear and affine automata are considered in their general form. The concept of dimensions of a finite automaton is introduced and finite automata of maximal dimensions are shown to be possible. The state reachability problem in monomial form is proved to be undecidable for two-dimensional affine automata. An analogue of Moore's theorem and theorems on homogenous and diagnostic words are also proved. An application of linear automata to mathematical economics is considered. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 10–21, January–February 2009.     

A tighter analysis of Piterman's Büchi determinization

Determinization and complementation are two fundamental problems in automata theory. Very recently, Piterman improved Safra's determinization and, presented a new construction which produces parity automata with a smaller size. We give a tighter analysis on that determinization construction and show that the number of states of the resulting deterministic automaton is bounded by 2n²(n!) instead of 2n!nn.     

Fault detection and isolation based on fuzzy automata

Fuzzy automata are proposed for fault diagnosis. The output of the monitored system is partitioned into linear segments which in turn are assigned to pattern classes (templates) with the use of membership functions. A sequence of templates is generated and becomes input to fuzzy automata which have transitions that correspond to the templates of the properly functioning system. If the automata reach their final states, i.e. the input sequence is accepted by the automata with a membership degree that exceeds a certain threshold, then normal operation is deduced, otherwise, a failure is diagnosed. Fault diagnosis of a DC motor and detection of abnormalities in the ECG signal are used as case studies.     

Derivatives of tree sets with applications to grammatical inference

Tree automata generalize the notion of a finite automaton working on strings to that of a finite automaton operating on trees. Most results for finite automata have been extended to tree automata. In this paper we introduce tree derivatives which extend the concept of Brzozowski's string derivatives. We use tree derivatives for minimizing and characterizing tree automata. Tree derivatives are used as a basis of inference of tree automata from finite samples of trees. Our method compares tree derivative sets and infers a tree automaton based on the amount of overlap between the derivative sets. Several of the limitations present in the tree inference techniques by Brayer and Fu and Edwards, Gonzalez, and Thomason are not imposed by our algorithm.     

Regular grammars with truth values in lattice-ordered monoid and their languages

In this study, we introduce the concept of lattice-valued regular grammars. Such grammars have become a necessary tool for the analysis of fuzzy finite automata. The relationship between lattice-valued finite automata (LA) and lattice-valued regular grammars (LRG) are discussed and we get the following results, for a given LRG, there exists an LA such that they accept the same languages, and vice versa. We also show the equivalence between deterministic lattice-valued regular grammars and deterministic lattice-valued finite automata.     

Bounded determinization of timed automata with silent transitions

Deterministic timed automata are strictly less expressive than their non-deterministic counterparts, which are again less expressive than those with silent transitions. As a consequence, timed automata are in general non-determinizable. This is unfortunate since deterministic automata play a major role in model-based testing, observability and implementability. However, by bounding the length of the traces in the automaton, effective determinization becomes possible. We propose a novel procedure for bounded determinization of timed automata. The procedure unfolds the automata to bounded trees, removes all silent transitions and determinizes via disjunction of guards. The proposed algorithms are optimized to the bounded setting and thus are more efficient and can handle a larger class of timed automata than the general algorithms. We show how to apply the approach in a fault-based test-case generation method, called model-based mutation testing, that was previously restricted to deterministic timed automata. The approach is implemented in a prototype tool and evaluated on several scientific examples and one industrial case study. To our best knowledge, this is the first implementation of this type of procedure for timed automata.