Advertisement
Published in:
1992 | OriginalPaper | Chapter
Kleene Algebra
Author : Dexter C. Kozen
Published in: The Design and Analysis of Algorithms
Publisher: Springer New York
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Consider a binary relation on an n element set represented by an n x n Boolean matrix E. Recall from the last lecture that we can compute the reflexive transitive closure of E by divide-and-conquer as follows: partition E into four submatrices A, B, C, D of size roughly $$ \frac{n}{2}{\rm{ x }}\frac{n}{2} $$ such that A and D are square: $$ E\;{\rm{ = }}\left[ {\frac{{A|B}}{{C|D}}} \right]. $$