论文标题
矢量加法系统中常规可分离性的方法
An Approach to Regular Separability in Vector Addition Systems
论文作者
论文摘要
我们研究了使用状态（VASS）的矢量加法系统语言定期可分离性的问题。它询问是否存在两种给定的VASS语言K和L，存在一种常规语言R，其中包括K，并且与L相关。虽然问题的确定性是完全的问题，但仍有一个悬而未决的问题，但已显示了几个子类别：（I）vass coversability of vass cossingability composity：vass coverability cossingability commuttiate vass语言（iii vass）vass vass vass vass vast vast vast vast vast vast vast vast vast vast vist vers vers vers v。我们提出了一种确定常规可分离性的一般方法。我们使用它来确定（i），（ii）和（iii）类中任何语言的任意VASS语言的定期可分离性。这概括了所有先前的结果，包括（iv）。
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. We propose a general approach to deciding regular separability. We use it to decide regular separability of an arbitrary VASS language from any language in the classes (i), (ii), and (iii). This generalizes all previous results, including (iv).
