Distributed Abstract State Machines and Their Expressive Power

Abstract

Gurevich’s sequential Abstract State Machines (ASMs) are taken as a basis for the construction of distributed ASMs as sets of sequential ASMs. A theorem on the expressive power of distributed ASM is proven in analogy to Gurevich’s classical theorem on the expressive power of sequential ASM.