Abstract state machine
An abstract state machine (English Abstract State Machine , not to be confused (ASM) with algorithmic state machines , formerly also Evolving Algebra called (EVA)), is in computer science , a model for formal operational description of algorithms . In contrast to finite automata , whose states only have names, the states of an abstract state machine are general mathematical structures .
In the field of translator construction , the model is used to describe the semantics of the program to be translated, and it helps to ensure that the semantics of the program to be translated are preserved ( verification ). When developing software in general, the model allows a formal description of the functional requirements in the analysis and design phase. This mathematical approach improves verifiability and reusability, for example.
When designing complex switchgear , formalization with abstract state machines is also used.
origin
The inventor of the model is Yuri Gurevich from Microsoft . The computer scientist Egon Börger , based in Italy at the University of Pisa , researches methods for the application of abstract state machines in the design and analysis of hardware and software systems.
In the meantime there are different implementations of the model so that the design and interpretation of programs for the abstract machine can be computer-aided.
literature
- Yuri Gurevich, Philipp W. Kutter, Martin Odersky , Lothar Thiele (eds.): Abstract State Machines. Theory and Applications. Springer, Berlin et al. 2000, ISBN 3-540-67959-6 ( Lecture Notes in Computer Science 1912).
swell
- ^ A New Thesis, Abstracts, American Mathematical Society, Vol. 6, No. 4 (Aug 1985), page 317, abstract 85T-68-203
- ↑ E. Börger, R. Stark: Abstract State Machines: A Method for High-Level System Design and Analysis , Springer-Verlag , 2003. ( ISBN 3-540-00702-4 )
Web links
information
- Abstract State Machines - definition, examples and counterexamples (19 pages PDF; 166 kB)
- Abstract State Machines - short explanation, detailed definition (English, 12 pages PDF; 372 kB)
- Verification of translators with ASMs - transparencies (165 pages PDF; 2.2 MB)
- Verification of translators with ASMs - text version (16 pages PDF; 237 kB)
- Abstract State Machines - sorted materials
- ASM Workshops - Events on the topic
Implementations
- (Abstract State Machine Language) - language designed by Yuri Gurevich
- XASM (Anlauff's eXtensible ASMs) - expandable, minimal language (English)
- The CoreASM Project - Verification of Distributed and Embedded Systems (English)
- TASM (Timed Abstract State Machine Language and Toolset) ( Memento from April 17, 2009 in the Internet Archive ) - Extensions for the description of non-functional properties (English)
- ASMETA project - ASM metamodel according to the guidelines of model-driven software development for interoperability between ASM languages (English)