You Should Be Scared of German Ghost

• Item type: Journal(1)
• 公開日: 2015-05-15
• タイトル: You Should Be Scared of German Ghost
• タイトル / 言語: en
• タイトル: You Should Be Scared of German Ghost
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [特集：娯楽の離散数理] algorithmic combinatorial game theory, mathematical games and puzzles, computational complexity
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: MIT Computer Science and Artificial Intelligence Laboratory
• 著者所属: MIT Computer Science and Artificial Intelligence Laboratory
• 著者所属: MIT Computer Science and Artificial Intelligence Laboratory
• 著者所属: MIT Computer Science and Artificial Intelligence Laboratory
• 著者所属(英): en
• 著者所属(英): MIT Computer Science and Artificial Intelligence Laboratory
• 著者所属(英): en
• 著者所属(英): MIT Computer Science and Artificial Intelligence Laboratory
• 著者所属(英): en
• 著者所属(英): MIT Computer Science and Artificial Intelligence Laboratory
• 著者所属(英): en
• 著者所属(英): MIT Computer Science and Artificial Intelligence Laboratory
• 著者名: ErikD., Demaine; Fermi, Ma; Matthew, Susskind; Erik, Waingarten
• 著者名(英): Erik, D.Demaine; Fermi, Ma; Matthew, Susskind; Erik, Waingarten
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Ghost is a popular word game played by two or more players. Players take turns adding a letter to the end of a growing word fragment, trying not to be the first to complete a valid word. We show that the game, when played on a regular language, is PSPACE-hard, and extend the result to four variants of the game. In addition, we take advantage of a quirk of the German language ― that German words can be concatenated together to form longer words ― to give a fun extension of our proof of PSPACE-hardness to subsets of the German language.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.23(2015) No.3 (online); DOI http://dx.doi.org/10.2197/ipsjjip.23.293; ------------------------------
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Ghost is a popular word game played by two or more players. Players take turns adding a letter to the end of a growing word fragment, trying not to be the first to complete a valid word. We show that the game, when played on a regular language, is PSPACE-hard, and extend the result to four variants of the game. In addition, we take advantage of a quirk of the German language ― that German words can be concatenated together to form longer words ― to give a fun extension of our proof of PSPACE-hardness to subsets of the German language.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.23(2015) No.3 (online); DOI http://dx.doi.org/10.2197/ipsjjip.23.293; ------------------------------
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 56, 号 5, 発行日 2015-05-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764