## Indexed grammars?

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

Darcey
Posts: 188
Joined: Sun May 13, 2007 9:47 pm UTC
Location: Rochester, NY
Contact:

### Indexed grammars?

Hello,

I'm a CS undergrad. While googling random topics last night, I came across Indexed Grammars, a formalism somewhere in between context sensitive grammars and context free grammars on the Chomsky hierarchy. The idea behind Indexed Grammars is that nonterminals pass stacks of stuff to other nonterminals and basically carry the context along with them. That's not a good explanation, but oh well.

Anyway there is a surprising dearth of information on these things online. I've found some academic papers, but as I really don't feel like reading twelve different academic papers on different kinds of Indexed Grammars and their parsing algorithms this evening, I was wondering if anyone could refer me to a comprehensive overview of Indexed Grammar formalisms, their parsing algorithms, and if at all possible a probabilistic extension of Indexed Grammars and a machine learning algorithm for them (not sure if those things exist). It sounds from what I've read so far that Indexed Grammars are too powerful for efficient parsing, but that there are restrictions on the formalism that allows polynomial parsing algorithms.

Thanks!
-Darcey

Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: Indexed grammars?

Spoiler:
Neat. I'm looking at the wikipedia article -- am I right in saying that the example has an error?

T[sigma g] -> T[sigma] a | T[sigma] b
T[sigma g] -> T[sigma] b
?

---

One way grammars are understood is finding their equivalence in the computational complexity hierarchy. That throw-away sentence in the wikipedia article -- that recognizing such grammars is NP-complete -- could be illuminating. First, it tells you that the answer to "what kind of parsing algorithms there are" is "nothing better than 'trying every guess' in the worst case", as we don't have solutions for NP that run faster than EXPTIME.

Naively, I'd guess that a probabilistic Indexed grammar would behave similarly to one of the probabilistic complexity class formalisms. See if you can find language classes whose recognition problem corresponds to the various probability complexity classes?

I assumed you also looked up the equivalent language-sets listed in the Wikipedia article?

---

Sorry if this is less than completely illuminating.

Sorry.

http://www.cs.st-andrews.ac.uk/~mjn/pub ... /1998e.pdf

That is someone applying probabilistic models to linear indexed grammars (a p-time restricted indexed grammar) for machine learning.

Here is a later paper:
http://staff.science.uva.nl/~rens/analogy.pdf

I'm assuming that is the kind of stuff you where talking about?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.