Operations on Sparse Relations

Various computations on relations, Boolean matrices,
or directed graphs, such as the computation 
of precedence relations for a context-free grammar, can be
done by a practical algorithm that is asymptotically 
faster than those in common use.  For example, how to compute
operator precedence or Wirth-Weber precedence 
relations in O(n^2) steps is shown, as well as how to
compute linear precedence functions in O(n^2) steps 
is shown, as well as how to compute linear precedence
functions in O(n) steps, where n is the size of 
a grammer.  The heart of the algorithms is a general
theorem giving sufficient conditions under which 
an expression whose operands are sparse relations and
whose operators are composition, transitive closure, 
union, and inverse, can be computed efficiently.

CACM March, 1977

Hunt, H. B. III
Szymanski, T. G.
Ullman, J. D.

computational complexity, sparse relation, Boolean
matrix, directed graph, Wirth-Weber precedence 
relation, linear precedence function, SLR
grammar, T-canonical precedence relation

4.12 5.23 5.25

CA770306 JB December 29, 1977  8:05 AM

1542	4	2986
1683	4	2986
1693	4	2986
1781	4	2986
1787	4	2986
1836	4	2986
1945	4	2986
2060	4	2986
2061	4	2986
2082	4	2986
2091	4	2986
2152	4	2986
2179	4	2986
2221	4	2986
2340	4	2986
2340	4	2986
2340	4	2986
2356	4	2986
2546	4	2986
2603	4	2986
2698	4	2986
2708	4	2986
2733	4	2986
2824	4	2986
2824	4	2986
2824	4	2986
2982	4	2986
2982	4	2986
2982	4	2986
2986	4	2986
2986	4	2986
2986	4	2986
2986	4	2986
2986	4	2986
3045	4	2986
3093	4	2986
3093	4	2986
3094	4	2986
1491	5	2986
1683	5	2986
1836	5	2986
2179	5	2986
2340	5	2986
2986	5	2986
2986	5	2986
2986	5	2986