Graph Algebras and Automata

by Kelarev; Andrei

• ISBN13: 9780824747084
• ISBN10: 0824747089
• Edition: 1st
• Format: Hardcover
• Copyright: 2003-07-08
• Publisher: CRC Press

Summary

Graph algebras possess the capacity to relate fundamental concepts of computer science, combinatorics, graph theory, operations research, and universal algebra. They are used to identify nontrivial connections across notions, expose conceptual properties, and mediate the application of methods from one area toward questions of the other four. After a concentrated review of the prerequisite mathematical background, Graph Algebras and Automata defines graph algebras and reveals their applicability to automata theory. It proceeds to explore assorted monoids, semigroups, rings, codes, and other algebraic structures and to outline theorems and algorithms for finite state automata and grammars.

Author Biography

Andrei Kelarev is a Senior Lecturer in Mathematics at the University of Tasmania, Hobart, Australia.

Table of Contents

Preface	p. v
Preliminaries	p. 1
Sets	p. 1
Sequences	p. 7
Functions or Mappings	p. 8
Operations	p. 15
Modular Arithmetic	p. 16
Extended Euclidean Algorithm	p. 19
Euler's Theorem and RSA Cryptosystem	p. 23
Relations	p. 31
Graphs	p. 34
Exercises	p. 36
Algebraic Structures	p. 39
Words and Free Monoids	p. 39
Groupoids	p. 49
Semigroups and Monoids	p. 52
Cayley Graphs	p. 60
Groups	p. 64
Commutative Semigroups	p. 69
Rees Matrix Semigroups	p. 73
Finite Semigroups	p. 79
Lattices	p. 82
Boolean Algebras	p. 84
Rings	p. 87
Fields and Vector Spaces	p. 91
Polynomial Rings and Finite Fields	p. 97
Matrix Rings	p. 107
Linear Codes	p. 111
Cyclic Codes	p. 124
Universal Algebras	p. 131
Exercises	p. 136
Automata and Languages	p. 143
Finite State Automata	p. 143
Language Accepted by Automata	p. 148
Operations on Languages, Regular Expressions	p. 150
Algorithm 1: Language Accepted by FSA	p. 154
Constructing Automata for Languages	p. 159
Algorithm 2: Language Accepted by FSA	p. 170
Minimization Algorithm	p. 173
Syntactic and Transformation Monoids	p. 179
Krohn-Rhodes Decomposition Theorem	p. 186
Grammars and Rewriting Systems	p. 190
Other Classes of Automata	p. 195
Tree Languages	p. 209
Exercises	p. 212
Syntactic Monoids of Automata	p. 219
Congruences on Automata	p. 227
Minimal Automata	p. 249
Languages	p. 255
Tree Languages	p. 283
Equational Theories	p. 289
Groupoid Rings	p. 311
Dualities, Topologies, Flatness	p. 315
Open Problems	p. 321
Glossary of Notation	p. 323
Bibliography	p. 329
Index	p. 351
Table of Contents provided by Ingram. All Rights Reserved.