Towards a theory of data structures

✍ Scribed by A.C. Fleck

• Publisher: Elsevier Science
• Year: 1971
• Tongue: English
• Weight: 743 KB
• Volume: 5
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(71)80011-9

✦ Synopsis

A formal idealization of the data structures 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 noncontext-free languages. Finally, it is shown that under certain restrictions, only context-sensitive languages are represented but that in general noncontext-sensitive languages can occur.