Abstract
The phenomenon of word order freedom plays an important role in syntactic analysis of many natural languages. This paper introduces a notion of a word order shift, an operation reflecting the degree of word order freedom of natural languages.
The word order shift is an operation based upon word order changes preserving syntactic correctness, individual word forms, their morphological characteristics, and their surface dependency relations in a course of a stepwise simplification of a sentence, a so called analysis by reduction. The paper provides linguistic motivation for this operation and concentrates on a formal description of the whole mechanism through a special class of automata, so called restarting automata with the shift operation enhanced with a structured output, and their computations.
The goal of this study is to clarify the properties of computations needed to perform (enhanced) analysis by reduction for free word order languages.