New Frontiers Beyond Context-Freeness: Di-Grammars and Di-Automata.

NEW FRONTIERS BEYOND CONTEXT-FREENESS: DI-GRAMMARS AND DI-AUTOMATA. Peter Staudacher Institut for Allgemeine und Indogermanische Sprachwissenschaft Universitat Regensburg Postfach 397 8400 Regensburg 1 Germany Abstract A new class of formal languages will be defined the Distributed Index Languages (DI-lan- guages). The grammar-formalism generating the new class - the DI-grammars - cover unbound dependencies in a rather natural way. The place of DI-languages in the Chomsky-hierarchy will be determined: Like Aho's indexed Languages, DI-languages represent a proper subclass of Type 1 (contextsensitive languages) and prop- erly include Type 2 (context-free languages), but the DI-class is neither a subclass nor a super- class of Aho's indexed class. It will be shown that, apart from DI-grammars, DI-languages can equivalently be characterized by a special type of automata - DI-automata. Finally, the time com- plexity of the recognition-problem for an inter- esting subclass of DI-Grammars will approxi- mately be determined. I Introduction It is common practice to parse nested Wh-dependen- cies, like the classical example of Rizzi (1982) in (1), (1) Tuo fratello, [a cui]l mi domando [che storie]2 abbiano raccontato t 2 t 1, era molto preoccupato (Your Brother, [to whom] 1 I wonder [which sto- ries] 2 they told t 2 t 1 was very troubled) using a stack mechanism. Under the binary branching hypothesis the relevant structure of (1) augmented by wh-stacks is as follows: (2) [a cui] 1 mi dornando Lpush ---tit 11--~ i--push ---~[t2,tll--- 1 [che storie]2abbiano V2[t2,tl] / \ / vlIt21 PPItll \ V~I] NP.It2I pop IP°P ] raccontato t 2 t 1 Up to now it is unclear, how far beyond context- freeness the generative power of a Type 2 grammar formalism is being extended if such a stack mechanism is grafted on it (assuming, of course, that an upper bound for the size of the stack can not be motivated). Fernando Pereira's concept of Extraposition Gram- mar (XG), introduced in his influential paper (Pereira, 1981; 1983; cf. Stabler, 1987) in order to delimit the new territory, can be shown to be inadequate for this purpose, since it is provable that the class of languages generable by XGs coincides with Type 0 (i,e. XGs have the power of Turing machines), whereas the increase of power by the stack mechanism is not even enough to generate all Type 1 languages (see below). In (2) an additional point is illustrated: the stack [t2,tl] belonging to V 2 has to be divided into the substacks [t2] and [tl], which are then inherited by the daughters V l and PP. For the PP-index tlis not dis- charged from the top of the V2-stack [t2,tl]. Generaliz- ing to stacks of unlimited size, the partition of a stack among the inheriting subconstituents K 1 and K 2 of a constituent K 0 is as in (3) (3) / K0 It 1,...,tj,tj+l,...,tk] \ Klltl,...,tjl K2ltj+l,...,tkl 358 If the generalization in (3) is tenable, the extension of context-free grmnmars (Vijay-Shanker and Weir, 1991, call the resulting formalism "linear indexed granunar" (LIG)) discussed by Gazdar in (Gazdar, …

Content truncated to 500 words