Research work · 1997

The Combinatorics of some Abstract Data Types

Mark D Atkinson, D. Tulley

Oxford University Press eBooks

Abstract

Abstract Abstract data types (ADTs) may be regarded as abstract machines and then a program for an ADT is any sequence of operations allowed by its speciflcation. The effect of such programs on container ADTs is captured by the relationship between each input sequence and the set of possible output sequences that can result from it. This relationship is studied principally in the case of dictionaries, stacks and priority queues and a distinction is drawn between ADTs of unbounded and bounded capacity. Abstract machines have a long and honourable history in Computer Science. Turing machines, push-down automata, and flnite-state machines are three well known types; they have been used to study general purpose computers, compilers, and string manipulation although their importance goes well beyond these three applications. The central theoretical issue for these (and other) machines is the characterisation of the languages associated with them. The aim of this paper is to study some abstract data types in the same spirit.

DOI: 10.1093/oso/9780198511922.003.0001