Towards a Theory of Data Structures.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1970
- Accession Number
- AD0713953
Entities
People
- Arthur C. Fleck
Organizations
- University of Iowa