The Associative Language Description model (ALD) is a combination of locally testable and constituent structure ideas. It is consistent with current views on brain organization and can rather conveniently describe typical technical languages such as Pascal or HTML. ALD languages are strictly enclosed in context-free languages but in practice the ALD model equals CF grammars in explanatory adequacy. Various properties of ALD have been investigated, but many theoretical questions are still open. For instance, it is unknown, at the present, whether the ALD family includes the regular languages. Here it is proved that several known classes of regular languages are ALD: threshold locally testable languages, group languages, positive commutative languages and commutative languages on 2-letter alphabet. Moreover, we show that there is an ALD language in each level of restricted star height hierarchy. These results seem to show that ALD languages are "well-distributed" over the class of regular languages.

Regular languages and associative language descriptions

CHERUBINI, ALESSANDRA;SAN PIETRO, PIERLUIGI
2007-01-01

Abstract

The Associative Language Description model (ALD) is a combination of locally testable and constituent structure ideas. It is consistent with current views on brain organization and can rather conveniently describe typical technical languages such as Pascal or HTML. ALD languages are strictly enclosed in context-free languages but in practice the ALD model equals CF grammars in explanatory adequacy. Various properties of ALD have been investigated, but many theoretical questions are still open. For instance, it is unknown, at the present, whether the ALD family includes the regular languages. Here it is proved that several known classes of regular languages are ALD: threshold locally testable languages, group languages, positive commutative languages and commutative languages on 2-letter alphabet. Moreover, we show that there is an ALD language in each level of restricted star height hierarchy. These results seem to show that ALD languages are "well-distributed" over the class of regular languages.
2007
INF
File in questo prodotto:
File Dimensione Formato  
ALD_reg.pdf

Accesso riservato

: Post-Print (DRAFT o Author’s Accepted Manuscript-AAM)
Dimensione 245.89 kB
Formato Adobe PDF
245.89 kB Adobe PDF   Visualizza/Apri

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/11311/551837
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact