
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 contextfree 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 noncontextfree languages. Finally it is shown that under certain restrictions only contextsensitive languages are represented but that in general noncontextsensitive 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