paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Re-pairing brackets

括号的重配对
LICS Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science2020匹配度 1/10 · 该论文研究 Dyck 词上的括号重配对游戏与策略宽度,属于形式语言/自动机与组合博弈的理论工作,未涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析等用户核心方向。引用 1 inbox
Dmitry Chistikov, Mikhail Vyalyi
crossref: 2026-09-12

AI 速览

一句话:研究 Dyck 词上擦除配对括号的一人游戏,并以“宽度”衡量策略代价。

论文研究一个作用于良构括号序列(Dyck 词)的单人擦除游戏:玩家每步可选择任一左括号与位于其右侧的任一右括号配对,并将这一对括号删除;目标是通过一系列合法配对最终删除整个序列。策略的代价用宽度衡量,即在游戏进行过程中,被空白隔开的非空符号段的最大数量。该模型把括号匹配、序列重配对与博弈/形式语言中的资源度量联系起来。摘要仅给出游戏定义与代价度量,未在给定文本中报告具体的复杂度分类、最优策略或上下界结果。

问题
在 Dyck 词上,玩家需通过反复配对并删除左括号和其右侧的右括号来清空序列;问题关注这种重配对过程及其策略的宽度代价。
方法
论文以单人组合博弈/形式语言模型来定义该重配对过程,并将策略优劣形式化为游戏过程中非空段的最大数量。
评估
评估基于理论分析;代价度量为宽度,而非实验或实现 benchmark。给定摘要未说明具体评估结果。
原文摘要(Abstract)

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.

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@inproceedings{paperbot5514,
  title = {Re-pairing brackets},
  author = {Dmitry Chistikov and Mikhail Vyalyi},
  booktitle = {LICS},
  year = {2020},
  doi = {10.1145/3373718.3394752}
}