Two dynamic programming algorithms for which interpreted pebbling helps (Q2277375): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
ReferenceBot (talk | contribs)
Changed an Item
 
(One intermediate revision by one other user not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4091421 / rank
 
Normal rank
Property / cites work
 
Property / cites work: An observation on time-storage trade off / rank
 
Normal rank
Property / cites work
 
Property / cites work: Speedups of deterministic machines by synchronous parallel machines / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Pebbling Problem is Complete in Polynomial Space / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4128417 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5592246 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3862379 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q5180413 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4192112 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3947137 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Tree-size bounded alternation / rank
 
Normal rank
Property / cites work
 
Property / cites work: Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space Implementations / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fast Parallel Computation of Polynomials Using Few Processors / rank
 
Normal rank
Property / cites work
 
Property / cites work: Properties that characterize LOGCFL / rank
 
Normal rank
Property / cites work
 
Property / cites work: A New Pebble Game that Characterizes Parallel Complexity Classes / rank
 
Normal rank

Latest revision as of 15:35, 21 June 2024

scientific article
Language Label Description Also known as
English
Two dynamic programming algorithms for which interpreted pebbling helps
scientific article

    Statements

    Two dynamic programming algorithms for which interpreted pebbling helps (English)
    0 references
    0 references
    1991
    0 references
    We consider extensions of one-person and two-person pebble games that take into account the types of the gates of the circuits on which the games are played. A simple relationship is established between the extended games and the corresponding original games. This is useful in showing that the extended games allow more efficient pebbling than the original games on certain natural circuits for problems such as context- free language recognition and transitive closure of directed graphs.
    0 references
    pebble games
    0 references
    context-free language recognition
    0 references
    transitive closure of directed graphs
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references