# Indexed language

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Indexed_language
> Markdown URL: https://mediated.wiki/source/Indexed_language.md
> Source: https://en.wikipedia.org/wiki/Indexed_language
> Source revision: 1355042397
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Formal languages in computing}}
{{multiple issues|
{{too detailed|date=May 2026}}
{{more categories|date=May 2026}}
}}
'''Indexed languages''' are a class of [formal language](/source/formal_language)s discovered by [Alfred Aho](/source/Alfred_Aho);<ref name="aho1968">{{cite journal | last = Aho | author-link = Alfred Aho | first = Alfred | s2cid = 9539666 | year = 1968 | title = Indexed grammars—an extension of context-free grammars | journal = [Journal of the ACM](/source/Journal_of_the_ACM) | volume = 15 | issue = 4 | pages = 647–671 | doi = 10.1145/321479.321488 | doi-access = free }}</ref> they are described by [indexed grammar](/source/indexed_grammar)s and can be recognized by [nested stack automata](/source/nested_stack_automata).<ref name="partee_etal_1990">{{cite book |author-link=Barbara Partee |last1=Partee |first1=Barbara |first2= Alice |last2=ter Meulen|author2-link=Alice ter Meulen |first3=Robert E. |last3=Wall |title=Mathematical Methods in Linguistics |year=1990 |publisher=Kluwer Academic Publishers |pages=536–542 |isbn=978-90-277-2245-4 }}</ref>

Indexed languages are a [proper subset](/source/proper_subset) of [context-sensitive language](/source/context-sensitive_language)s.<ref name="aho1968"/> They qualify as an [abstract family of languages](/source/abstract_family_of_languages) (furthermore a full AFL) and hence satisfy many closure properties. However, they are not closed under intersection or complement.<ref name="aho1968" />

The class of indexed languages has {{citation needed span|practical importance in [natural language processing](/source/natural_language_processing) as a computationally affordable|date=August 2014}} generalization of [context-free languages](/source/context-free_languages), since [indexed grammar](/source/indexed_grammar)s can describe many of the nonlocal constraints occurring in natural languages.

[Gerald Gazdar](/source/Gerald_Gazdar) (1988)<ref name="gazdar1998">{{cite book |last1=Gazdar |first1=Gerald |chapter=Applicability of Indexed Grammars to Natural Languages |pages=69–94 |doi=10.1007/978-94-009-1337-0_3 |editor1-first=U. |editor1-last=Reyle |editor2-first=C. |editor2-last=Rohrer |title=Natural Language Parsing and Linguistic Theories |series=Studies in Linguistics and Philosophy |date=1988 |volume=35 |publisher=Springer Netherlands |isbn=978-94-009-1337-0 }}</ref>  and Vijayashanker (1987)<ref>{{cite thesis |last1=Vijayashanker |first1=K. |year=1987 |title=A study of tree adjoining grammars |id={{ProQuest|303610666}} }}</ref> introduced a [mildly context-sensitive language](/source/mildly_context-sensitive_language) class now known as linear indexed grammars (LIG).<ref name="Kallmeyer2010">{{cite book |first1=Laura |last1=Kallmeyer |title=Parsing Beyond Context-Free Grammars |url=https://books.google.com/books?id=F5wC0dko1L4C&pg=PA31 |year=2010 |publisher=Springer |isbn=978-3-642-14846-0 |page=31 }}</ref> Linear indexed grammars have additional restrictions relative to indexed grammars. LIGs are [weakly equivalent](/source/Equivalence_(formal_languages)) (generate the same language class) as [tree adjoining grammars](/source/tree_adjoining_grammars).<ref name="Kallmeyer2010b">{{cite book |first1=Laura |last1=Kallmeyer |title=Parsing Beyond Context-Free Grammars |url=https://books.google.com/books?id=F5wC0dko1L4C&pg=PA32 |date=16 August 2010 |publisher=Springer |isbn=978-3-642-14846-0 |page=32 }}</ref>

==Examples==

The following languages are indexed, but are not context-free:
:<math> \{a^n b^n c^n d^n| n \geq 1 \} </math> <ref name="gazdar1998"/>

:<math> \{a^n b^m c^n d^m | m,n \geq 0 \}</math> <ref name="partee_etal_1990"/>

These two languages are also indexed, but are not even mildly context sensitive under Gazdar's characterization:

:<math> \{a^{2^{n}} | n \geq 0 \}</math> <ref name="partee_etal_1990"/>

:<math> \{www | w \in \{a,b\}^+ \}</math> <ref name="gazdar1998"/>

On the other hand, the following language is not indexed:<ref name="Gilman.1996">{{cite journal| last = Gilman | first = Robert H. | s2cid = 14479068 | title=A Shrinking Lemma for Indexed Languages| journal=[Theoretical Computer Science](/source/Theoretical_Computer_Science_(journal))| year=1996| volume=163| issue = 1–2  | pages=277–281| doi = 10.1016/0304-3975(96)00244-7| arxiv=math/9509205}}</ref>
:<math>\{(a b^n)^n | n \geq 0 \}</math>

==Properties==

[Hopcroft](/source/John_Hopcroft) and [Ullman](/source/Jeffrey_Ullman) tend to consider indexed languages as a "natural" class, since they are generated by several formalisms, such as:{{#tag:ref|Introduction to automata theory, languages, and computation,<ref name="hopcroft_ullman_1979">{{cite book |author-link= John Hopcroft |last1=Hopcroft |first1=John |first2=Jeffrey |last2=Ullman |author2link=Jeffrey Ullman |title=Introduction to automata theory, languages, and computation |year=1979 |publisher=Addison-Wesley |isbn=978-0-201-02988-8 |url=https://archive.org/details/introductiontoau00hopc/page/390 |page=390 }}</ref> Bibliographic notes, p.394-395}}
* Aho's [indexed grammar](/source/indexed_grammar)s<ref name="aho1968"/>
* Aho's one-way [nested stack automata](/source/nested_stack_automata)<ref>{{cite journal |last1=Aho |first1=Alfred V. |s2cid=685569 |title=Nested Stack Automata |journal=Journal of the ACM |date=July 1969 |volume=16 |issue=3 |pages=383–406 |doi=10.1145/321526.321529 |doi-access=free }}</ref>
* [Fischer](/source/Michael_J._Fischer)'s macro grammars<ref>{{cite conference |last1=Fischer |first1=Michael J. |title=9th Annual Symposium on Switching and Automata Theory (Swat 1968) |chapter=Grammars with macro-like productions  |date=October 1968 |pages=131–142 |doi=10.1109/SWAT.1968.12 }}</ref>
* [Greibach](/source/Sheila_Greibach)'s automata with stacks of stacks<ref>{{cite journal |last1=Greibach |first1=Sheila A. |title=Full AFLs and nested iterated substitution |journal=[Information and Control](/source/Information_and_Control) |date=March 1970 |volume=16 |issue=1 |pages=7–35 |doi=10.1016/s0019-9958(70)80039-0 |doi-access= }}</ref>
* [Maibaum](/source/Tom_Maibaum)'s algebraic characterization<ref>{{cite journal |last1=Maibaum |first1=T.S.E. |title=A generalized approach to formal languages |journal=[Journal of Computer and System Sciences](/source/Journal_of_Computer_and_System_Sciences) |date=June 1974 |volume=8 |issue=3 |pages=409–439 |doi=10.1016/s0022-0000(74)80031-0 |doi-access=free }}</ref>

Hayashi<ref>{{cite journal |last1=Hayashi |first1=Takeshi |title=On derivation trees of indexed grammars: an extension of the {$uvwxy$}-theorem |journal=Publications of the Research Institute for Mathematical Sciences |date=1973 |volume=9 |issue=1 |pages=61–92 |doi=10.2977/prims/1195192738 |doi-access=free }}</ref> generalized the [pumping lemma](/source/Pumping_lemma_for_context-free_languages) to indexed grammars.
Conversely, Gilman<ref name="Gilman.1996"/> gives a "shrinking lemma" for indexed languages.

==See also==
* [Chomsky hierarchy](/source/Chomsky_hierarchy)

==References==

{{Reflist}}

==External links==
* [https://web.archive.org/web/20070311042935/http://www.cogs.susx.ac.uk/research/nlp/gazdar/nlp-in-prolog/ch04/chapter-04-sh-1.6.3.html#sh-1.6.3 "NLP in Prolog" chapter on indexed grammars and languages]

{{Formal languages and grammars}}

{{DEFAULTSORT:Indexed Language}}
Category:Formal languages
Category:Computational linguistics

---
Adapted from the Wikipedia article [Indexed language](https://en.wikipedia.org/wiki/Indexed_language) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Indexed_language?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.