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).