Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

A PSPACE complete problem related to a pebble game

Lingas, Andrzej LU (1978) Automata, Languages and Programming Fifth Colloquium 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
host publication
Automata, Languages and Programming /Lecture notes in computer science
volume
62
pages
300 - 300
publisher
Springer
conference name
Automata, Languages and Programming Fifth Colloquium
conference location
Udine, Italy
conference dates
1978-07-17 - 1978-07-21
external identifiers
  • scopus:84918326078
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
2016-04-04 11:07:33
date last changed
2025-10-14 09:24:33
@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}},
  keywords     = {{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}},
  doi          = {{10.1007/3-540-08860-1_22}},
  volume       = {{62}},
  year         = {{1978}},
}