Abstract
The paper provides linguistic observations as a motivation for a formal study of analysis by reduction (AR). It concentrates on a study of the whole mechanism through a class of restarting automata with meta-instructions using pebbles, delete, and shift operations (DS-automata).
The complexity of DS-automata is naturally measured by the number of deletions, and the number of word order shifts used in a single meta-instruction. We study reduction languages, backward correctness preserving AR, correctness preserving AR, and show unbounded hierarchies (scales) for various classes of reduction languages by the same finite witness languages.
The scales make it possible to estimate relevant complexity issues of analysis by reduction for natural languages.