Research and Advances

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(n2) steps is shown, as well as how to compute linear precedence functions in O(n) steps, where n is the size of a grammar. 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.

Advertisement

Author Archives

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved