19.10 Variants of one-counter systems universality

Problem 1:¹ Given a 1-VASS, let \(L_n\) be its language where acceptance is by reaching a final state from a fixed initial state and initial counter value \(n\). Does there exist \(n\) such that \(\Sigma^* = L_n\) ?

Problem 2: Given a 1-VASS, let \(L^n\) be the language of the $n$-bounded system (the NFA where values 0..n are hard-coded) where acceptance is by reaching a final state from a fixed initial configuration. Does there exist \(n\) such that \(\Sigma^* \subseteq L^n\)?

Questions:

• Are these problems decidable?
• Are they inter-reducible?
• What about trace languages?
• Is there a direct reduction from the seemingly simpler Universality Problem (fixed initial configuration) to either of these problems?

Footnotes:

¹

Whether this problem is decidable is also a question suggested by Piotrek Hofman