Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 3 / Issue 4

available in:   PDF (275 kB) PS (98 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-003-04-0279


Gurevich Abstract State Machines and Schoenhage Storage Modification Machines

Scott Dexter (University of Michigan, USA)

Patrick Doyle (Stanford University, USA)

Yuri Gurevich (University of Michigan, USA)

Abstract: We demonstrate that Schoenhage storage modification machines are equivalent, in a strong sense, to unary abstract state machines. We also show that if one extends the Schoenhage model with a pairing function and removes the unary restriction, then equivalence between the two machine models survives.