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