On Finite-Index Indexed Grammars and Their Restrictions
01 Pubblicazione su rivista
D'Alessandro Flavio, Ibarra Oscar, Mcquillan Ian
ISSN: 0890-5401
The family, L(INDLIN), of languages generated by linear indexed grammars has been studied in the literature. It is known that the Parikh image of every language in L(INDLIN) is semi-linear. However, there are bounded semi-linear languages that are not in L(INDLIN). Here, we look at larger families of (restricted) indexed languages and study their combinatorial and decidability properties, and their relationships.