Introduction to Lattice Theory with Computer Science Applications (eBook)

Vijay K. Garg (Autor)

eBook Download: EPUB

2015
John Wiley & Sons (Verlag)
978-1-119-06971-3 (ISBN)

Infos

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 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.

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).

Rezensionen

"This nice book on lattices and their applications in computer science is written from
the perspective of a computer scientist rather than a mathematician...Given its emphasis on algorithms and their complexity, it
seems to be mainly intended for students of computer science and engineering. The
author's approach is based on the premise that a student needs to learn the heuristics
that guide the proofs, besides the proofs themselves, and to learn ways to extend and
analyze theorems...One of the most important and valuable features of the book is its focus on applications
of lattice theory. The author intends to treat applications on par with the theory." Altogether a "lovely book". (Mathematical Reviews/MathSciNet April 2017)

Textauszug

List Of Figures

Figure 1.1

The graph of a relation

Figure 1.2

Hasse diagram

Figure 1.3

Only the first two posets are lattices

Figure 1.4

(a) Pentagon(N5) and (b) diamond(M3)

Figure 1.5

Cross product of posets

Figure 1.6

A computation in the happened-before model

Figure 1.7

Ferrer's diagram for (4,3,2) shown to contain (2,2,2)

Figure 1.8

Young's lattice for (3,3,3)

Figure 2.1

Adjacency list representation of a poset

Figure 2.2

Vector clock labeling of a poset for a distributed computation

Figure 2.3

Vector clock algorithm

Figure 2.4

(a) An antichain of size 5 and (b) its two linear extensions

Figure 2.5

(a,b) Trivial examples of p-diagrams

Figure 2.6

(a) A p-diagram and (b) its corresponding infinite poset

Figure 3.1

Decomposition of P into t chains

Figure 3.2

Hall's Marriage Theorem

Figure 3.3

A poset of width 2 forcing an algorithm to use three chains for decomposition

Figure 3.4

Chain partitioning algorithm

Figure 4.1

Function that determines if an antichain of size k exists

Figure 4.2

An example of a failed naive strategy. (a) The initial configuration. (b) The point at which the strategy fails: there is nowhere to insert (2,0,0). (c) This example can be merged into two chains

Figure 4.3

Generalized merge procedure for deposets

Figure 4.4

Function FindQ that finds the output queue to insert an element

Figure 4.5

Using a queue insert graph to find the output queue

Figure 4.6

Algorithm for the adversary

Figure 5.1

Examples: lattices and sublattices

Figure 5.2

Table notation for the algebra (X, ⊔ , ⊓ )

Figure 5.3

Join-irreducible elements: J(L)={a, b, c, d}

Figure 6.1

(a) A poset. (b) Its completion (the unshaded vertex is the added element)

Figure 6.2

A poset that is not a complete lattice

Figure 6.3

The DM completion of the poset from Figure 6.2

Figure 6.4

Two posets and their DM completions

Figure 6.5

The complete lattice via order ideals that embeds the poset from Figure 6.4(b)

Figure 6.6

Incremental algorithm IDML for DM construction

Figure 6.7

Algorithm BFS-DML for BFS enumeration of DM-Lattice

Figure 6.8

Algorithm DFS-DML for DFS enumeration of DM-lattice

Figure 6.9

(a) The original poset. (b) Equivalent representation using vector clocks. (c) Its Lattice of normal cuts

Figure 7.1

Monotone f

Figure 7.2

Fundamental Homomorphism Theorem

Figure 7.3

(a,b) Quadrilateral-closed structures

Figure 7.4

Simple reduction of state graph does not preserve path based formulas

Figure 7.5

(a,b) Proof of Lemma 7.13

Figure 7.6

Proof of Lemma 7.14

Figure 8.1

Proof of Theorem 8.5

Figure 8.2

Theorem 8.9

Figure 8.3

(a) A ranked poset, (b) A poset that is not ranked, (c) A ranked and graded poset, and (d) A ranked and graded lattice

Figure 9.1

Diamond M3–a nondistributive lattice

Figure 9.2

A lattice L, its set of join-irreducibles J(L), and their ideals LI (J(L))

Figure 9.3

A lattice with the “N-poset” as the set of join-irreducibles

Figure 9.4

(a) Poset of Join- (“j”) and meet- (“m”) irreducible elements are isomorphic; (b) Irreducibles in a nondistributive lattice

Figure 10.1

(a) P: A partial order. (b) The lattice of ideals. (c) The directed graph P′

Figure 10.2

(a) A directed graph and (b) the lattice of its nontrivial ideals

Figure 10.3

(a) The poset or directed graph K for generating subsets of X of size k. (b) The ideal denoting the subset {1,3,4}

Figure 10.4

Graphs and slices for generating subsets of X when |X| = 4

Figure 10.5

An efficient algorithm to detect a linear predicate

Figure 10.6

An efficient algorithm to compute the slice for a predicate B

Figure 10.7

An efficient algorithm to compute the slice for a linear predicate B

Figure 11.1

Graphs and slices for generating subsets of X when |X| = 4

Figure 11.2

Slice for the predicate “does not contain consecutive numbers”

Figure 11.3

Ferrer's diagram for the integer partition (4,2,1) for 7

Figure 11.4

An Application of Ferrer's diagram

Figure 11.5

Young's lattice for (3,3,3)

Figure 11.6

The poset corresponding to Ferrer's diagram of (3,3,3)

Figure 11.7

Slice for δ2 = 2

Figure 11.8

Slice for “distinct parts.”

Figure 11.9

Poset T(5).

Figure 11.10

Slice for subsets of permutations

Figure 12.1

A poset that is a ranking

Figure 12.2

Examples of weak orders (or rankings.)

Figure 12.3

A poset and its normal ranking extension

Figure 12.4

Mapping elements of poset to interval order

Figure 13.1

Example series and parallel compositions. (a–c) Posets. (d) Result of P2 + P3. (e) Result of P1 * (P2 + P3)

Figure 13.2

(a) An SP tree for the poset in Figure 13.1(e). (b) The conjugate SP tree. (c) The conjugate poset

Figure 13.3

(a) A two-dimensional poset. (b) Its comparability graph G. (c) GC. (d) A valid conjugate for the original poset

Figure 13.4

The poset S3

Figure 13.5

(a) is a non-separating linear extension of the partial order (b), when at least one of the dotted edges holds

Figure 13.6

A two-dimensional Poset P=(X,⩽p)

Figure 13.7

Conjugate Q = L1 ∩ L2−1 of the poset P

Figure 13.8

The order imposed by ⩽p ∪ ⩽Q

Figure 13.9

A partial order P that has a nonseparating linear extension

Figure 14.1

(a) A computation. (b) Its lattice of consistent global states. (c) Traversals of the lattice

Figure 14.2

BFS enumeration of CGS

Figure 14.3

A vector clock based BFS enumeration of CGS

Figure 14.4

A vector clock based DFS enumeration of CGS

Figure 14.5

An algorithm for lexical traversal of all ideals of a poset with any chain partition

Figure 14.6

L(3,3) with example of an ideal

Figure...

Produkt-Details

• Erscheint lt. Verlag: 10.6.2015
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Netzwerke
• Themenwelt: Informatik ► Theorie / Studium ► Algorithmen
• Themenwelt: Technik ► Elektrotechnik / Energietechnik
• Schlagworte: bipartite matching • Birkhoff's Representation Theorem • Boolean algebra • combinatorics • Computer Science • Data Mining • Dedekind-MacNeille Completion • Dilworth's theorem • Dimension Theory • Distributed Computing • Electrical & Electronics Engineering • Elektrotechnik u. Elektronik • Enumeration Algorithms • Hall's Marriage Theorem • Informatik • Interval Oders • Lattice Congruences • Lattice Homomorphism • lattice isomorphism • lattice theory • Maximal Antichain Lattice • Merging Algorithms • Modular lattice • Numerical Methods & Algorithms • Numerische Methoden u. Algorithmen • Parallel and Distributed Computing • Paralleles u. Verteiltes Rechnen • Posets • Quotient Lattice • Sublattices • Tractable Posets • Verbandstheorie
• ISBN-10: 1-119-06971-8 / 1119069718
• ISBN-13: 978-1-119-06971-3 / 9781119069713