Title Some structural properties of Associative Language Descriptions
Authors Alessandra Cherubini, Politecnico di Milano
Stefano Crespi Reghizzi, Politecnico di Milano
Pierluigi San Pietro, Politecnico di Milano
Main Fields 8. formal languages
Other Main Fields
Abstract + Keywords The Associative Language Description model (ALD), a combination of locally testable and constituent structure ideas, has been recently proposed to overcome some criticisms relative to context-free languages. This approach 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. Moreover, it excludes mathematical sets based on counting properties which are never used in the definition of artificial languages. Many properties of ALD are still to be investigated. Here, a characterization of context free languages in term of ALD languages is proved and a new hierarchy in the ALD family is given.