Expressive Power of Abstract State Machines

• Contact: Andreas Glausch, Prof. Dr. Wolfgang Reisig

This project is funded by the Deutsche Forschungsgemeinschaft (DFG).

Abstract State Machines (ASMs) have been introduced as a ''computation model that is more powerful and more universal than the standard computation models'' by Yuri Gurevich in 1985. This is achieved by adopting classical concepts from logics and universal algebra: States are represented as first-order structures, and steps are described by ASM programs built from terms and Boolean formulas.

Gurevich characterized the expressive power of sequential ASMs in a Theorem known as the sequential ASM theorem. The theorem states that every transition system whose states are first-order structures and which meets only a few intuitive requirements can be expressed by a sequential  ASM.

Several variants of ASMs have been identified, among them nondeterministric, parallel, distributed, and interactive versions. In recent years the expressive power of parallel and interactive ASMs has been characterized and published in papers co-authored by Gurevich. In the course of this project we have established similar results for the case of nondeterministic and distributed ASMs.

The overall aim of this Project is to understand and to characterize the expressive power of all major variants of ASMs within a single, consistent framework. In that way, subtle relationships between those variants and connections to other computational models are revealed. Furthermore, this project aims at relating ASMs to existing system specification techniques. This in particular includes problems of refinement and composition.

Events Organized by the Chair

Workshop "Perspectives on the ASM Theorem 2007", Feb. 26-28

The Chair's Recent Publications on ASMs

• Andreas Glausch and Wolfgang Reisig. On the Expressive Power of Unbounded-Nondeterministic Abstract State Machines. Informatik-Berichte 211, Humboldt-Universität zu Berlin, December 2006.

• Andreas Glausch and Wolfgang Reisig. Distributed Abstract State Machines and Their Expressive Power. Informatik-Berichte 196, Humboldt-Universität zu Berlin, January 2006.

• Wolfgang Reisig. Abstract State Machines for the Classroom, The Basics. Mai 2006. Note: To appear.

• Wolfgang Reisig. On Gurevich's Theorem on Sequential Algorithms. Acta Informatica, 39(5):273-305, 2003.

• Wolfgang Reisig. The Expressive Power of Abstract State Machines. Computing and Informatics, 22(3):209-219, 2003.

• Wolfgang Reisig. The Computable Kernel of ASM. In Egon Börger, Angelo Gargantini, and Elvinia Riccobene, editors, Abstract State Machines, Advances in Theory and Practice, 10th International Workshop, ASM 2003, Taormina, Italy, volume 2589 of Lecture Notes in Computer Science, pages 421-422, 2003.

• Wolfgang Reisig. Towards an ASM Thesis for Unconventional Algorithms. In Yuri Gurevich, Philipp W. Kutter, Martin Odersky, and Lothar Thiele, editors, Abstract State Machines, volume 1912 of Lecture Notes in Computer Science, pages 112-130, 2000. Springer-Verlag.

Links

• ASM Homepage
• ASM Research Center
• 14th International ASM-Workshop (ASM'07), June 7-9