Regular Languages and Associative Language Descriptions
Marcella Anselmo, Alessandra Cherubini, Pierluigi San Pietro
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.
Full Text: PDF PostScript