# Uniform _vs._ Nonuniform Membership for Mildly Context-Sensitive Languages: A Brief Survey
## 1 Introduction  
Context-free and context-sensitive grammars were introduced in the 1950s by [PERSON], as possible formalisms for describing the structure of natural languages; see, e.g., [1]. Context-free grammars (CFG for short), in particular, have been very successful, both when it comes to natural language modelling and, perhaps to an even larger degree, the description of the syntax of programming languages.  
During the sixty years since their introduction, it has become clear that context-free grammars, though immensely useful in many applications, also have certain limitations in their ability to formalize natural language grammar. As an example, they are unable to model the cross-serial dependencies that appear in some languages and that are archetypically captured by the copy language \(\mathcal{L}_{copy}\) over an alphabet \(\Sigma\) defined by  
\[\mathcal{L}_{copy}=\{ww\mid w\in\Sigma^{*}\}\]  
An example of this phenomenon in English is the construction used together with \"respectively\":  
_Cats, rabbits, dogs, and monkeys like fish, carrots, bones, and bananas, respectively._  
Context-sensitive grammars, on the other hand, are able to model these and many other natural language constructions that go beyond the context-free languages. The drawback of using them for natural language processing is the computational complexity of their associated decision problems. It is well known that the membership problems (and thus parsing) for context-sensitive languages are equivalent to the acceptance problems for linear-bounded nondeterministic Turing machines. The emptiness problem for context-sensitive grammars is undecidable; see, e.g., [2].  
For these reasons, [PERSON] suggested the concept of mildly context-sensitive languages in 1985. The idea was to capture the full richness of natural language syntax and still havea computationally tractable formalism. Mildly context-sensitive formalisms should extend the context-free languages to include relevant natural language features, while preserving constant growth and polynomial time parsing. [PERSON] himself suggested tree-adjoining grammars (TAGs) as a suitable formalism [3]. Other suggested formalisms, such as Linear Indexed Grammars (LIG), Combinatory Categorial Grammars (CCG), and Head Grammars (HG) have been shown to be expressively equivalent to TAGs [4]. (The equivalence holds for the CCG version used in [4], but not for all CCG definitions that are currently used; see, e.g., [5].)  
There were, however, still some linguistic constructions that TAGs could not fully model. (This has to do with the locality of dependencies in TAGSs; for details, see, e.g., [6].) This led to other formalisms being suggested during the late 1980s, notably multi-component TAGs [7], linear context-free rewriting systems (LCFRSs) [8], and the very similar multiple context-free grammars [9].  
Already in 1971, [PERSON] and [PERSON] had introduced deterministic tree-walking transducers (DTWTs). Their goal was to characterize transformations over context-free grammars [10]. It was later shown that these transducers produce the same class of output languages as a kind of context-free hypergraph grammar [11; 12]. In 1992, rather surprisingly, [PERSON] showed that they also produce the same class of languages as LCFRSs [13]. That put DTWTs in the running as a candidate formalism for representing mildly context-sensitive languages.