On the degree of scattered context-sensitivity
In this paper, we prove that every recursively enumerable language can be generated by a scattered context grammar with no more than two context-sensitive productions. (C) 2002 Elsevier Science B.V. All rights reserved.
scattered context grammars descriptional complexity