论文标题
分支机构结构的过渡系统和扩展
Branch-Well-Structured Transition Systems and Extensions
论文作者
论文摘要
我们对结构良好的过渡系统（\ wst）的定义提出了放松，同时保留了界限和非终止的可决定性。在此课程中，良好的序列（WQO）条件放松，使其仅适用于在彼此之间可以达到的状态之间。此外，单调条件以相同的方式放松。尽管这保留了非终止和有限性的可决定性，但看来覆盖性问题是不可决定的。为此，我们定义了一种新的单调概念，称为“封面单调”，它严格比通常的单调更一般，并且仍然允许我们决定可覆盖性问题的受限制形式。
We propose a relaxation to the definition of well-structured transition systems (\WSTS) while retaining the decidability of boundedness and non-termination. In this class, the well-quasi-ordered (wqo) condition is relaxed such that it is applicable only between states that are reachable one from another. Furthermore, the monotony condition is relaxed in the same way. While this retains the decidability of non-termination and boundedness, it appears that the coverability problem is undecidable. To this end, we define a new notion of monotony, called cover-monotony, which is strictly more general than the usual monotony and still allows us to decide a restricted form of the coverability problem.
