= Bounded-difference automaton
{title2=$d\mapsto u^{-1}dv$}
For a fixed finite generating alphabet and integer $K$, use the elements of the word-metric ball $B_K(1)$ as states, together with a reject state and padding-status flags. Starting at the identity, a padded letter pair $(u,v)$ changes the state to $u^{-1}dv$ if it stays in the ball. A padding letter acts as the identity. Final state $a$ recognizes endpoint difference $a$ among pairs whose prefixes remain within $K$. On a regular synchronous <combing>, intersecting with the two word acceptors gives the full <group multiplier automaton>. It does not recognize unrestricted endpoint relations for all input words.
Back to article page
