The reachability problem for 1-dimensional Pushdown Vector Addition Systems (1-PVASS) is a big open problem. Here I propose another problem, which seems much simpler, but hopefully can shed a light into reachability of 1-PVASS. Instead of 1-PVASS we consider 1-dimensional Grammar Vector Addition Systems, (1-GVASS) which are equivalent wrt. the reachability problem to 1-PVASS.
The problem is formulated as follows: we are given a context-free grammar G with terminals being integers and two natural numbers a, b. The question is whether there exists a witness word \(w \in Z^*\) such that:
- for each prefix v of w the expression (a + the sum of letters of v) is nonnegative;
- a + sum of letters of w = b.
For example consider a grammar G with two nonterminals X, Y with starting nonterminal being Y and the rules X → -1 X 2 | 0, Y → -1 Y X | 1. For a = 2 and b = 4 the word w = -1 -1 1 -1 2 -1 -1 2 2 is a witness.
I propose to consider thin 1-GVASS, for which for each rule X → \(\alpha\) there is at most one occurrence of a nonterminal \(Y \in \alpha\) such that X is derivable from X. The problem is known to be decidable for thin 1-GVASS, but the complexity is high.
I propose the following conjectures:
- for thin grammars with 2 nonterminals if there is a witness then there is a witness of length polynomial wrt. size of the grammar and numbers a, b;
- the same holds for any number of nonterminals;
- decidability of the problem for d nonterminals is below the complexity class \(F_d\).