Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

THE SPACE COMPLEXITY OF TWO PEBBLE GAMES ON TREES

IP.com Disclosure Number: IPCOM000149071D
Original Publication Date: 1979-Apr-30
Included in the Prior Art Database: 2007-Mar-30
Document File: 48 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Loui, Michael C.: AUTHOR [+2]

Abstract

MlCH AEL C. LOlJI APRIL 1979 This report was prepared with the support of the National Science Foundation Grant No. tlCS77-19754 and the PannLe and John Hertz Foundation. MASSACHUSETTS INSTITUTE OF TECHNOLOGY LABORATORJ' FOR COA4PUTER SCIENCE CAM BIXIDCE MASSACHUSETTS 02139 Tine Space Gcilnplexiay of Two PeSble Gawes ona Trees April 1979 Abstract. Fn the scanda~d pebble gatm ehe number of pebbles required es pebble the root of 2 tree can be o r l p t d In tlnw Ilnea!-ly proportional to the nur-iibe~ of nodes. For the black/whaee pebble game the l.iiaml~er of pebbles necessary to pei~ble the root of a complete eree ss derived. gey Words: pebble game, tree, colnputational camplexiey. Michael C. L,ouit Lnbo?aior.y Jor Conipute.r Scie?rce Mnssas Auselts %~zstitutcof Technology C;ai.rttrricigt., M~ssa~'husetts 02139 i~upilul-ted by tile Fannie and John rletrr Fo~indation. A combinatorial "pebb%e9"$arne on graphs has been used to estab'llsh trade-offs between time

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 7% of the total text.

Page 1 of 48

MIT/LCS/m-133

THE SPACE COMPLEXITY OF TWO PEBBLE GAMES ON TREES

MlCH AEL C. LOlJI

APRIL 1979

This report was prepared with the support of the National Science Foundation
Grant No.
tlCS77-19754 and the PannLe and John Hertz Foundation.

MASSACHUSETTS INSTITUTE OF TECHNOLOGY LABORATORJ' FOR COA4PUTER SCIENCE

CAM BIXIDCE MASSACHUSETTS 02139

[This page contains 1 picture or other non-text object]

Page 2 of 48

Tine Space Gcilnplexiay of Two PeSble Gawes ona Trees

Michael C. L,ouit

April 1979

  Lnbo?aior.y Jor Conipute.r Scie?rce Mnssas Auselts %~zstitutc
of Technology C;ai.rttrricigt., M~ssa~'husetts

02139

Abstract. Fn the scanda~d pebble gatm ehe number of pebbles required es pebble the root of --

2 tree can be ~ o r ~ l p ~ t @ d

                    In tlnw Ilnea!-ly proportional to the nur-iibe~ of nodes. For the black/whaee pebble game the l.iiaml~er of pebbles necessary to pei~ble the root of a complete eree ss derived.

gey Words:

- pebble game, tree, colnputational camplexiey.

i~upilul-ted by tile Fannie and John rletrr Fo~indation.

[This page contains 1 picture or other non-text object]

Page 3 of 48

A combinatorial "pebb%e9"$arne on graphs has been used to estab'llsh trade-offs between time

and space required for arithmetic expression evaluation [PI and for Turirag machine simulation

[HPV]. Given a directed acyclic graph ]P and several pebbles, one places pebbles con the nodes of in steps according to the fo'ollowia~g rules:

Standard Pebble Gam?
(1) A SU?~ consists of either

(is) a p8acenirent of a pebble on an empty node, or

(12) a removal of a pebble from a node, or
(c) a shifl sf a pebble to an empty node from one of its immediate p redecesssrs.

    (2) A pebble may be placed otr or shifted to a node only if there are pebbles on ali immediate predecessors of the node. (TAUS, a node with no predecessors can be pebbled.)

     A conf~guraeioq! specifies the nodes of a pebbked graph that hold pebbles. A computation is a finite sequence of coe~figearaticsns (Co, ..., Gn) such that for each t, either Ct-l = Ctp or configuration

Ct-l is transformed irat13 configuration C, by a step that saeic;fies restriction (2). The object of the

game is to pebble a designated node of $P, starring from a configuration in which no pebbles are on the graph. Ordinarily, there is a limit on the number of pebbles that can appear in each configuration during- a. computation.

     This pebble game models the evaluat~on sf an expression by a straight-line program. EzcR pebble represents a storage register. Pebbling a node corre!;ponds to storing a value in a register, removing. a pebble from a node to releasing a register, and pebbling the designat& node to computing the value of the expression. The number of petlbles used measures the amount of
storage (space) used by the program. The number of steps equals the length of the program, equivalently, the time \:hat the program...