RAM Simulation of BGS Model of Abstract-state Machines

• Autorzy: Seshadhri S. , Seth A. , Biswas S.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

abstract state machines; BGS model

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 77, nr 1,2
• Strony: 175--185
• Opis fizyczny: bibliogr. 9 poz.

Twórcy

autor

Seshadhri S.

autor

Seth A.

autor

Biswas S.

• Department of Computer Science, Princeton University, Princeton NJ 08544, USA,

Bibliografia

• [1] The Design and Analysis of Computer Algorithms, Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman, Addison-Wesley, 1974.
• [2] The Linear Time Hierarchy Theorems for RAMs and Abstract State Machines, Andreas Blass and Yuri Gurevich, Springer Jl. of Universal Computer Science, Vol 3, No. 4, pp 247-278, 1997.
• [3] Background, Reserve, and GandyMachines, Andreas Blass and Yuri Gurevich, Proc. CSL 2000, LNCS Vol. 1862, pp 1 - 17, 2000.
• [4] Personal communication, Andreas Blass and Yuri Gurevich, July 2004.
• [5] Choiceless Polynomial Time, Andreas Blass, Yuri Gurevich, and Saharon Shelah, Annals of Pure and Applied Logic, 100, pp 141 - 187, 1999.
• [6] On Polynomial Time Computation over Unordered Structures, Andreas Blass, Yuri Gurevich, and Saharon Shelah, Journal of Symbolic Logic, 67:3, pp 1093 - 1125, 2002.
• [7] Abstract State Machines, Egon Börger and Robert Stärk, Springer-Verlag, 2003.
• [8] See home page of Yuri Gurevich http://www.research.microsoft.com/~ gurevich for extensive information on ASMs.
• [9] The Design and Analysis of Algorithms, Dexter C. Kozen, Springer-Verlag, 1992.