Problem 1: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:
1
Whether this problem is decidable is also a question suggested by Piotrek Hofman