Linear-time multiplication in an automatic structure
= Linear-time multiplication in an automatic structure
{title2=$|v|\leq|u|+N$}
Fix the first tape of a <group multiplier automaton> and use <dynamic programming> over automaton states and output-padding status, retaining predecessor pointers. The <pumping of a group multiplier automaton> bounds the search by $|u|+N$ layers, each of fixed size. This constructs a representative of $\overline u x$ in time $O(|u|+1)$ without assuming uniqueness of representatives.