Fuzzy discrete structures

Publication date 28 March 2001

Published in Studies in Fuzziness and Soft Computing (Search for Journal in Brave)

fuzzy automata fuzzy decision trees fuzzy grammars fuzzy graphs fuzzy languages fuzzy logic fuzzy machines fuzzy networks fuzzy path problems fuzzy switching functions

Mathematics Subject Classification ID

Fuzzy logic; logic of vagueness (03B52) Semigroups in automata theory, linguistics, etc. (20M35) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70) Graph theory (including graph drawing) in computer science (68R10)

Review text

The book is devoted to the fuzzification of discrete structures. It covers fuzzy logic and fuzzy switching functions, fuzzy decision trees, fuzzy networks, fuzzy graphs and fuzzy path problems, fuzzy machines and fuzzy automata, as well as fuzzy languages and fuzzy grammars. Chapter 1 is introductory. The necessary notions and statements for the next presentation are given -- fuzzy sets, fuzzy relations, fuzzy functions, fuzzy semigroups. The attention is concentrated on fuzzy logic for the purpose of fuzzy switching functions (completely and incompletely specified), of their decomposition and minimization. Fuzzy logical inequalities are included also. In Chapter 2 fuzzy decision trees and a branch-bound-backtrack algorithm are presented. The algorithm has time complexity \(O(\log n)\) and gives the optimal solution; \(n\) is the number of the decision classes. In the Appendix this algorithm is described in C++. Fuzzy networks are subject of Chapter 3. Network flow problem with various capacities is investigated and corresponding algorithms are given. Fuzzy Petri nets are introduced for rule based decision making. The shortest path problem as the most basic network problem, is presented in Chapter 4. A fuzzy shortest path length can be found, but it may not correspond to an actual path in the network. This problem is circumvented with models based on fuzzy shortest paths and multiple objective functions. Algorithms for the models are given. Submodular functions are used to analyze these models. Various kinds of machines are considered in Chapters 5 and 6 -- Mealy, Moore, acceptors, etc. Chapter 5 deals with fuzzy machines, fuzzy languages and fuzzy grammars. In order to develop the theory of max-product machines, the max-product algebra is introduced and investigated. By its use the equivalence and minimization problems are studied for max-product machines. Then maximin algebra is devoted as a useful and necessary tool for dealing with maximin machines. By the use of maximin algebra the reduction and minimization problems are presented. The max-product, maximin and linear algebra are almost completely unrelated. Most of the results for fuzzy machines are motivated by the theory of stochastic, deterministic and nondeterministic machines. Many of the results for the maximin machines are strengthened for the particular cases of deterministic and nondeterministic machines. Deterministic acceptors of regular fuzzy languages are presented. An algorithm is given for constructing a deterministic finite automaton which classifies the strings of a language with a regular fuzzy grammar. The algebraic properties of fuzzy regular languages, adjunctive languages and dense languages are also studied. The last Chapter 6 is an algebraic investigation of fuzzy automata. Semigroups of fuzzy finite state machines, homomorphisms, admissible relations, submachines, decomposition and partition problems, fuzzy recognizers and fuzzy regular languages are extensively studied. The exposition is lucid, propositions and statements are provided with complete proofs, there are many suitable examples, completing the concepts and the exposition.

Recommendations

Cited in

(38)

This page was built for publication: Fuzzy discrete structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5928253)