Advanced

A PSPACE complete problem related to a pebble game

Lingas, Andrzej LU (1978) Automata, Languages and Programming Fifth Colloquium In Automata, Languages and Programming /Lecture notes in computer science 62. p.300-300
Abstract
The pebble game on AND/OR dags which is natural generalization of a well known pebble game on dags is considered. The following problem is given: if k pebbles are enough to place a pebble on a given vertex of an AND/OR dag. It is shown that the problem is log-space complete for languages accepted in polynomial space.
Please use this url to cite or link to this publication:
author
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
pebble game, AND/OR graph, computational complexity, completeness in polynomial space, PSPACE, dag
in
Automata, Languages and Programming /Lecture notes in computer science
volume
62
pages
300 - 300
publisher
Springer
conference name
Automata, Languages and Programming Fifth Colloquium
ISBN
3-540-08860-1
DOI
10.1007/3-540-08860-1_22
language
English
LU publication?
no
id
1d13b8d1-0eb6-4179-af46-6faf70081dcd (old id 1664650)
date added to LUP
2010-08-31 14:03:53
date last changed
2016-06-29 09:17:19
@inproceedings{1d13b8d1-0eb6-4179-af46-6faf70081dcd,
  abstract     = {The pebble game on AND/OR dags which is natural generalization of a well known pebble game on dags is considered. The following problem is given: if k pebbles are enough to place a pebble on a given vertex of an AND/OR dag. It is shown that the problem is log-space complete for languages accepted in polynomial space.},
  author       = {Lingas, Andrzej},
  booktitle    = {Automata, Languages and Programming /Lecture notes in computer science},
  isbn         = {3-540-08860-1},
  keyword      = {pebble game,AND/OR graph,computational complexity,completeness in polynomial space,PSPACE,dag},
  language     = {eng},
  pages        = {300--300},
  publisher    = {Springer},
  title        = {A PSPACE complete problem related to a pebble game},
  url          = {http://dx.doi.org/10.1007/3-540-08860-1_22},
  volume       = {62},
  year         = {1978},
}