Efficient Analysis of VASS Termination Complexity

The termination complexity of a given VASS is a function L assigning to every 𝑛 the length of the longest nonterminating computation initiated in a configuration with all counters bounded by 𝑛. We show that for every VASS with demonic nondeterminism and every fixed 𝑘, the problem whether L ∈ G 𝑘 , where G 𝑘 is the 𝑘-th level in the Grzegorczyk hierarchy, is decidable in polynomial time. Furthermore, we show that if L ∉ G 𝑘 , then L grows at least as fast as the generator 𝐹 𝑘+1 of G 𝑘+1 . Hence, for every terminating VASS, the growth of L can be reasonably characterized by the least

Furthermore, we consider VASS with both angelic and demonic nondeterminism, i.e., VASS games where the players aim at lowering/raising the termination time. We prove that for every fixed 𝑘, the problem whether L ∈ G 𝑘 for a given VASS game is NP-complete. Furthermore, if L ∉ G 𝑘 , then L grows at least as fast as 𝐹 𝑘+1 .

• Theory of computation → Abstract machines.