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):

Report Date:

1970-08-01

Pagination or Media Count:

29.0

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

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE