On efficient parallel computations of costs of paths on a grid graph (Q1824395): Difference between revisions

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...''.