We consider the problems of language inclusion and language equivalence for Vector Addition Systems with States (VASSes) with the acceptance condition defined by the set of accepting states (and more generally by some upward-closed conditions). In general the problem of language equivalence is undecidable even for one-dimensional VASSes, thus to get decidability we investigate restricted subclasses. On one hand we show that the problem of language inclusion of a VASS in k-ambiguous VASS (for any natural k) is decidable and even in Ackermann. On the other hand we prove that the language equivalence problem is Ackermann-hard already for deterministic VASSes. These two results imply Ackermann-completeness for language inclusion and equivalence in several possible restrictions. Some of our techniques can be also applied in much broader generality in infinite-state systems, namely for some subclass of well-structured transition systems.
翻译:我们考虑了病媒添加系统与国家(VASS)的语言融合和语言等同问题,其接受条件由一套接受国(更一般地说,由某些上层封闭条件)界定。一般而言,语言等同问题即使对一维VASS来说也是不可分的,因此我们调查了受限制的亚类。一方面,我们表明,将VASS的语言融入k-模糊的VASS(对任何自然 k)是可分而治之,甚至在阿克曼(Ackermann)也是可分之。另一方面,我们证明,语言等同问题已经对确定性VASS(确定性VASS)来说是难以解决的。这两个结果表明,即使在可能的限制中,语言融合和等同方面,Ackermann(Ackermann)是无法分而成的。我们的一些技术也可以在无限状态系统中广泛应用,即一些结构完善的过渡系统。