
doi: 10.46298/dmtcs.406
handle: 11386/1656118 , 11311/255529 , 11311/551837
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.
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], QA1-939, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], INF, Mathematics
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], QA1-939, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], INF, Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
