This paper is concerned with the relation between mild context-sensitivity
and the class of languages generated by Linear Context-Free Rewriting Systems
(LCFRSs). We show that there are languages that are polynomial and of constant
growth but that are not LCFRLs. Starting from this observation we define an extension
of LCFRS that, roughly allows for a limited amount of copying (or intersection
if considered in a bottom-up perspective) The proposed LCFRS extension Literal
Movement Grammars of constant non-linearity (CNL-LMG) is such that the parts
that are copied into different places during a derivation cannot increase when iterating
the non-linear parts of a derivation We show that this condition guarantees that the
string languages are still of constant growth As a consequence CNL-LMG is mildly
context-sensitive while properly extending LCFRS This result suggests that a limited
and controlled amount of copying and intersection can remain tractable since it does
not lead outside mild context-sensitivity Furthermore we show that there are natural
language phenomena (in particular gapping and scrambling) where such a limited possibility
of intersection gives the necessary expressive power beyond LCFRS to model
these phenomena.

EB00000002733K

Available

• On Mildly Context-Sensitive Non-Linear Rewriting