Indexed language: Difference between revisions

Content deleted Content added

Inline

Revision as of 14:20, 2 August 2020

Indexed languages are a class of formal languages discovered by Alfred Aho;^[1] they are described by indexed grammars and can be recognized by nested stack automata.^[2]

Indexed languages are a proper subset of context-sensitive languages.^[1] They qualify as an abstract family of languages (furthermore a full AFL) and hence satisfy many closure properties. However, they are not closed under intersection or complement.^[1]

The class of indexed languages has practical importance in natural language processing as a computationally affordable^{[citation needed]} generalization of context-free languages, since indexed grammars can describe many of the nonlocal constraints occurring in natural languages.

Gerald Gazdar (1988)^[3] and Vijay-Shanker (1987)^[4] introduced a mildly context-sensitive language class now known as linear indexed grammars (LIG).^[5] Linear indexed grammars have additional restrictions relative to IG. LIGs are weakly equivalent (generate the same language class) as tree adjoining grammars.^[6]

Examples

The following languages are indexed, but are not context-free:

\{a^{n}b^{n}c^{n}d^{n}|n\geq 1\}

^[3]

\{a^{n}b^{m}c^{n}d^{m}|m,n\geq 0\}

^[2]

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

\{a^{2^{n}}|n\geq 0\}

^[2]

\{www|w\in \{a,b\}^{+}\}

^[3]

On the other hand, the following language is not indexed:^[7]

\{(ab^{n})^{n}|n\geq 0\}

Properties

Hopcroft and Ullman tend to consider indexed languages as a "natural" class, since they are generated by several formalisms, such as:^[9]

Aho's indexed grammars^[1]
Aho's one-way nested stack automata^[10]
Fischer's macro grammars^[11]
Greibach's automata with stacks of stacks^[12]
Maibaum's algebraic characterization^[13]

Hayashi^[14] generalized the pumping lemma to indexed grammars. Conversely, Gilman^[7] gives a "shrinking lemma" for indexed languages.

References

^ ^a ^b ^c ^d Aho, Alfred (1968). "Indexed grammars—an extension of context-free grammars". Journal of the ACM. 15 (4): 647–671. doi:10.1145/321479.321488. S2CID 9539666.
^ ^a ^b ^c Partee, Barbara; ter Meulen, Alice; Wall, Robert E. (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. pp. 536–542. ISBN 978-90-277-2245-4.
^ ^a ^b ^c Gazdar, Gerald (1988). "Applicability of Indexed Grammars to Natural Languages". In Reyle, U.; Rohrer, C. (eds.). Natural Language Parsing and Linguistic Theories. Springer Netherlands. pp. 69–94. doi:10.1007/978-94-009-1337-0_3. ISBN 978-94-009-1337-0.
^ Vijayashanker, K. (1987). A study of tree adjoining grammars (Thesis). ProQuest 303610666.
^ Kallmeyer, Laura (2010). Parsing Beyond Context-Free Grammars. Springer. p. 31. ISBN 978-3-642-14846-0.
^ Kallmeyer, Laura (16 August 2010). Parsing Beyond Context-Free Grammars. Springer. p. 32. ISBN 978-3-642-14846-0.
^ ^a ^b Gilman, Robert H. (1996). "A Shrinking Lemma for Indexed Languages". Theoretical Computer Science. 163 (1–2): 277–281. arXiv:math/9509205. doi:10.1016/0304-3975(96)00244-7. S2CID 14479068.
^ Hopcroft, John; Ullman, Jeffrey (1979). Introduction to automata theory, languages, and computation. Addison-Wesley. p. 390. ISBN 978-0-201-02988-8.
^ Introduction to automata theory, languages, and computation,^[8] Bibliographic notes, p.394-395
^ Aho, Alfred V. (July 1969). "Nested Stack Automata". Journal of the ACM. 16 (3): 383–406. doi:10.1145/321526.321529.
^ Fischer, Michael J. (October 1968). Grammars with macro-like productions. 9th Annual Symposium on Switching and Automata Theory (swat 1968). pp. 131–142. doi:10.1109/SWAT.1968.12.
^ Greibach, Sheila A. (March 1970). "Full AFLs and nested iterated substitution". Information and Control. 16 (1): 7–35. doi:10.1016/s0019-9958(70)80039-0.
^ Maibaum, T.S.E. (June 1974). "A generalized approach to formal languages". Journal of Computer and System Sciences. 8 (3): 409–439. doi:10.1016/s0022-0000(74)80031-0.
^ Hayashi, Takeshi (1973). "On derivation trees of indexed grammars: an extension of the {$uvwxy$}-theorem". Publications of the Research Institute for Mathematical Sciences. 9 (1): 61–92. doi:10.2977/prims/1195192738.

External links

"NLP in Prolog" chapter on indexed grammars and languages

[aho1968-1] Aho, Alfred (1968). "Indexed grammars—an extension of context-free grammars". Journal of the ACM. 15 (4): 647–671. doi:10.1145/321479.321488. S2CID 9539666.

[partee_etal_1990-2] Partee, Barbara; ter Meulen, Alice; Wall, Robert E. (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. pp. 536–542. ISBN 978-90-277-2245-4.

[gazdar1998-3] Gazdar, Gerald (1988). "Applicability of Indexed Grammars to Natural Languages". In Reyle, U.; Rohrer, C. (eds.). Natural Language Parsing and Linguistic Theories. Springer Netherlands. pp. 69–94. doi:10.1007/978-94-009-1337-0_3. ISBN 978-94-009-1337-0.

[4] Vijayashanker, K. (1987). A study of tree adjoining grammars (Thesis). ProQuest 303610666.

[Kallmeyer2010-5] Kallmeyer, Laura (2010). Parsing Beyond Context-Free Grammars. Springer. p. 31. ISBN 978-3-642-14846-0.

[Kallmeyer2010b-6] Kallmeyer, Laura (16 August 2010). Parsing Beyond Context-Free Grammars. Springer. p. 32. ISBN 978-3-642-14846-0.

[Gilman.1996-7] Gilman, Robert H. (1996). "A Shrinking Lemma for Indexed Languages". Theoretical Computer Science. 163 (1–2): 277–281. arXiv:math/9509205. doi:10.1016/0304-3975(96)00244-7. S2CID 14479068.

[hopcroft_ullman_1979-8] Hopcroft, John; Ullman, Jeffrey (1979). Introduction to automata theory, languages, and computation. Addison-Wesley. p. 390. ISBN 978-0-201-02988-8.

[9] Introduction to automata theory, languages, and computation,^[8] Bibliographic notes, p.394-395

[10] Aho, Alfred V. (July 1969). "Nested Stack Automata". Journal of the ACM. 16 (3): 383–406. doi:10.1145/321526.321529.

[11] Fischer, Michael J. (October 1968). Grammars with macro-like productions. 9th Annual Symposium on Switching and Automata Theory (swat 1968). pp. 131–142. doi:10.1109/SWAT.1968.12.

[12] Greibach, Sheila A. (March 1970). "Full AFLs and nested iterated substitution". Information and Control. 16 (1): 7–35. doi:10.1016/s0019-9958(70)80039-0.

[13] Maibaum, T.S.E. (June 1974). "A generalized approach to formal languages". Journal of Computer and System Sciences. 8 (3): 409–439. doi:10.1016/s0022-0000(74)80031-0.

[14] Hayashi, Takeshi (1973). "On derivation trees of indexed grammars: an extension of the {$uvwxy$}-theorem". Publications of the Research Institute for Mathematical Sciences. 9 (1): 61–92. doi:10.2977/prims/1195192738.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[9]

[10]

[11]

[12]

[13]

[14]

[8]

@@ Line 1: / Line 1: @@
-'''Indexed languages''' are a class of [[formal language]]s discovered by [[Alfred Aho]];<ref name="aho1968">{{cite journal | last = [[Alfred Aho|Aho]] | first = Alfred | s2cid = 9539666 | year = 1968 | title = Indexed grammars—an extension of context-free grammars | journal = [[Journal of the ACM]] | volume = 15 | issue = 4 | pages = 647–671 | doi = 10.1145/321479.321488 }}</ref> they are described by [[indexed grammar]]s and can be recognized by [[nested stack automata]].<ref name="partee_etal_1990">{{cite book |authorlink=Barbara Partee| last = Partee | first = Barbara | author2 = Alice ter Meulen|author3= Robert E. 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 class of [[formal language]]s discovered by [[Alfred Aho]];<ref name="aho1968">{{cite journal | last = [[Alfred Aho|Aho]] | first = Alfred | s2cid = 9539666 | year = 1968 | title = Indexed grammars—an extension of context-free grammars | journal = [[Journal of the ACM]] | volume = 15 | issue = 4 | pages = 647–671 | doi = 10.1145/321479.321488 }}</ref> they are described by [[indexed grammar]]s and can be recognized by [[nested stack automata]].<ref name="partee_etal_1990">{{cite book |authorlink=Barbara Partee |last1=Partee |first1=Barbara |first2= Alice |last2=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]] of [[context-sensitive language]]s.<ref name="aho1968"/> They qualify as an [[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" />
@@ Line 5: / Line 5: @@
 The class of indexed languages has {{cnspan|practical importance in [[natural language processing]] as a computationally affordable|date=August 2014}} generalization of [[context-free languages]], since [[indexed grammar]]s can describe many of the nonlocal constraints occurring in natural languages.
-[[Gerald Gazdar]] (1988)<ref name="gazdar1998">{{cite book | chapter=Applicability of Indexed Grammars to Natural Languages | year=1988 | last=Gazdar | first=Gerald | title=Natural Language Parsing and Linguistic Theories | editor=U. Reyle and C. Rohrer | pages=69–94}}</ref>  and Vijay-Shanker (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]] class now known as linear indexed grammars (LIG).<ref name="Kallmeyer2010">{{cite book|author=Laura Kallmeyer|title=Parsing Beyond Context-Free Grammars|url=https://books.google.com/books?id=F5wC0dko1L4C&pg=PA31|year=2010|publisher=Springer Science & Business Media|isbn=978-3-642-14846-0|page=31}}</ref> Linear indexed grammars have additional restrictions relative to IG. LIGs are [[Equivalence (formal languages)|weakly equivalent]] (generate the same language class) as [[tree adjoining grammars]].<ref name="Kallmeyer2010b">{{cite book|author=Laura Kallmeyer|title=Parsing Beyond Context-Free Grammars|url=https://books.google.com/books?id=F5wC0dko1L4C&pg=PA32|date=16 August 2010|publisher=Springer Science & Business Media|isbn=978-3-642-14846-0|page=32}}</ref>
+[[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 |date=1988 |publisher=Springer Netherlands |isbn=978-94-009-1337-0 }}</ref>  and Vijay-Shanker (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]] 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 IG. LIGs are [[Equivalence (formal languages)|weakly equivalent]] (generate the same language class) as [[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==
@@ Line 25: / Line 25: @@
 ==Properties==
-[[John Hopcroft|Hopcroft]] and [[Jeffrey Ullman|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 | authorlink= John Hopcroft|last = Hopcroft | first = John | author2 = Jeffrey Ullman|author2link = Jeffrey Ullman | title = Introduction to automata theory, languages, and computation | year = 1979 | publisher = Addison-Wesley | isbn = 978-0-201-02988-8 | page = [https://archive.org/details/introductiontoau00hopc/page/390 390]|title-link = Introduction to automata theory, languages, and computation }}</ref> Bibliographic notes, p.394-395}}
+[[John Hopcroft|Hopcroft]] and [[Jeffrey Ullman|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 |authorlink= John Hopcroft |last=Hopcroft |first=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}}
 * [[Alfred Aho|Aho]]'s [[indexed grammar]]s<ref name="aho1968"/>
-* [[Alfred Aho|Aho]]'s one-way [[nested stack automata]]<ref>{{cite journal| author=Alfred Aho| s2cid=685569| title=Nested Stack Automata| journal=Journal of the ACM| year=1969| volume=16| number=3| pages=383–406| doi=10.1145/321526.321529}}</ref>
+* [[Alfred Aho|Aho]]'s one-way [[nested stack automata]]<ref>{{cite journal |last1=Aho |first1=Alfred V. |title=Nested Stack Automata |journal=Journal of the ACM |date=July 1969 |volume=16 |issue=3 |pages=383–406 |doi=10.1145/321526.321529 }}</ref>
-* [[Michael J. Fischer|Fischer]]'s macro grammars<ref>{{cite book| author=Michael J. Fischer| chapter=Grammars with Macro-Like Productions| title=Proc. 9th Ann. IEEE Symp. on Switching and Automata Theory (SWAT)| year=1968| pages=131–142}}</ref>
+* [[Michael J. Fischer|Fischer]]'s macro grammars<ref>{{cite conference |last1=Fischer |first1=Michael J. |title=Grammars with macro-like productions |conference=9th Annual Symposium on Switching and Automata Theory (swat 1968) |date=October 1968 |pages=131–142 |doi=10.1109/SWAT.1968.12 }}</ref>
-* [[Sheila Greibach|Greibach]]'s automata with stacks of stacks<ref>{{cite journal| author=Sheila A. Greibach| title=Full AFL's and Nested Iterated Substitution| journal=Information and Control| year=1970| volume=16| number=1| pages=7–35| doi=10.1016/s0019-9958(70)80039-0| doi-access=free}}</ref>
+* [[Sheila Greibach|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 |date=March 1970 |volume=16 |issue=1 |pages=7–35 |doi=10.1016/s0019-9958(70)80039-0 |doi-access=free }}</ref>
-* [[Tom Maibaum|Maibaum]]'s algebraic characterization<ref>{{cite journal| author=T.S.E. Maibaum| title=A Generalized Approach to Formal Languages| journal=Journal of Computer and System Sciences| year=1974| volume=8| number=3| pages=409–439| doi=10.1016/s0022-0000(74)80031-0}}</ref>
+* [[Tom Maibaum|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 |date=June 1974 |volume=8 |issue=3 |pages=409–439 |doi=10.1016/s0022-0000(74)80031-0 }}</ref>
-Hayashi<ref>{{cite journal| author=T. Hayashi| title= On derivation trees of indexed grammars: An extension of the ''uvwxy''-theorem| journal= Publications of the Research Institute for Mathematical Sciences| year=1973| volume=9| number=1| pages=61–92 | url=http://www.ems-ph.org/journals/show_pdf.php?issn=0034-5318&vol=9&iss=1&rank=3| doi=10.2977/prims/1195192738| doi-access=free}}</ref> generalized the [[Pumping lemma for context-free languages|pumping lemma]] to indexed grammars.
+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 for context-free languages|pumping lemma]] to indexed grammars.
-Conversely, Gilman<ref name="Gilman.1996"/><ref>{{cite arxiv| author=Robert H. Gilman| title=A Shrinking Lemma for Indexed Languages|date=Sep 1995| eprint=math/9509205}}</ref> gives a "shrinking lemma" for indexed languages.
+Conversely, Gilman<ref name="Gilman.1996"/> gives a "shrinking lemma" for indexed languages.
 ==See also==