Two dynamic programming algorithms for which interpreted pebbling helps

DOI10.1016/0890-5401(91)90010-YMaRDI QIDQ2277375zbMATH OpenFDO

Authors H. Venkateswaran

Publication date 1991

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(91)90010-Y

zbMATH Keywords

context-free language recognitionpebble gamestransitive closure of directed graphs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) 2-person games (91A05) Games involving graphs (91A43)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 3871062
• Pebbling Algorithms in Diameter Two Graphs
• Dynamic programming and pseudo-inverses
• From dynamic programming to bynamic programming
• scientific article; zbMATH DE number 1260458
• scientific article; zbMATH DE number 1431652
• Dynamic programming
• scientific article; zbMATH DE number 53073
• scientific article; zbMATH DE number 5866260

Cites work

• A New Pebble Game that Characterizes Parallel Complexity Classes
• An observation on time-storage trade off
• Fast Parallel Computation of Polynomials Using Few Processors
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3765164 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3555903 (Why is no real title available?)
• scientific article; zbMATH DE number 3630813 (Why is no real title available?)
• scientific article; zbMATH DE number 3428547 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Properties that characterize LOGCFL
• Speedups of deterministic machines by synchronous parallel machines
• The Pebbling Problem is Complete in Polynomial Space
• Tree-size bounded alternation
• Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space Implementations

Cited in

(4)

• The complexity of short two-person games
• The complexity of computing maximal word functions
• An infinite pebble game and applications
• Rounds versus time for the two person pebble game (extended abstract)

This page was built for publication: Two dynamic programming algorithms for which interpreted pebbling helps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2277375)