Paper: New Frontiers Beyond Context-Freeness: Di-Grammars And Di-Automata

ACL ID E93-1042
Title New Frontiers Beyond Context-Freeness: Di-Grammars And Di-Automata
Venue Annual Meeting of The European Chapter of The Association of Computational Linguistics
Session Main Conference
Year 1993
Authors

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 b...