ALMOST FULLY-PARALLEL PARENTHESES MATCHING

The parentheses matching problem is considered. Suppose we are given a balanced sequence of parentheses and wish to find for each parenthesi s its mate. Assuming the levels of nesting of each parenthesis are giv en, we present an algorithm that runs in O(alpha(n)) time using an opt imal number of processors (where alpha(n) is the inverse of Ackermann' s function) on the CRCW PRAM. Without this assumption the running time becomes O(log n/log log n).