Does a given regular language over an alphabet of integer vectors contain a word such that
In this talk I will recall the status quo regarding the complexity of the reachability problem, mostly focussing on the subproblems for fixed and small dimensions.
I will present our recent result on the two-dimensional case that the length of shortest reachability certificates is polynomial in the largest integer and the size of the NFA defining the input language. This complements a result by Blondin et. al. (LICS'15) and shows that the 2-dim. reachability problem is PSPACE-complete when numbers are encoded in binary and NL-complete if the input is given in unary.