Regular Languages and Associative Language Descriptions
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 en...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2007-05-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Online Access: | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/663 |
| _version_ | 1818918574195998720 |
|---|---|
| author | Marcella Anselmo Alessandra Cherubini Pierluigi San Pietro |
| author_facet | Marcella Anselmo Alessandra Cherubini Pierluigi San Pietro |
| author_sort | Marcella Anselmo |
| collection | DOAJ |
| description | 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-distributedover the class of regular languages. |
| first_indexed | 2024-12-20T00:52:07Z |
| format | Article |
| id | doaj.art-f6d4f683b0a1405abdd06e23b153da7c |
| institution | Directory Open Access Journal |
| issn | 1462-7264 1365-8050 |
| language | English |
| last_indexed | 2024-12-20T00:52:07Z |
| publishDate | 2007-05-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-f6d4f683b0a1405abdd06e23b153da7c2022-12-21T19:59:13ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1462-72641365-80502007-05-0192Regular Languages and Associative Language DescriptionsMarcella AnselmoAlessandra CherubiniPierluigi San PietroThe 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-distributedover the class of regular languages.http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/663 |
| spellingShingle | Marcella Anselmo Alessandra Cherubini Pierluigi San Pietro Regular Languages and Associative Language Descriptions Discrete Mathematics & Theoretical Computer Science |
| title | Regular Languages and Associative Language Descriptions |
| title_full | Regular Languages and Associative Language Descriptions |
| title_fullStr | Regular Languages and Associative Language Descriptions |
| title_full_unstemmed | Regular Languages and Associative Language Descriptions |
| title_short | Regular Languages and Associative Language Descriptions |
| title_sort | regular languages and associative language descriptions |
| url | http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/663 |
| work_keys_str_mv | AT marcellaanselmo regularlanguagesandassociativelanguagedescriptions AT alessandracherubini regularlanguagesandassociativelanguagedescriptions AT pierluigisanpietro regularlanguagesandassociativelanguagedescriptions |