Abstract
Turbo Abstract State Machines are ASMs with parallel and sequential composition and possibly recursive submachine calls. Turbo ASMs are viewed as black-boxes that can combine arbitrary many steps of one or more submachines into one big step. The intermediate steps of a turbo ASM are not observable from outside. It is not even clear what exactly the intermediate steps are, because the semantics of turbo ASMs is usually defined inductively along the call graph of the ASM and the structure of the rule bodies. The most important application of turbo ASMs are recursive algorithms. Such algorithms can directly be simulated on turbo ASMs without transforming them into multi-agent (distributed) ASMs. In this article we analyze the hidden intermediate steps of turbo ASMs and characterize them using PAR/SEQ trees. We also address the problem of the reserve in the presence of recursion and sequential composition. Turbo ASMs with return values are obtained by syntactic sugar.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
M. Anlau. and P. Kutter. Xasm Open Source. Web pages at http://www.xasm.org/, 2001. 261
A. Blass and Y. Gurevich. Background, reserve, and Gandy machines. In P. Clote and H. Schwichtenberg, editors, Computer Science Logic (CSL 2000), pages 1–17. Springer-Verlag, Lecture Notes in Computer Science 1862, 2000. 256
A. Blass and Y. Gurevich. Abstract state machines capture parallel algorithms. ACM Transactions on Computational Logic, 2002. to appear. 245
A. Blass and Y. Gurevich. Algorithms vs. machines. The Logic in Computer Science Column, Bulletin of the European Association for Theoretical Computer Science, 77:96–118, 2002. 246
T. Bolognesi and E. Börger. Abstract State Processes. These Proceedings. 245
E. Börger and T. Bolognesi. Remarks on Turbo ASMs for Functional Equations and Recursion Schemes. These Proceedings. 260
E. Börger and J. Schmid. Composition and submachine concepts. In P. Clote and H. Schwichtenberg, editors, Computer Science Logic (CSL 2000), pages 41–60. Springer-Verlag, Lecture Notes in Computer Science 1862, 2000. 244, 248
Foundations of Software Engineering Group, Microsoft Research. AsmL. Web pages at http://research,microsoft.com/foundations/AsmL/, 2001. 261
Y. Gurevich. Evolving algebras 1993: Lipari guide. In E. Börger, editor, Specifi-cation and Validation Methods, pages 9–36. Oxford University Press, 1993. 256
Y. Gurevich. May 1997 draft of the ASM guide. Technical Report CSE-TR-336-97, EECS Dept., University of Michigan, 1997. 256, 257
Y. Gurevich. Sequential abstract state machines capture sequential algorithms. ACM Transactions on Computational Logic, 1(1):77–111, 2000. 245
Y. Gurevich and M. Spielmann. Recursive Abstract State Machines. J. of Universal Computer Science, 3(4):233–246, 1997. 246
Y. Moschovakis. What is an algorithm? In B. Engquist and W. Schmid, editors, Mathematics Unlimited-2001 and beyond (Part II), pages 919–936. Springer-Verlag, 2001. 245
J. Schmid. Executing ASM specifications with AsmGofer. Web pages at http://www.tydo.de/AsmGofer. 261
R. F. Stärk and S. Nanchen. Al ogic for Abstract State Machines. J. of Universal Computer Science, 7(11):981–1006, 2001. 262
R. F. Stärk, J. Schmid, and E. Börger. Java and the Java Virtual Machine-Definition, Verification, Validation. Springer-Verlag, 2001. 251
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fruja, N.G., Stärk, R.F. (2003). The Hidden Computation Steps of Turbo Abstract State Machines. In: Börger, E., Gargantini, A., Riccobene, E. (eds) Abstract State Machines 2003. ASM 2003. Lecture Notes in Computer Science, vol 2589. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36498-6_14
Download citation
DOI: https://doi.org/10.1007/3-540-36498-6_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00624-4
Online ISBN: 978-3-540-36498-6
eBook Packages: Springer Book Archive