HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download

Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Wednesday, March 26, 2014 - 5:01:29 PM
Last modification on : Thursday, June 10, 2021 - 12:41:09 PM
Long-term archiving on: : Thursday, June 26, 2014 - 12:01:13 PM


Files produced by the author(s)




Marcella Anselmo, Alessandra Cherubini, Pierluigi San Pietro. Regular languages and associative language descriptions. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2007, Vol. 9 no. 2 (2), pp.153--173. ⟨10.46298/dmtcs.406⟩. ⟨hal-00966526⟩



Record views


Files downloads