| Autor: |
Manacher, G., Graham, S. L., Hunt, III, H. B., Szymanski, T. G., Ullman, J. D. |
| Předmět: |
|
| Zdroj: |
Communications of the ACM; Mar1977, Vol. 20 Issue 3, p171-176, 6p, 4 Diagrams |
| Abstrakt: |
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²) 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. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
