Keywords:Batch mode reading, pointer machine, real time simulation, multiset discrimination, type system.
In [Paige89], it was shown how to simulate a set machine in real-time on a RAM that provides cursor or even only pointer access to data. The underlying assumption was that the establishment of efficient data structures would be provided by some `client' program. In the current paper, we fill in the gap by presenting a linear-time high level reading method that translates external input in string form into data structures that facilitate such real-time simulation. The algorithm builds the data structures for a much richer type system than what appeared in [Paige94], and is powerful enough to support our reading algorithm itself in an efficient way. Consequently, it equips a high level set-theoretic language with I/O, without the loss of computational transparency.
This work alleviates the burden of creating low-level data structures manually, and generates the internal pointer inputs required by most pointer algorithms [Ben-Amram95] from the external string representation.