Relations and Graphs
Discrete Mathematics for Computer Scientists
Published on 16. January 2012
Book
Paperback/Softback
IX, 301 pages
978-3-642-77970-1 (ISBN)
Description
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.
More details
Series
Edition
Softcover reprint of the original 1st ed. 1993
Language
English
Place of publication
Berlin
Germany
Publishing group
Springer Berlin
Target group
Professional and scholarly
Research
Illustrations
IX, 301 p.
Dimensions
Height: 235 mm
Width: 155 mm
Thickness: 18 mm
Weight
487 gr
ISBN-13
978-3-642-77970-1 (9783642779701)
DOI
10.1007/978-3-642-77968-8
Schweitzer Classification
Other editions
Additional editions
Book
04/1993
Springer
€85.55
Article exhausted; check different version
Persons
Gunther Schmidt arbeitete in der Komplexen Analysis, geriet aber als Mitarbeiter in die Ingenieurmathematik. Der in München sich entwickelnden Informatik half er früh mit Projekten und Vorlesungen zu Logik, Semantik, Übersetzerbau und Graphentheorie. Seine Arbeit über Relationen machte ihn zum vielfachen Herausgeber und Buchautor.
Content
1. Sets.- 2. Homogeneous Relations.- 2.1 Boolean Operations on Relations.- 2.2 Transposition of a Relation.- 2.3 The Product of Two Relations.- 2.4 Subsets and Points.- 2.5 References.- 3. Transitivity.- 3.1 Orderings and Equivalence Relations.- 3.2 Closures and Closure Algorithms.- 3.3 Extrema, Bounds, and Suprema.- 3.4 References.- 4. Heterogeneous Relations.- 4.1 Bipartite Graphs.- 4.2 Functions and Mappings.- 4.3 n-ary Relations in Data Bases.- 4.4 Difunctionality.- 4.5 References.- 5. Graphs: Associated Relation, Incidence, Adjacency.- 5.1 Directed Graphs.- 5.2 Graphs via the Associated Relation.- 5.3 Hypergraphs.- 5.4 Graphs via the Adjacency Relation.- 5.5 Incidence and Adjacency.- 5.6 References.- 6. Reachability.- 6.1 Paths and Circuits.- 6.2 Chains and Cycles.- 6.3 Terminality and Foundedness.- 6.4 Confluence and Church-Rosser Theorems.- 6.5 Hasse Diagrams and Discreteness.- 6.6 References.- 7. The Category of Graphs.- 7.1 Homomorphisms of 1-Graphs.- 7.2 More Graph Homomorphisms.- 7.3 Covering of Graphs and Path Equivalence.- 7.4 Congruences.- 7.5 Direct Product and n-ary Relations.- 7.6 References.- 8. Kernels and Games.- 8.1 Absorptiveness and Stability.- 8.2 Kernels.- 8.3 Games.- 8.4 References.- 9. Matchings and Coverings.- 9.1 Independence.- 9.2 Coverings.- 9.3 Matching Theorems.- 9.4 Starlikeness.- 9.5 References.- 10. Programs: Correctness and Verification.- 10.1 Programs and Their Effect.- 10.2 Partial Correctness and Verification.- 10.3 Total Correctness and Termination.- 10.4 Weakest Preconditions.- 10.5 Coverings of Programs.- 10.6 References.- General References.- Name Index.- Table of Symbols.