Almost fully-parallel parentheses matching

The parentheses matching problem is considered. Suppose the authors are given a balanced sequence of parentheses and wish to find for each parenthesis its mate. Assuming the levels of nesting of each parenthesis are given, they present an algorithm that runs in O(α(n)) time using an optimal number of processors (where α(n) is the inverse Ackermann’s function) on the CRCW PRAM. Without this assumption the running time becomes O(logn/loglogn).