Accession Number : AD0713953

Title :   Towards a Theory of Data Structures.

Descriptive Note : Technical rept.,

Corporate Author : IOWA UNIV IOWA CITY DEPT OF MATHEMATICS

Personal Author(s) : Fleck,Arthur C.

Report Date : AUG 1970

Pagination or Media Count : 29

Abstract : A formal idealization of the data structure used in many 'list processing' languages is defined. It is then shown that under a natural interpretation these data structures define exactly the context-free languages of automata theory. Then a generalization in the direction of the 'patterns' of SNOBOL is made. It is observed that this generalization models the ability of SNOBOL patterns to represent non-context-free languages. Finally it is shown that under certain restrictions only context-sensitive languages are represented but that in general non-context-sensitive languages can occur. (Author)

Descriptors :   (*PROGRAMMING LANGUAGES, GRAMMARS), CONTEXT FREE GRAMMARS, CONTEXT SENSITIVE GRAMMARS, AUTOMATA

Subject Categories : Computer Programming and Software

Distribution Statement : APPROVED FOR PUBLIC RELEASE