Fuzzy Automata and Languages: Theory and Applications (Computational Mathematics)

FUZZY AUTOMATA and LANGUAGES: Theory and Applications......Page 1
Preface......Page 5
Authors......Page 8
CONTENTS......Page 9
List of Symbols......Page 14
1.1 Sets......Page 17
1.2 Relations......Page 18
1.3 Functions......Page 22
1.4 Fuzzy Subsets......Page 24
1.5 Semigroups......Page 25
1.6 Finite-State Machines......Page 29
1.7 Finite-State Automata......Page 31
1.8 Languages and Grammars......Page 36
1.9 Nondeterministic Finite-State Automata......Page 40
1.10 Relationships Between Languages and Automata......Page 46
1.11 Pushdown Automata......Page 52
1.12 Exercises......Page 58
2.2 General Formulation of Automata......Page 60
2.3 Classes of Automata......Page 61
2.4 Behavior of Max-Min Automata......Page 63
2.5 Equivalences and Homomorphisms of Max-Min Automata......Page 66
2.6 Reduction of Max-Min Automata......Page 70
2.7 Definite Max-Min Automata......Page 71
2.8 Reduction of Max-Min Machines......Page 73
2.9 Equivalences......Page 82
2.10 Irreducibility and Minimality......Page 90
2.11 Nondeterministic and Deterministic Case......Page 101
2.12 Exercises......Page 103
3.1 Max-Product Machines......Page 105
3.2 Equivalences......Page 109
3.3 Irreducibility and Minimality......Page 112
3.4 Max-Product Grammars and Languages......Page 116
3.5 Weak Regular Max-Product Grammars......Page 122
3.6 Weak Regular Max-Product Languages......Page 130
3.7 Properties of £......Page 134
3.8 Exercises......Page 139
4.1 Fuzzy Languages......Page 140
4.2 Types of Grammars......Page 143
4.3 Fuzzy Context-Free Grammars......Page 144
4.4 Context-Free Max-Product Grammars......Page 150
4.5 Context-Free Fuzzy Languages......Page 154
4.6 On the Description of the Fuzzy Meaning of Context-Free Languages......Page 159
4.7 Trees and Pseudoterms......Page 160
4.8 Fuzzy Dendrolanguage Generating Systems......Page 161
4.9 Normal Form of F-CFDS......Page 163
4.10 Sets of Derivation Trees of Fuzzy Context-Free Grammars......Page 167
4.11 Fuzzy Tree Automaton......Page 171
4.12 Fuzzy Tree Transducer......Page 175
4.13 Fuzzy Meaning of Context-Free Languages......Page 179
4.14 Exercises......Page 183
5.1 Probabilistic Automata and Their Approximation......Page 185
5.2 E-Approximating by Nonprobability Devices......Page 189
5.3 E-Approximating by Finite Automata......Page 192
5.4 Applications......Page 193
5.5 The PE Relation......Page 195
5.6 Fuzzy Stars Acceptors and Probabilistic Acceptors......Page 198
5.7Characterizations and the RE-Relation......Page 199
5.8 Probabilistic and Weighted Grammars......Page 203
5.9 Probabilistic and Weighted Grammars of Type 3......Page 209
5.10 Interrelations with Programmed and Time-Variant Grammars......Page 214
5.11 Probabilistic Grammars and Automata......Page 216
5.12 Probabilistic Grammars......Page 217
5.13 Weakly Regular Grammars and Asynchronous Automata......Page 221
5.14 Type-0 Probabilistic Grammars and ProbabilisticTuring Machines......Page 225
5.15 Context-Free Probabilistic Grammars and Pushdown Automata......Page 229
5.16 Realization of Fuzzy Languages by Various Automata......Page 234
5.17 Properties of Lk, k = 1, 2, 3......Page 240
5.18 Rirther Properties of L3......Page 243
5.19 Exercises......Page 246
6.2 Semigroups of Fuzzy Finite State Machines......Page 248
6.3 Homomorphisms......Page 253
6.4 Admissible Relations......Page 256
6.5 Fuzzy Transformation Semigroups......Page 258
6.6 Products of Fuzzy Finite State Machines......Page 264
6.7 Submachines of a Fuzzy Finite State Machine......Page 279
6.8 Retrievability, Separability, and Connectivity......Page 283
6.9 Decomposition of Fuzzy Finite State Machines......Page 285
6.10 Subsystems of Fuzzy Finite State Machines......Page 288
6.11 Strong Subsystems......Page 294
6.12 Cartesian Composition of Fuzzy Finite State Machines......Page 298
6.13 Cartesian Composition......Page 300
6.14 Admissible Partitions......Page 307
6.15 Coverings of Products of Fuzzy Finite State Machines......Page 315
6.16 Associative Properties of Products......Page 317
6.17 Covering Properties of Products......Page 319
6.18 Fuzzy Semiautomaton over a Finite Group......Page 323
6.19 Exercises......Page 333
7.1 Fuzzy Regular Languages......Page 335
7.2 On Fuzzy Recognizers......Page 344
7.3 Minimal Fuzzy Recognizers......Page 357
7.4 Fuzzy Recognizers and Recognizable Sets......Page 363
7.5 Operations on (Fuzzy) Subsets......Page 364
7.6 Construction of Recognizers and Recognizable Sets......Page 368
7.7 Accessible and Coaccessible Recognizers......Page 372
7.8 Complete Fuzzy Machines......Page 374
7.9 Fuzzy Languages on a Free Monoid......Page 376
7.10 Algebraic Character and Properties of Fuzzy Regular Languages......Page 380
7.11 Deterministic Acceptors of Regular Fuzzy Languages......Page 393
7.12 Exercises......Page 398
8.1 Equivalence, Reduction, and Minimization of Finite Fuzzy Automata......Page 400
8.2 Equivalence of Fuzzy Automata: An Algebraic Approach......Page 405
8.3 Reduction and Minimization of Fuzzy Automata......Page 409
8.4 Minimal Fuzzy Finite State Automata......Page 413
8.6 Matrices over a Bounded Chain......Page 419
8.7 Systems of Linear Equivalences over a Bounded Chain......Page 421
8.8 Finite IL-Automata-Behavior Matrix......Page 423
8.9 E-Equivalence......Page 425
8.10 E-Irreducibility......Page 427
8.11 Minimization......Page 428
8.12 Exercises......Page 430
9.1 Fuzzy Recognition of Fuzzy Languages......Page 431
9.2 Fuzzy Languages......Page 432
9.3 Fuzzy Recognition by Machines......Page 434
9.4 Cutpoint Languages......Page 438
9.5 Fuzzy Languages not Fuzzy Recognized by Machines in DT2......Page 443
9.6 Rational Probabilistic Events......Page 444
9.7 Recursive Fuzzy Languages......Page 446
9.8 Closure Properties......Page 447
9.9 Fuzzy Grammars and Recursively Enumerable Fuzzy Languages......Page 449
9.10 Recursively Enumerable L-Subsets......Page 450
9.11 Various Kinds of Automata with Weights......Page 454
9.12 Exercises......Page 469
10.2 Formulation of Fuzzy Automata......Page 470
10.3 Special Cases of Fuzzy Automata......Page 473
10.4 Fuzzy Automata as Models of Learning Systems......Page 475
10.5 Applications and Simulation Results......Page 478
10.6 Properties of Fuzzy Automata......Page 486
10.7 Fractionally Fuzzy Grammars and Pattern Recognition......Page 488
10.8 Fractionally Fuzzy Grammars......Page 491
10.9 A Pattern Recognition Experiment......Page 497
10.10 General Fuzzy Acceptors for Syntactic Pattern Recognition......Page 501
10.11 E-Equivalence by Inputs......Page 503
10.12 Fuzzy-State Automata: Their Stability and Fault Tolerance......Page 506
10.13 Relational Description of Automata......Page 507
10.14 Fuzzy-State Automata......Page 511
10.15 Stable and Almost Stable Behavior of Fuzzy-State Automata......Page 515
10.16 Fault Tolerance of Fuzzy-State Automata......Page 518
10.17 Clinical Monitoring with Fuzzy Automata......Page 523
10.18 Fuzzy Systems......Page 529
10.19 Exercises......Page 533
References......Page 535