Towards a Theory of Data Structures.
IOWA UNIV IOWA CITY DEPT OF MATHEMATICS
Pagination or Media Count:
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
- Computer Programming and Software