PDT · Pushdown transduction
Polish notation to reverse Polish
Prefix to postfix: +x*xx becomes xxx*+. Each operator waits on the stack, remembering how many of its operands are complete; an x completes one, and an operator whose second operand completes is printed and itself counts as an operand for the one below. Łukasiewicz’s notation, turned round.
The author’s examples, run
x → accept · x+xx → accept · xx++x*xx → accept · xxx*+*+xxx → accept · xx+x*+*xx*xx → accept · xx*xx*++x → rejectxx → reject