Change search
ReferencesLink to record
Permanent link

Direct link
Scrabble is PSPACE-Complete
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2012 (English)Conference paper (Refereed)
Abstract [en]

In this paper we study the computational complexity of the game of Scrabble.We prove the PSPACE-completeness of a derandomized model of the game, answeringan open question of Erik Demaine and Robert Hearn.

Place, publisher, year, edition, pages
2012. Vol. abs/1201.5298, 258-269 p.
, Lecture Notes in Computer Science, ISSN 0302-9743 ; 7288
Keyword [en]
Scrabble, PSPACE-completeness, combinatorial games, computational complexity
National Category
Computer Science
URN: urn:nbn:se:kth:diva-112878DOI: 10.1007/978-3-642-30347-0_26ScopusID: 2-s2.0-84861994938OAI: diva2:587535
6th International Conference on Fun with Algorithms, FUN 2012; Venice; Italy

QC 20130502

Available from: 2013-01-14 Created: 2013-01-14 Last updated: 2013-09-30Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Lampis, Michael
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 28 hits
ReferencesLink to record
Permanent link

Direct link