论文标题
语言包含有限的效能矢量加法系统是可决定的
Language Inclusion for Boundedly-Ambiguous Vector Addition Systems is Decidable
论文作者
论文摘要
我们考虑了与状态（VAS）（VASS）的语言包容性和语言等效性的问题，其接受条件由一组接受状态定义（以及更普遍地是由某些向上关闭的条件）。通常，即使对于一维vass，语言等效性的问题也是不可决定的，因此为了获得可决定性，我们研究了受限的子类。一方面，我们证明了语言在K漫不经心的VASS中包含VASS的问题（对于任何天然K）都是可以决定的，甚至是Ackermann。另一方面，我们证明语言等效问题已经是确定性vass的Ackermann-Hard。这两个结果意味着在几个可能的限制中，对语言包容性和等效性的ackermann综合性。我们的某些技术也可以在无限国家系统中更广泛的一般性中应用，即用于某些结构良好的过渡系统的子类。
We consider the problems of language inclusion and language equivalence for Vector Addition Systems with States (VASS) 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 VASS, thus to get decidability we investigate restricted subclasses. On the 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 already Ackermann-hard for deterministic VASS. 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.
