paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Regular Separability of One Counter Automata

单计数器自动机的正则可分离性
LMCS vol.Volume 15, Issue 22019匹配度 1/10 · 该论文属于纯自动机理论与形式语言，研究单计数器自动机的正则可分离性，未涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析，与用户当前研究方向基本无关；仅在形式化方法层面有非常远的邻近性。引用 0 inbox
Wojciech Czerwiński, Sławomir Lasota
逻辑与自动机
crossref: 2026-09-10

AI 速览

一句话：证明无零测试单计数器自动机的正则可分离性可判定且 PSpace 完全，并证明带零测试时不可判定。

本文研究正则可分离性问题：给定两个语言，是否存在一个正则语言包含其中一个且与另一个不相交。主要结果是，对于无零测试的单计数器自动机（又称单计数器网），该问题是可判定的，并且是 PSpace 完全的。这一结果形成鲜明对比：单计数器网的正则性问题不可判定，而带零测试的单计数器自动机的正则可分离性问题也不可判定，后者是本文的第二个结果。论文由此刻画了零测试能力对可分离性判定边界的根本影响。

问题
给定两个语言，判定是否存在一个正则语言包含其中一个且与另一个不相交；本文聚焦单计数器自动机（网）这一语言类的正则可分离性。
方法
摘要未展开具体技术证明；工作通过自动机与形式语言的可判定性及复杂度分析，分别处理无零测试与带零测试的单计数器自动机。
评估
以可判定性与 PSpace 完全性作为主要理论结果，并与单计数器网正则性不可判定、带零测试单计数器自动机正则可分离性不可判定作对比。
原文摘要（Abstract）

The regular separability problem asks, for two given languages, if there exists a regular language including one of them but disjoint from the other. Our main result is decidability, and PSpace-completeness, of the regular separability problem for languages of one counter automata without zero tests (also known as one counter nets). This contrasts with undecidability of the regularity problem for one counter nets, and with undecidability of the regular separability problem for one counter automata, which is our second result.

链接与引用

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

BibTeX 
@article{paperbot786,
  title = {Regular Separability of One Counter Automata},
  author = {Wojciech Czerwiński and Sławomir Lasota},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 15, Issue 2},
  year = {2019},
  doi = {10.23638/lmcs-15(2:20)2019}
}