一句话:研究 Dyck 词上擦除配对括号的一人游戏,并以“宽度”衡量策略代价。
论文研究一个作用于良构括号序列(Dyck 词)的单人擦除游戏:玩家每步可选择任一左括号与位于其右侧的任一右括号配对,并将这一对括号删除;目标是通过一系列合法配对最终删除整个序列。策略的代价用宽度衡量,即在游戏进行过程中,被空白隔开的非空符号段的最大数量。该模型把括号匹配、序列重配对与博弈/形式语言中的资源度量联系起来。摘要仅给出游戏定义与代价度量,未在给定文本中报告具体的复杂度分类、最优策略或上下界结果。
Consider the following one-player game. Take a well-formed sequence of opening and closing brackets (a Dyck word). As a move, the player can pair any opening bracket with any closing bracket to its right, erasing them. The goal is to re-pair (erase) the entire sequence, and the cost of a strategy is measured by its width: the maximum number of nonempty segments of symbols (separated by blank space) seen during the play.