A PSPACE complete problem related to a pebble game
(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:
https://lup.lub.lu.se/record/1664650
- author
- Lingas, Andrzej LU
- publishing date
- 1978
- 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
- 2021-01-03 03:48:28
@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}}, }