← All problems
Unverified

Variants of one-counter systems universality

Problem 1: 1 Given a 1-VASS, let LnL_n be its language where acceptance is by reaching a final state from a fixed initial state and initial counter value nn. Does there exist nn such that Σ∗=Ln\Sigma^* = L_n ? Problem 2: Given a 1-VASS, let LnL^n be the language of the nn-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 nn such that Σ∗⊆Ln\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

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu