Optimal parallel algorithms for dynamic expression evaluation and context-free recognition
A parallel algorithm that evaluates an algebraic expression in 0(log n) time using n / log(n) processors without free preprocessing is presented. The model used for parallel computations is the parallel random access machine without write conflicts. The method is used for the recognition of two subclasses of context-free languages: bracket and input-driven languages.
scientific article; zbMATH DE number 4117849