According to Noam Chomsky ``the main problem of immediate relevance to the theory of language is that of determining where in the hierarchy of devices the grammars of natural languages lie'' [Chomsky,1959]. This statement was given 40 years ago, but it is still up to date. Nowadays, linguists seem to agree that natural languages as well as artificial ones contain constructions which cannot be described by Context-Free Grammars (CFG). Three basic such features are [Dassow,Paun,Salomaa,1997]:
All these languages are well known as examples of non-context-free languages.
In the Chomsky hierarchy, beyond the context-free family,
there is the context-sensitive one. Linguists agree that this is large enough,
but they are also convinced that context-sensitive grammars are ``too much'', [Manaster-Ramer,1994].
The known algorithms for the membership problem have exponential time
complexity in the worst case.
Small extensions of context-free languages are therefore interesting for
natural language processing.
In [Joshi,Vijay-Shanker,Weir,1991] mildly-context-sensitive languages are characterized.
The term ``mild'' is used with a precise meaning:
semilinear and parsable in polynomial time. Tree-adjoining languages
are described as a representative of this class.
Tree-Adjoining Grammars (TAG), introduced in [Joshi,Levy,Takahashi,1975], and Coupled-Context-Free Grammars
(CCFG), introduced in [Hotz,1967] and analyzed in [Guan,1992] and [Pitsch,1993],
mainly influenced the development of the Recursive Matrix (Grammar) Systems.
Linear Context-Free Rewriting Systems (LCFRS) are
generalizations of tree-adjoining grammars.
LCFRS, introduced in [Vijay-Shanker,Weir,Joshi,1987], are primarily two-step systems.
In the first step an arbitrary kind of structure (e.g., a tree) is derived
by a general context-free grammar.
In the second step a yield function maps this structure to a string-word.
RMS, introduced in [Heckmann,1998] and
[Becker,Heckmann,1998], form a new class of
mildly-context-sensitive grammar formalisms. RMS are, like LCFRS, two-step systems.
In the first step a grammar generates so called recursive matrices.
In the second step these recursive matrices are mapped to strings.
A recursive matrix is a finite two-dimensional array whose elements are either terminal symbols or recursive matrices again. Figure 1.1 shows an example.
Figure 1.1: A Recursive Matrix