Ebook: Relations and Graphs: Discrete Mathematics for Computer Scientists

Relational methods can be found at various places in computer science, notably in data base theory, relational semantics of concurrency, relationaltype theory, analysis of rewriting systems, and modern programming language design. In addition, they appear in algorithms analysis and in the bulk of discrete mathematics taught to computer scientists. This book is devoted to the background of these methods. It explains how to use relational and graph-theoretic methods systematically in computer science. A powerful formal framework of relational algebra is developed with respect to applications to a diverse range of problem areas. Results are first motivated by practical examples, often visualized by both Boolean 0-1-matrices and graphs, and then derived algebraically.

---

Relational methods can be found at various places in computer science, notably in data base theory, relational semantics of concurrency, relationaltype theory, analysis of rewriting systems, and modern programming language design. In addition, they appear in algorithms analysis and in the bulk of discrete mathematics taught to computer scientists. This book is devoted to the background of these methods. It explains how to use relational and graph-theoretic methods systematically in computer science. A powerful formal framework of relational algebra is developed with respect to applications to a diverse range of problem areas. Results are first motivated by practical examples, often visualized by both Boolean 0-1-matrices and graphs, and then derived algebraically.

---

Relational methods can be found at various places in computer science, notably in data base theory, relational semantics of concurrency, relationaltype theory, analysis of rewriting systems, and modern programming language design. In addition, they appear in algorithms analysis and in the bulk of discrete mathematics taught to computer scientists. This book is devoted to the background of these methods. It explains how to use relational and graph-theoretic methods systematically in computer science. A powerful formal framework of relational algebra is developed with respect to applications to a diverse range of problem areas. Results are first motivated by practical examples, often visualized by both Boolean 0-1-matrices and graphs, and then derived algebraically.
Content:
Front Matter....Pages i-ix
Sets....Pages 1-4
Homogeneous Relations....Pages 5-27
Transitivity....Pages 28-49
Heterogeneous Relations....Pages 50-80
Graphs: Associated Relation, Incidence, Adjacency....Pages 81-104
Reachability....Pages 105-141
The Category of Graphs....Pages 142-171
Kernels and Games....Pages 172-196
Matchings and Coverings....Pages 197-228
Programs: Correctness and Verification....Pages 229-264
Back Matter....Pages 265-304

---

Relational methods can be found at various places in computer science, notably in data base theory, relational semantics of concurrency, relationaltype theory, analysis of rewriting systems, and modern programming language design. In addition, they appear in algorithms analysis and in the bulk of discrete mathematics taught to computer scientists. This book is devoted to the background of these methods. It explains how to use relational and graph-theoretic methods systematically in computer science. A powerful formal framework of relational algebra is developed with respect to applications to a diverse range of problem areas. Results are first motivated by practical examples, often visualized by both Boolean 0-1-matrices and graphs, and then derived algebraically.
Content:
Front Matter....Pages i-ix
Sets....Pages 1-4
Homogeneous Relations....Pages 5-27
Transitivity....Pages 28-49
Heterogeneous Relations....Pages 50-80
Graphs: Associated Relation, Incidence, Adjacency....Pages 81-104
Reachability....Pages 105-141
The Category of Graphs....Pages 142-171
Kernels and Games....Pages 172-196
Matchings and Coverings....Pages 197-228
Programs: Correctness and Verification....Pages 229-264
Back Matter....Pages 265-304
....