← All problems
Unverified
Variants of one-counter systems universality
Problem 1: 1 Given a 1-VASS, let be its language where acceptance is by reaching a final state from a fixed initial state and initial counter value . Does there exist such that ? Problem 2: Given a 1-VASS, let be the language of the -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 such that ? 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
