Almost fully-parallel parentheses matching Original Research Article

The parentheses matching problem is considered. Suppose we 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, we present an algorithm that runs in O (α(n)) time using an optimal number of processors (where α(n) is the inverse of Ackermannʹs function) on the CRCW PRAM. Without this assumption the running time becomes O(log nlog log n).