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.
On Finite-Index Indexed Grammars and Their Restrictions / D'Alessandro, Flavio; Ibarra, Oscar; Mcquillan, Ian. - In: INFORMATION AND COMPUTATION. - ISSN 0890-5401. - 279:(2021), pp. 1-13. [10.1016/j.ic.2020.104613]
On Finite-Index Indexed Grammars and Their Restrictions
d'alessandro, flavio
Primo
;
2021
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
D'Alessandro_preprint_On-finite-index_2020.pdf
accesso aperto
Note: preprint, versione preliminare alla
Tipologia:
Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza:
Creative commons
Dimensione
457.61 kB
Formato
Adobe PDF
|
457.61 kB | Adobe PDF | |
D'Alessandro_On-finite-index_2021.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
692.45 kB
Formato
Adobe PDF
|
692.45 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.