Optimal parallel algorithms for dynamic expression evaluation and context-free recognition
type: Item
instance of: scholarly article
title: Optimal parallel algorithms for dynamic expression evaluation and context-free recognition
zbMATH Open document ID: 0682.68046
DOI: 10.1016/0890-5401(89)90027-8
author: Wojciech Rytter
author: A. Gibbons
published in: Information and Computation
publication date: 1989-01-01T00:00:00Z
review text: 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.
reviewed by: Dorel Lucanu
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 4117849
zbMATH Keywords: analysis of algorithms
zbMATH Keywords: parallel algorithms
zbMATH Keywords: dynamic expression evaluation
zbMATH Keywords: context-free recognition
zbMATH Keywords: parallel random access machine
MaRDI profile type: Publication
full work available at URL: 0890-5401(89)90027-8
OpenAlex ID: W2015439916
cites work: Optimal parallel generation of a computation tree form
cites work: An introduction to parallelism in combinatorial optimization
cites work: Q3700838
cites work: Q5753770
cites work: Q3742751
cites work: An application of Mehlhorn's algorithm for bracket languages to log(n) space recognition of input-driven languages
cites work: Parallel time O(log n) recognition of unambiguous context-free languages
description: scientific article; zbMATH DE number 4117849