Optimal parallel algorithms for dynamic expression evaluation and context-free recognition

We describe a deterministic parallel algorithm to evaluate algebraic expressions in O(log n) time using n log(n) processors on a parallel random access machine without write conflicts (P-RAM) and with no free preprocessing. The input to the algorithm is a string (of the symbols making up the expression) store in an array. Such a form for the input enables a consecutive numbering of the operands in the expression in O(log(n)) time with n log(n) processors. This corresponds to a consecutive numbering of the leaves of the expression tree. This then further permits us to partition the leaves into small segments. We improve the result of Miller and Reif (1985, in “26th IEEE Sympos. on Found. of Comput. Sci. ,” pp. 478–489), who described an optimal parallel randomized algorithm. (Strictly speaking, the input to their algorithm is different being the parse tree of the expression. The input to the innovative part of our algorithm (step 2) is this parse tree which, in addition, has its leaves numbered consecutively from left to right. These two orms are equivalent if we note that such a numbering can be obtained by an optimal parallel algorithm which employs the Euler tour technique and optimal list ranking). Our algorithm can be used to construct optimal parallel algorithms for the recognition of two nontrival subclasses of context-free languages: bracket and input-driven languages. These languages are the most complicated context-free languages known to be recognizable in deterministic logarithmic space. This strengthens the result of Matheyses and Fiduccia (1982 in “20th Allerton Conf. on Commun. Control and Comput. ”) who constructed an almost optimal parallel algorithm for Dyck languages, since Dyck languages are a proper subclass of input-driven languages. Our algorithm includes a new simple method for tree contraction which we call the leaves-cutting method. Its correctness is trival (compared with the method of Miller and Reif) and it can be implemented on a P-RAM without write and without read conflicts.

Authors

• Alan Gibbons
• Wojciech Rytter

Keywords

No keywords are indexed for this paper.