= Solution
Part (a)(i), applied to $w=u$ and $g=\overline u x$, guarantees an accepted output of length at most $m+N$. Its <padded convolution of words> has at most $m+N$ columns. Thus the <dynamic programming> search in part (b) reaches an accepting layer by this bound.
Each layer has at most twice the fixed number of states of $M_x$, and each record has at most $|A|+1$ outgoing choices. These are constants for the fixed <automatic structure for a group>. Storing a pointer and a symbol takes constant time; copying whole partial output strings at every step would unnecessarily spoil this bound. Reconstruction also takes at most $m+N$ steps. Therefore \b[automatic multiplication has linear time and bounded length increase]:
$$
\boxed{|v|\leq |u|+N,\qquad T(u,x)=O(|u|+1).}
$$
For nonempty inputs this is the requested $O(|u|)$ <time complexity>. The additive $1$ merely includes the constant work on the <empty word>.
Back to article page
