Introduction to Lattice Theory with Computer Science Applications
(Sprache: Englisch)
A computational perspective on partial order and lattice theory, focusing on algorithms and their applications
This book provides a uniform treatment of the theory and applications of lattice theory. The applications covered include tracking...
This book provides a uniform treatment of the theory and applications of lattice theory. The applications covered include tracking...
Leider schon ausverkauft
versandkostenfrei
Buch (Gebunden)
85.90 €
42 DeutschlandCard Punkte
sammeln
- Lastschrift, Kreditkarte, Paypal, Rechnung
- Kostenlose Rücksendung
- Ratenzahlung möglich
Produktdetails
Produktinformationen zu „Introduction to Lattice Theory with Computer Science Applications “
Klappentext zu „Introduction to Lattice Theory with Computer Science Applications “
A computational perspective on partial order and lattice theory, focusing on algorithms and their applicationsThis book provides a uniform treatment of the theory and applications of lattice theory. The applications covered include tracking dependency in distributed systems, combinatorics, detecting global predicates in distributed systems, set families, and integer partitions. The book presents algorithmic proofs of theorems whenever possible. These proofs are written in the calculational style advocated by Dijkstra, with arguments explicitly spelled out step by step. The author's intent is for readers to learn not only the proofs, but the heuristics that guide said proofs.
Introduction to Lattice Theory with Computer Science Applications:
* Examines; posets, Dilworth's theorem, merging algorithms, lattices, lattice completion, morphisms, modular and distributive lattices, slicing, interval orders, tractable posets, lattice enumeration algorithms, and dimension theory
* Provides end of chapter exercises to help readers retain newfound knowledge on each subject
* Includes supplementary material at www.ece.utexas.edu/~garg
Introduction to Lattice Theory with Computer Science Applications is written for students of computer science, as well as practicing mathematicians.
Inhaltsverzeichnis zu „Introduction to Lattice Theory with Computer Science Applications “
List of Figures xiiiNomenclature xv
Preface xvii
1 Introduction 1
1.1 Introduction 1
1.2 Relations 2
1.3 Partial Orders 3
1.4 Join and Meet Operations 5
1.5 Operations on Posets 7
1.6 Ideals and Filters 8
1.7 Special Elements in Posets 9
1.8 Irreducible Elements 10
1.9 Dissector Elements 11
1.10 Applications: Distributed Computations 11
1.11 Applications: Combinatorics 12
1.12 Notation and Proof Format 13
1.13 Problems 15
1.14 Bibliographic Remarks 15
2 Representing Posets 17
2.1 Introduction 17
2.2 Labeling Elements of The Poset 17
2.3 Adjacency List Representation 18
2.4 Vector Clock Representation 20
2.5 Matrix Representation 22
2.6 Dimension-Based Representation 22
2.7 Algorithms to Compute Irreducibles 23
2.8 Infinite Posets 24
2.9 Problems 26
2.10 Bibliographic Remarks 27
3 Dilworth's Theorem 29
3.1 Introduction 29
3.2 Dilworth's Theorem 29
3.3 Appreciation of Dilworth's Theorem 30
3.4 Dual of Dilworth's Theorem 32
3.5 Generalizations of Dilworth's Theorem 32
3.6 Algorithmic Perspective of Dilworth's Theorem 32
3.7 Application: Hall's Marriage Theorem 33
3.8 Application: Bipartite Matching 34
3.9 Online Decomposition of Posets 35
3.10 A Lower Bound on Online Chain Partition 37
3.11 Problems 38
3.12 Bibliographic Remarks 39
4 Merging Algorithms 41
4.1 Introduction 41
4.2 Algorithm to Merge Chains in Vector Clock Representation 41
4.3 An Upper Bound for Detecting an Antichain of Size K 47
4.4 A Lower Bound for Detecting an Antichain of Size K 48
4.5 An Incremental Algorithm for Optimal Chain Decomposition 50
4.6 Problems 50
4.7
... mehr
Bibliographic Remarks 51
5 Lattices 53
5.1 Introduction 53
5.2 Sublattices 54
5.3 Lattices as Algebraic Structures 55
5.4 Bounding The Size of The Cover Relation of a Lattice 56
5.5 Join-Irreducible Elements Revisited 57
5.6 Problems 59
5.7 Bibliographic Remarks 60
6 Lattice Completion 61
6.1 Introduction 61
6.2 Complete Lattices 61
6.3 Closure Operators 62
6.4 Topped intersection -Structures 63
6.5 Dedekind-Macneille Completion 64
6.6 Structure of Dedekind--Macneille Completion of a Poset 67
6.7 An Incremental Algorithm for Lattice Completion 69
6.8 Breadth First Search Enumeration of Normal Cuts 71
6.9 Depth First Search Enumeration of Normal Cuts 73
6.10 Application: Finding the Meet and Join of Events 75
6.11 Application: Detecting Global Predicates in Distributed Systems 76
6.12 Application: Data Mining 77
6.13 Problems 78
6.14 Bibliographic Remarks 78
7 Morphisms 79
7.1 Introduction 79
7.2 Lattice Homomorphism 79
7.3 Lattice Isomorphism 80
7.4 Lattice Congruences 82
7.5 Quotient Lattice 83
7.6 Lattice Homomorphism and Congruence 83
7.7 Properties of Lattice Congruence Blocks 84
7.8 Application: Model Checking on Reduced Lattices 85
7.9 Problems 89
7.10 Bibliographic Remarks 90
8 Modular Lattices 91
8.1 Introduction 91
8.2 Modular Lattice 91
8.3 Characterization of Modular Lattices 92
5 Lattices 53
5.1 Introduction 53
5.2 Sublattices 54
5.3 Lattices as Algebraic Structures 55
5.4 Bounding The Size of The Cover Relation of a Lattice 56
5.5 Join-Irreducible Elements Revisited 57
5.6 Problems 59
5.7 Bibliographic Remarks 60
6 Lattice Completion 61
6.1 Introduction 61
6.2 Complete Lattices 61
6.3 Closure Operators 62
6.4 Topped intersection -Structures 63
6.5 Dedekind-Macneille Completion 64
6.6 Structure of Dedekind--Macneille Completion of a Poset 67
6.7 An Incremental Algorithm for Lattice Completion 69
6.8 Breadth First Search Enumeration of Normal Cuts 71
6.9 Depth First Search Enumeration of Normal Cuts 73
6.10 Application: Finding the Meet and Join of Events 75
6.11 Application: Detecting Global Predicates in Distributed Systems 76
6.12 Application: Data Mining 77
6.13 Problems 78
6.14 Bibliographic Remarks 78
7 Morphisms 79
7.1 Introduction 79
7.2 Lattice Homomorphism 79
7.3 Lattice Isomorphism 80
7.4 Lattice Congruences 82
7.5 Quotient Lattice 83
7.6 Lattice Homomorphism and Congruence 83
7.7 Properties of Lattice Congruence Blocks 84
7.8 Application: Model Checking on Reduced Lattices 85
7.9 Problems 89
7.10 Bibliographic Remarks 90
8 Modular Lattices 91
8.1 Introduction 91
8.2 Modular Lattice 91
8.3 Characterization of Modular Lattices 92
... weniger
Autoren-Porträt von Vijay K. Garg
Vijay K. Garg, PhD, is a Cullen Trust Endowed professor at the University of Texas at Austin. His research focuses on applications of lattice theory to distributed computing. He has worked in the areas of distributed systems and discrete event systems for the past thirty years. Dr. Garg is the author of Elements of Distributed Computing (Wiley, 2002), Concurrent and Distributed Computing in Java (Wiley, 2004) and Modeling and Control of Logical Discrete Event Systems (co-authored with Ratnesh Kumar).
Bibliographische Angaben
- Autor: Vijay K. Garg
- 2015, 1. Auflage, 272 Seiten, Maße: 15 x 25 cm, Gebunden, Englisch
- Verlag: Wiley & Sons
- ISBN-10: 1118914376
- ISBN-13: 9781118914373
Sprache:
Englisch
Kommentar zu "Introduction to Lattice Theory with Computer Science Applications"
0 Gebrauchte Artikel zu „Introduction to Lattice Theory with Computer Science Applications“
| Zustand | Preis | Porto | Zahlung | Verkäufer | Rating |
|---|
Schreiben Sie einen Kommentar zu "Introduction to Lattice Theory with Computer Science Applications".
Kommentar verfassen