RAM Simulation of BGS Model of Abstract-state Machines

Issue title: This is a SPECIAL ISSUE ON ASM'05

Article type: Research Article

Authors: Seshadhri, Comandur | Seth, Anil | Biswas, Somenath

Affiliations: Department of Computer Science, Princeton University, Princeton NJ 08544, USA. E-mail: sb@cse.iitk.ac.in | Department of Computer Science and Engineering, IIT Kanpur, Kanpur 208016, India

Abstract: We show in this paper that the BGS model of abstract state machines can be simulated by random access machines with at most a polynomial time overhead. This result is already stated in [5] with a very brief proof sketch. The present paper gives a detailed proof of the result. We represent hereditarily finite sets, which are the typical BGS ASM objects, by membership graphs of the transitive closure of the sets. Testing for equality between BGS objects can be done in linear time in our representation.

Journal: Fundamenta Informaticae, vol. 77, no. 1-2, pp. 175-185, 2007