The Expressive Power of Abstract-State Machines

Authors

  • Wolfgang Reisig

Keywords:

Specification technique, expressive power, computation models, sequential

Abstract

Conventional computation models assume symbolic representations of states and actions. Gurevich's Abstract-State Machine model takes a more liberal position: Any mathematical structure may serve as a state. This results in "a computational model that is more powerful and more universal than standard computation models". We characterize the Abstract-State Machine model as a special class of transition systems that widely extends the class of "computable" transition systems. This characterization is based on a fundamental Theorem of Y. Gurevich.

Downloads

Download data is not yet available.

Downloads

Published

2012-02-20

How to Cite

Reisig, W. (2012). The Expressive Power of Abstract-State Machines. Computing and Informatics, 22(3-4), 209–219. Retrieved from http://147.213.75.17/ojs/index.php/cai/article/view/455