Geodesic
Regular languages and associative language descriptions
Discrete mathematics & theoretical computer science, Tome 9 (2007) no. 2.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2007_9_2_a11,
     author = {Anselmo, Marcella and Cherubini, Alessandra and San Pietro, Pierluigi},
     title = {Regular languages and associative language descriptions},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {9},
     number = {2},
     year = {2007},
     doi = {10.46298/dmtcs.406},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.406/}
}
TY  - JOUR
AU  - Anselmo, Marcella
AU  - Cherubini, Alessandra
AU  - San Pietro, Pierluigi
TI  - Regular languages and associative language descriptions
JO  - Discrete mathematics & theoretical computer science
PY  - 2007
VL  - 9
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.406/
DO  - 10.46298/dmtcs.406
LA  - en
ID  - DMTCS_2007_9_2_a11
ER  - 
%0 Journal Article
%A Anselmo, Marcella
%A Cherubini, Alessandra
%A San Pietro, Pierluigi
%T Regular languages and associative language descriptions
%J Discrete mathematics & theoretical computer science
%D 2007
%V 9
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.406/
%R 10.46298/dmtcs.406
%G en
%F DMTCS_2007_9_2_a11
Anselmo, Marcella; Cherubini, Alessandra; San Pietro, Pierluigi. Regular languages and associative language descriptions. Discrete mathematics & theoretical computer science, Tome 9 (2007) no. 2. doi : 10.46298/dmtcs.406. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.406/

Cité par Sources :