Research and Advances

Operations on sparse relations

Posted

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.

View this article in the ACM Digital Library.

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

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

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More