We are given an array $a$ of $n$ integers, such that the difference between each element $a[i]$ and the adjacent elements $a[i-1]$ and $a[i+1]$ is at most $1$. Define a root of $a$ as an index $k$ in $1,\ldots,n$ such that $a[k]=0$. If $a[1]<0$ and $a[n]>0$, then $a$ has at least one root. Moreov...

A multi-acceptance deterministic finite state automaton is a tuple $(Q,\Sigma,\delta,q_0,T,f)$ where $Q$, $\Sigma$, $\delta: Q \times \Sigma \to Q$, and $q_0 \in Q$ are defined in the standard way of DFAs; $T$ is a finite set of labels; $f: Q \to 2^L$ is a function that associates a set of label...