paperbot · PL 论文追踪

全部论文 待读 收藏

P2 An Approach to Regular Separability in Vector Addition Systems

向量加法系统（VASS）中正则可分离性的一种方法
LICS Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science2020匹配度 2/10 · 该论文属于 VASS 正则可分离性的纯自动机/形式语言理论研究，与用户关注的 LLM/Agent 静态分析、浮点程序分析、贝叶斯程序分析等核心方向没有直接交叉。虽涉及形式化验证/逻辑与自动机，但与用户画像中的问题意识和方法论匹配度很低。引用 4 inbox
Wojciech Czerwiński, Georg Zetzsche
逻辑与自动机
crossref: 2026-09-12

AI 速览

一句话：研究 VASS 语言的正则可分离性，并讨论一维、覆盖、整数与交换 VASS 等可判定子类。

论文研究带状态向量加法系统（VASS）语言的正则可分离性问题：给定两个 VASS 语言 K 和 L，判定是否存在一个正则语言 R，使得 K 包含于 R 且 R 与 L 不相交。该问题在一般情况下是否可判定仍是开放问题。已有结果仅覆盖若干子类，包括一维 VASS、VASS 覆盖语言、整数 VASS 语言以及交换 VASS 语言。论文围绕这一问题提出一种研究路径，并借助这些子类刻画可判定性边界。摘要主要说明问题背景与已知可判定情形，未展开具体技术细节或复杂度结果。

问题
判定两个 VASS 语言之间是否存在正则语言将二者分离，即是否存在正则 R 包含 K 且与 L 不相交。
方法
论文研究 VASS 语言正则可分离性问题，提出一种处理该问题的方法/路径；摘要未展开具体技术构造。
评估
以可判定性分析为主，梳理并讨论一维 VASS、VASS 覆盖语言、整数 VASS 与交换 VASS 等已知可判定子类。
原文摘要（Abstract）

We study the problem of regular separability of languages of vector addition systems with states (VASS). It asks whether for two given VASS languages K and L, there exists a regular language R that includes K and is disjoint from L. While decidability of the problem in full generality remains an open question, there are several subclasses for which decidability has been shown: It is decidable for (i) one-dimensional VASS, (ii) VASS coverability languages, (iii) languages of integer VASS, and (iv) commutative VASS languages.

链接与引用

DOI 原文 · PDF（开放获取） ·

BibTeX 
@inproceedings{paperbot5549,
  title = {An Approach to Regular Separability in Vector Addition Systems},
  author = {Wojciech Czerwiński and Georg Zetzsche},
  booktitle = {LICS},
  year = {2020},
  doi = {10.1145/3373718.3394776}
}