Mike's home
Academic history
Recent Articles
Old Articles
Theory group
My bookmarks
My blog
Some of my research is centred around the view that an abstract data type is a special sort of abstract machine. The operations that characterise the ADT are the instructions of the machine. At present this idea has been exploited mainly in the case of container data types - those equipped with an insert and delete operation (and usually not much else). The aim of the work is to study the relationship between a stream of input tokens that are inserted sequentially, and the stream of output tokens generated by the delete operations.
For container data types the output is a permutation of the input. In most cases only the relative order of the input and output symbols matters; so one relabels the symbols so that the input and output sequences are permutations of 1...n. The behaviour of the container data type is then represented by the set of allowable (input, output) pairs.
Specialising further, it may be that the actual values of the symbols are irrelevant and that only the permutation induced by the container data type matters. In that case we may regard the abstract data type as being a permutation generator. The permutations that it can generate are studied via the theory of restricted permutations .