Before revision: Recently, the predicate detection problem was shown to be in the parallel complexity class NC . In this paper, we give some more work efficient parallel algorithms to solve the predicate detection problem on a distributed computation with n processes and at most m states per process.
After revision: Recently, the predicate detection problem was shown to be in the parallel complexity class NC . In this paper, we give the first work-optimal parallel algorithm to solve the predicate detection problem on a distributed computation with n processes and at most m states per process.