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.
2021
Indexed Languages; finite-index; full trios; semi-linearity; Bounded languages; ET0L languages
01 Pubblicazione su rivista::01a Articolo in rivista
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]
File allegati a questo prodotto
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1468546
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact