Graph algebras and automata. (English) Zbl 1070.68097

Pure and Applied Mathematics, Marcel Dekker 257. New York, NY: Marcel Dekker (ISBN 0-8247-4708-9/hbk). viii, 366 p. (2003).
The book is a very thorough research monograph and the first one devoted to graph algebras.
The investigation of graph algebras has started fairly recently and the book reflects in a large measure the author’s valuable and well-recognized contribution in this regard. The concept was introduced by G. F. McNulty and C. R. Shallon in 1983. Let \(D=(V,E)\) be a directed graph. The graph algebra associated with \(D\) is the set \(V \cup \{0\}\) equipped with multiplication defined by the rule \[ xy=\begin{cases} x & \text{if } x,y \in V \text{ and } (x,y) \in E \\0& \text{otherwise}. \end{cases} \]
Apart from providing a profound presentation of the most important results on graph algebras, this text offers a detailed coverage of all necessary fundamentals required for a self-understanding book. The way of presentation is bridging the gap between the results that appeared in publications addressing advanced specialists and a unified fashion with required preliminaries included for convenience of the reader.
The blend of the abstract theory of graph algebras with its practical use in many other research areas of computer science, combinatorics, graph theory, operations research and universal algebras succeeds to reflect the importance of graph algebras in establishing nontrivial relations among different notions on the one hand and to apply methods of one of these theories in order to answer questions motivated by complementary branches on the other.
The first three chapters of the book: 1. Preliminaries; 2. Algebraic structures; 3. Automata and languages, concentrate on introducing a background knowledge. The reader has benefit from a large number of examples and practical exercises.
The next eight chapters are focused on using graph algebras as a means for providing valuable insights into the essential properties of automata, languages, groupoid rings, etc. Their headings are: 4. Syntactic monoids of automata; 5. Congruences on automata; 6. Minimal automata; 7. Languages; 8. Tree languages; 9. Equational theories; 10. Groupoid rings; 11. Dualities, topologies, flatness.
As a peculiarity, these chapters are small sized and devoted to some specific topic on graph algebras, presented in a convenient form and in the unified frame provided by the book. These chapters can be regarded as a unified and solid fundament for a deeper study of graph algebras. Some topics for further investigation are suggested in Chapter 12. Open problems.
By content and way of presentation, the book may serve as a basis for undergraduate or graduate student courses. It should be added that any researcher with more than a passing interest in graph algebras could find hints for further investigations on that topic.


68Q70 Algebraic theory of languages and automata
68Q45 Formal languages and automata
68-02 Research exposition (monographs, survey articles) pertaining to computer science