On efficient parallel computations of costs of paths on a grid graph
type: Item
instance of: scholarly article
title: On efficient parallel computations of costs of paths on a grid graph
zbMATH Open document ID: 0682.68061
DOI: 10.1016/0020-0190(88)90031-2
author: Wojciech Rytter
published in: Information Processing Letters
publication date: 1988-01-01T00:00:00Z
review text: From the author's text: ``We consider directed acyclic graphs whose edges are labelled by elements of a semiring. It is known that the computation of the cost of paths between two nodes of a k-vertex graph G can be computed in \(\log^ 2k\) time with \(k^ 6\) processors. If G is an n \(\times\) n grid then \(k=n^ 2\) and \(n^ 6\) processors are needed. The main result of this paper is the reduction of the number of processors from \(n^ 6\) to \(n^ 3\) in the case of grid graphs. Two applications are an efficient simulation of two-head finite automata and an efficient parallel computation of the edit-distance. As another application we obtain a recognition of linear context-free languages in \(\log^ 2n\) time with \(n^ 3\) processors. The best algorithms for the recognition of general context-free languages use \(n^ 6\) processors.... Our model of parallel computation is EREW PRAM...''.
reviewed by: Andreas Brandstädt
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 4117864
zbMATH Keywords: parallel recognition
zbMATH Keywords: cost of paths in dags
zbMATH Keywords: context-free languages
zbMATH Keywords: parallel computation
zbMATH Keywords: EREW PRAM
MaRDI profile type: Publication
full work available at URL: 0020-0190(88)90031-2
OpenAlex ID: W86786547
cites work: Q4773298
cites work: Parallelism in random access machines
cites work: Tree-size bounded alternation
cites work: Q3700838
cites work: On the complexity of parallel parsing of general context-free languages
cites work: Parallel time O(log n) recognition of unambiguous context-free languages
description: scientific article; zbMATH DE number 4117864