Operations on sparse relations
- 1 March 1977
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 20 (3) , 171-176
- https://doi.org/10.1145/359436.359446
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(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.Keywords
This publication has 10 references indexed in Scilit:
- Evaluating relational expressions with dense and sparse argumentsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1975
- Operations on sparse relations and efficient algorithms for grammar problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1974
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972
- A Boolean matrix method for the computation of linear precedence functionsCommunications of the ACM, 1972
- Simple LR(k) grammarsCommunications of the ACM, 1971
- A new method for determining linear precedence functions for precedence grammarsCommunications of the ACM, 1969
- Single pass precedence analysisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1969
- Programming Languages: Boolean matrix methods for the detection of simple precedence grammarsCommunications of the ACM, 1968
- EULER: A generalization of ALGOL and its formal definition: Part 1Communications of the ACM, 1966
- Syntactic Analysis and Operator PrecedenceJournal of the ACM, 1963