Optimal parallel algorithms for dynamic expression evaluation and context-free recognition (Q1824389)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Optimal parallel algorithms for dynamic expression evaluation and context-free recognition |
scientific article |
Statements
Optimal parallel algorithms for dynamic expression evaluation and context-free recognition (English)
0 references
1989
0 references
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.
0 references
analysis of algorithms
0 references
parallel algorithms
0 references
dynamic expression evaluation
0 references
context-free recognition
0 references
parallel random access machine
0 references
0 references
