Extending Linear Indexed Grammars
- This paper presents a possibility to extend the formalism of linear indexed grammars. The extension is based on the use of tuples of pushdowns instead of one pushdown to store indices during a derivation. If a restriction on the accessibility of the pushdowns is used, it can be shown that the resulting formalisms give rise to a hierarchy of languages that is equivalent with a hierarchy defined by Weir. For this equivalence, that was already known for a slightly different formalism, this paper gives a new proof. Since all languages of Weir's hierarchy are known to be mildly context sensitive, the proposed extensions of LIGs become comparable with extensions of tree adjoining grammars and head grammars.
| Author: | Christian WartenaORCiDGND |
|---|---|
| URN: | urn:nbn:de:bsz:960-opus4-20789 |
| URL: | https://aclanthology.org/W00-2029.pdf |
| DOI: | https://doi.org/10.25968/opus-2078 |
| Parent Title (English): | Proceedings of the Fifth International Workshop on Tree Adjoining Grammar and Related Frameworks (TAG+5) |
| Publisher: | Association for Computational Linguistics |
| Document Type: | Conference Proceeding |
| Language: | English |
| Year of Completion: | 2000 |
| Publishing Institution: | Hochschule Hannover |
| Release Date: | 2021/09/22 |
| Tag: | LIG; Linear Indexed Grammars |
| First Page: | 207 |
| Last Page: | 214 |
| Link to catalogue: | 1777320518 |
| Institutes: | Fakultät III - Medien, Information und Design |
| DDC classes: | 004 Informatik |
| 410 Linguistik | |
| Licence (English): |  Creative Commons - Namensnennung-Nicht-kommerziell-Weitergabe unter gleichen Bedingungen 3.0 International |
