paperbot · PL 论文追踪

全部论文 待读 收藏

P2 On the Separability Problem of VASS Reachability Languages

VASS 可达语言的可分离性问题
LICS Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science2024匹配度 2/10 · 该论文是纯自动机与形式验证理论工作,研究 VASS 可达语言的可分离性与复杂度,未涉及 LLM/Agent、浮点程序分析、贝叶斯程序分析或 ML 系统静态分析,与用户画像的核心交叉方向基本无关。引用 8 inbox
Eren Keskin, Roland Meyer
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:证明 VASS 可达语言的正则可分离性可判定且为 Fω-完全,并引入双标记图转移序列分解算法。

本文研究向量加法系统(VASS)可达语言的正则可分离性问题:给定两个 VASS 可达语言,是否存在正则语言包含其中一个且与另一个不相交。作者证明该问题是可判定的,且其复杂度为 Fω-完全。核心工具是双标记图转移序列(DMGTS),一种跟踪待分离 VASS 的适当乘积的新证明对象。作者为 DMGTS 设计了分解算法,不仅达到已知 MGTS 的完美性,还满足新提出的忠实性。忠实性使得可以从 VASS 的 Z-版本正则分离器构造出 N-版本的正则分离器,其关键在于:为判定可分离性,只需跟踪一个 VASS 的计数器模一个由分解确定的大数。

问题
给定两个 VASS 可达语言,判定是否存在一个正则语言将它们分离。
方法
引入双标记图转移序列(DMGTS)来跟踪待分离 VASS 的乘积,并给出满足完美性与忠实性的分解算法,从而从 Z-版本正则分离器构造 N-版本正则分离器。
评估
通过理论证明确立正则可分离性问题的可判定性、Fω-完全性以及分解算法的正确性。
原文摘要(Abstract)

We show that the regular separability problem of VASS reachability languages is decidable and Fω-complete. At the heart of our decision procedure are doubly-marked graph transition sequences, a new proof object that tracks a suitable product of the VASS we wish to separate. We give a decomposition algorithm for DMGTS that not only achieves perfectness as known from MGTS, but also a new property called faithfulness. Faithfulness allows us to construct, from a regular separator for the Z-versions of the VASS, a regular separator for the N-versions. Behind faithfulness is the insight that, for separability, it is sufficient to track the counters of one VASS modulo a large number that is determined by the decomposition.

链接与引用

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

BibTeX
@inproceedings{abs-2401-16095,
  title = {On the Separability Problem of VASS Reachability Languages},
  author = {Eren Keskin and Roland Meyer},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662116}
}