Access Restriction

Author Ullman, J. D. ♦ Hunt, H. B. ♦ Szymanski, T. G.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Wirth-weber precedence relation ♦ Boolean matrix ♦ Slr grammar ♦ Linear precedence function ♦ T-canomical precedence relation ♦ Sparse relation ♦ Computational complexity ♦ Directed graph
Abstract 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.
Description Affiliation: Harvard Univ., Cambridge, MA (Hunt, H. B.) || Princeton Univ., Princeton, NJ (Ullman, J. D.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 20
Issue Number 3
Page Count 6
Starting Page 171
Ending Page 176

Open content in new tab

   Open content in new tab
Source: ACM Digital Library