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

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
ReferenceBot (talk | contribs)
Changed an Item
 
(3 intermediate revisions by 3 users not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/0020-0190(88)90031-2 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W86786547 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4773298 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Parallelism in random access machines / rank
 
Normal rank
Property / cites work
 
Property / cites work: Tree-size bounded alternation / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3700838 / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the complexity of parallel parsing of general context-free languages / rank
 
Normal rank
Property / cites work
 
Property / cites work: Parallel time O(log n) recognition of unambiguous context-free languages / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 09:58, 20 June 2024

scientific article
Language Label Description Also known as
English
On efficient parallel computations of costs of paths on a grid graph
scientific article

    Statements

    On efficient parallel computations of costs of paths on a grid graph (English)
    0 references
    0 references
    1988
    0 references
    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...''.
    0 references
    parallel recognition
    0 references
    cost of paths in dags
    0 references
    context-free languages
    0 references
    parallel computation
    0 references
    EREW PRAM
    0 references

    Identifiers