Tractability issues in extraposition grammar

Extraposition Grammar (XG) was introduced in [Per81] as a grammar formalism whose increase in recognizing power over context free grammars is limited to mechanisms for adequate description of structural phenomena occurring in natural language. This paper proposes versions of XG whose fixed recognition problems are in deterministic polynomial and exponential time; furthermore it is shown that the unrestricted XG defined in the original work [Per81] describe any recursively enumerable language.