Operations on sparse relations
| Autor: | Jeffrey D. Ullman, Harry B. Hunt, Thomas G. Szymanski |
|---|---|
| Rok vydání: | 1977 |
| Předmět: | |
| Zdroj: | Communications of the ACM. 20:171-176 |
| ISSN: | 1557-7317 0001-0782 |
| DOI: | 10.1145/359436.359446 |
| Popis: | 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) 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|