Regular languages and associative language descriptions

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 alphabets. 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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (2), pp.153--173
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00966526
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 26 mars 2014 - 17:01:29
Dernière modification le : mercredi 29 novembre 2017 - 10:26:22
Document(s) archivé(s) le : jeudi 26 juin 2014 - 12:01:13

Fichier

663-2380-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00966526, version 1

Collections

Citation

Marcella Anselmo, Alessandra Cherubini, Pierluigi San Pietro. Regular languages and associative language descriptions. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, 9 (2), pp.153--173. 〈hal-00966526〉

Partager

Métriques

Consultations de la notice

81

Téléchargements de fichiers

198