Fuzzy Automata and Languages: Theory and Applications

by Mordeson; John N.

• ISBN13: 9781584882251
• ISBN10: 1584882255
• eBook ISBN(s): 9781040219980
• Format: Hardcover
• Copyright: 2002-03-19
• Publisher: Chapman & Hall/
• More Book Details

Summary

The huge number and broad range of the existing and potential applications of fuzzy logic have precipitated a veritable avalanche of books published on the subject. Most, however, focus on particular areas of application. Many do no more than scratch the surface of the theory that holds the power and promise of fuzzy logic.Fuzzy Automata and Languages: Theory and Applications offers the first in-depth treatment of the theory and mathematics of fuzzy automata and fuzzy languages. After introducing background material, the authors study max-min machines and max-product machines, developing their respective algebras and exploring properties such as equivalences, homomorphisms, irreducibility, and minimality. The focus then turns to fuzzy context-free grammars and languages, with special attention to trees, fuzzy dendrolanguage generating systems, and normal forms. A treatment of algebraic fuzzy automata theory follows, along with additional results on fuzzy languages, minimization of fuzzy automata, and recognition of fuzzy languages. Although the book is theoretical in nature, the authors also discuss applications in a variety of fields, including databases, medicine, learning systems, and pattern recognition.Much of the information on fuzzy languages is new and never before presented in book form. Fuzzy Automata and Languages incorporates virtually all of the important material published thus far. It stands alone as a complete reference on the subject and belongs on the shelves of anyone interested in fuzzy mathematics or its applications.

Author Biography

John N. Mordeson is a Professor of Mathematies and Davender S. Malik is a Professor of Mathematies and Computer Science at Creighton University, Omaha, Nebraska

Table of Contents

Preface	v
Authors	ix
List of Symbols	xvii
Introduction	1	(44)
Sets	1	(1)
Relations	2	(4)
Functions	6	(2)
Fuzzy Subsets	8	(1)
Semigroups	9	(4)
Finite-State Machines	13	(2)
Finite-State Automata	15	(5)
Languages and Grammars	20	(4)
Nondeterministic Finite-State Automata	24	(6)
Relationships Between Languages and Automata	30	(6)
Pushdown Automata	36	(6)
Exercises	42	(3)
Max-Min Automata	45	(46)
Max-Min Automata	45	(1)
General Formulation of Automata	45	(1)
Classes of Automata	46	(2)
Behavior of Max-Min Automata	48	(3)
Equivalences and Homomorphisms of Max-Min Automata	51	(4)
Reduction of Max-Min Automata	55	(1)
Definite Max-Min Automata	56	(2)
Reduction of Max-Min Machines	58	(9)
Equivalences	67	(8)
Irreducibility and Minimality	75	(11)
Nondeterministic and Deterministic Case	86	(2)
Exercises	88	(3)
Fuzzy Machines, Languages, and Grammars	91	(36)
Max-Product Machines	91	(4)
Equivalences	95	(3)
Irreducibility and Minimality	98	(4)
Max-Product Grammars and Languages	102	(6)
Weak Regular Max-Product Grammars	108	(8)
Weak Regular Max-Product Languages	116	(4)
Properties of £	120	(5)
Exercises	125	(2)
Fuzzy Languages and Grammars	127	(46)
Fuzzy Languages	127	(3)
Types of Grammars	130	(1)
Fuzzy Context-Free Grammars	131	(6)
Context-Free Max-Product Grammars	137	(4)
Context-Free Fuzzy Languages	141	(5)
On the Description of the Fuzzy Meaning of Context-Free Languages	146	(1)
Trees and Pseudoterms	147	(1)
Fuzzy Dendrolanguage Generating Systems	148	(2)
Normal Form of F-CFDS	150	(4)
Sets of Derivation Trees of Fuzzy Context-Free Grammars	154	(4)
Fuzzy Tree Automation	158	(4)
Fuzzy Tree Transducer	162	(4)
Fuzzy Meaning of Context-Free Languages	166	(4)
Exercises	170	(3)
Probabilistic Automata and Grammars	173	(64)
Probabilistic Automata and Their Approximation	173	(4)
ε-Approximating by Nonprobability Devices	177	(3)
ε-Approximating by Finite Automata	180	(1)
Applications	181	(2)
The Pε Relation	183	(3)
Fuzzy Stars Acceptors and Probabilistic Acceptors	186	(1)
Characterizations and the Rε-Relation	187	(4)
Probabilistic and Weighted Grammars	191	(6)
Probabilistic and Weighted Grammars of Type 3	197	(5)
Interrelations with Programmed and Time-Variant Grammars	202	(2)
Probabilistic Grammars and Automata	204	(1)
Probabilistic Grammars	205	(4)
Weakly Regular Grammars and Asynchronous Automata	209	(4)
Type-0 Probabilistic Grammars and Probabilistic Turing Machines	213	(4)
Context-Free Probabilistic Grammars and Pushdown Automata	217	(5)
Realization of Fuzzy Languages by Various Automata	222	(6)
Properties of Lk, k = 1,2,3	228	(3)
Further Properties of L3	231	(3)
Exercises	234	(3)
Algebraic Fuzzy Automata Theory	237	(88)
Fuzzy Finite State Machines	237	(1)
Semigroups of Fuzzy Finite State Machines	237	(5)
Homomorphisms	242	(3)
Admissible Relations	245	(2)
Fuzzy Transformation Semigroups	247	(6)
Products of Fuzzy Finite State Machines	253	(15)
Submachines of a Fuzzy Finite State Machines	268	(4)
Retrievability, Separability, and Connectivity	272	(2)
Decomposition of Fuzzy Finite State Machines	274	(3)
Subsystems of Fuzzy Finite State Machines	277	(6)
Strong Subsystems	283	(4)
Cartesian Composistion of Fuzzy Finite State Machines	287	(2)
Cartesian Composition	289	(7)
Admissible Partitions	296	(8)
Coverings of Products of Fuzzy Finite State Machines	304	(2)
Associative Properties of Products	306	(2)
Covering Properties of Products	308	(4)
Fuzzy Semiautomation over a Finite Group	312	(10)
Exercises	322	(3)
More on Fuzzy Languages	325	(66)
Fuzzy Regular Languages	325	(9)
On Fuzzy Recognizers	334	(13)
Minimal Fuzzy Recognizers	347	(6)
Fuzzy Recognizers and Recognizable Sets	353	(1)
Operations on (Fuzzy) Subsets	354	(4)
Construction of Recognizers and Recognizable Sets	358	(4)
Accessible and Coaccessible Recognizers	362	(2)
Complete Fuzzy Machines	364	(2)
Fuzzy Languages on a Free Monoid	366	(4)
Algebraic Character and Properties of Fuzzy Regular Languages	370	(13)
Deterministic Acceptors of Regular Fuzzy Languages	383	(5)
Exercises	388	(3)
Minimization of Fuzzy Automata	391	(32)
Equivalence, Reduction, and Minimization of Finite Fuzzy Automata	391	(5)
Equivalence of Fuzzy Automata: An Algebraic Approach	396	(4)
Reduction and Minimization of Fuzzy Automata	400	(4)
Minimal Fuzzy Finite State Automata	404	(6)
Behavior, Reduction, and Minimization of Finite L-Automata	410	(1)
Matrices over a Bounded Chain	410	(2)
Systems of Linear Equivalences over a Bounded Chain	412	(2)
Finite L-Automata-Behavior Matrix	414	(2)
ε-Equivalence	416	(2)
ε-Irreducibility	418	(1)
Minimization	419	(2)
Exercises	421	(2)
L-Fuzzy Automata, Grammars, and Languages	423	(40)
Fuzzy Recognition of Fuzzy Languages	423	(1)
Fuzzy Languages	424	(2)
Fuzzy Recognition by Machines	426	(4)
Cutpoint Languages	430	(5)
Fuzzy Languages not Fuzzy Recognized by Machines in DT2	435	(1)
Rational Probabilistic Events	436	(2)
Recursive Fuzzy Languages	438	(1)
Closure Properties	439	(2)
Fuzzy Grammars and Recursively Enumerable Fuzzy Languages	441	(1)
Recursively Enumerable L-Subsets	442	(4)
Various Kinds of Automata with Weights	446	(15)
Exercises	461	(2)
Applications	463	(66)
A Formulation of Fuzzy Automata and Its Application as a Model of Learning Systems	463	(1)
Formulation of Fuzzy Automata	463	(3)
Special Cases of Fuzzy Automata	466	(2)
Fuzzy Automata as Models of Learning Systems	468	(3)
Applications and Simulation Results	471	(8)
Properties of Fuzzy Automata	479	(2)
Fractionally Fuzzy Grammars and Pattern Recognition	481	(3)
Fractionally Fuzzy Grammars	484	(6)
A Pattern Recognition Experiment	490	(4)
General Fuzzy Acceptors for Syntactic Pattern Recognition	494	(2)
ε-Equivalence by Inputs	496	(3)
Fuzzy-State Automata: Their Stability and Fault Tolerance	499	(1)
Relational Description of Automata	500	(4)
Fuzzy-State Automata	504	(4)
Stable and Almost Stable Behavior of Fuzzy-State Automata	508	(3)
Fault Tolerance of Fuzzy-State Automata	511	(5)
Clinical Monitoring with Fuzzy Automata	516	(6)
Fuzzy Systems	522	(4)
Exercises	526	(3)
References	529	(18)
Index	547