A PSPACE complete problem related to a pebble game
(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:
http://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
- 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
@misc{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}, 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 = {ARRAY(0x8480898)}, series = {Automata, Languages and Programming /Lecture notes in computer science}, 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}, }