一句话：证明了无零测试单计数器自动机语言的正则可分离性可判定且为 PSPACE 完全。
正则可分离性问题询问：给定两个语言，是否存在一个正则语言包含其中之一且与另一个不相交。本文研究单计数器自动机语言的正则可分离性。主要结果表明，对于不带零测试的单计数器自动机（又称单计数器网），该问题是可判定的，并且是 PSPACE 完全的。这一结果与单计数器网的正则性问题不可判定形成对比；同时，作者还证明了对于带零测试的一般单计数器自动机，正则可分离性是不可判定的。因此，论文在可判定性边界上给出了精确刻画。
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 原文 ·
@inproceedings{paperbot4159,
title = {Regular separability of one counter automata},
author = {Wojciech Czerwinski and Slawomir Lasota},
booktitle = {LICS},
year = {2017},
doi = {10.1109/lics.2017.8005079}
}