Top

Published in:

2021 | OriginalPaper | Chapter

What is the Natural Abstraction Level of an Algorithm?

Author : Andreas Prinz

Published in: Logic, Computation and Rigorous Methods

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Abstract State Machines work with algorithms on the natural abstraction level. In this paper, we discuss the notion of the natural abstraction level of an algorithm and how ASM manage to capture this abstraction level. We will look into three areas of algorithms: the algorithm execution, the algorithm description, and the algorithm semantics. We conclude that ASM capture the natural abstraction level of the algorithm execution, but not necessarily of the algorithm description. ASM do also capture the natural abstraction level of execution semantics.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Analysis of Mobile Networks’ Protocols Based on Abstract State Machine

next chapter The ASMETA Approach to Safety Assurance of Software Systems

This is given by the abstract state postulate.

In some sense, this turns HALT from a syntactic element into a semantic element. Minsky would have been able to avoid the HALT if there was a rule that the execution stops when moving (GOTO) out of the program.

There are also advanced ASM concepts to handle structured executions, often called Turbo-ASM [9].

Bennedsen, J., Caspersen, M.E.: Model-driven programming. In: Bennedsen, J., Caspersen, M.E., Kölling, M. (eds.) Reflections on the Teaching of Programming. LNCS, vol. 4821, pp. 116–129. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-77934-6_10. http://link.springer.com/book/10.1007%2F978-3-540-77934-60CrossRef

Blass, A., Gurevich, Y.: Ordinary interactive small-step algorithms I. ACM Trans. Comput. Log. 7(2), 363–419 (2006)MathSciNetCrossRef

Blass, A., Gurevich, Y.: Abstract state machines capture parallel algorithms: correction and extension. ACM Trans. Comput. Log. 9(3) (2008). https://doi.org/10.1145/1352582.1352587

Blass, A., Gurevich, Y., Rosenzweig, D., Rossman, B.: Interactive small-step algorithms II: abstract state machines and the characterization theorem. Log. Methods Comput. Sci. 3(4) (2007). https://doi.org/10.2168/LMCS-3(4:4)2007

Blass, A., Gurevich, Y.: Abstract state machines capture parallel algorithms. ACM Trans. Comput. Log. (TOCL) 4(4), 578–651 (2003). https://doi.org/10.1145/937555.937561MathSciNetCrossRefMATH

Blass, A., Gurevich, Y.: Persistent queries in the behavioral theory of algorithms. ACM Trans. Comput. Log. (TOCL) 12(2), 16:1–16:43 (2011). https://doi.org/10.1145/1877714.1877722MathSciNetCrossRefMATH

Boolos, G.S., Burgess, J.P., Jeffrey, R.C.: Computability and Logic, 5th edn. Cambridge University Press, Cambridge (2007). https://doi.org/10.1017/CBO9780511804076CrossRefMATH

Börger, E., Cisternino, A. (eds.): Advances in Software Engineering. LNCS, vol. 5316. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-89762-0CrossRef

Börger, E., Stärk, R.: Abstract State Machines - A Method for High-Level System Design and Analysis. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-642-18216-7CrossRefMATH

10.

Börger, E.: Construction and analysis of ground models and their refinements as a foundation for validating computer-based systems. Appl. Formal Methods 19(2), 225–241 (2007). https://doi.org/10.1007/s00165-006-0019-yCrossRefMATH

11.

Börger, E., Cavarra, A., Riccobene, E.: On formalizing UML state machines using ASMs. Inf. Softw. Technol. 46(5), 287–292 (2004). https://doi.org/10.1016/j.infsof.2003.09.009CrossRef

12.

Börger, E., Raschke, A.: Modeling Companion for Software Practitioners. Springer, Heidelberg (2018). https://doi.org/10.1007/978-3-662-56641-1CrossRef

13.

Börger, E., Schewe, K.D.: Concurrent abstract state machines. Acta Informatica 53(5), 469–492 (2016). https://doi.org/10.1007/s00236-015-0249-7MathSciNetCrossRefMATH

14.

Börger, E., Schulte, W.: A programmer friendly modular definition of the semantics of Java. In: Alves-Foss, J. (ed.) Formal Syntax and Semantics of Java. LNCS, vol. 1523, pp. 353–404. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48737-9_10CrossRef

15.

Brooks Jr, F.P.: No silver bullet essence and accidents of software engineering. Computer 20(4), 10–19 (1987). https://doi.org/10.1109/MC.1987.1663532. http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1663532

16.

Editor OMG: Meta object facility (MOF) 2.0 query/view/transformation specification, version 1.1. Object Management Group (2011). http://www.omg.org/spec/QVT/1.1/

17.

Editor OMG: Meta object facility (MOF). Object Management Group (2016). https://www.omg.org/spec/MOF

18.

Felleisen, M., Hieb, R.: The revised report on the syntactic theories of sequential control and state. Theor. Comput. Sci. 103(2), 235–271 (1992)MathSciNetCrossRef

19.

Fischer, J., Møller-Pedersen, B., Prinz, A.: Real models are really on M0- or how to make programmers use modeling. In: Proceedings of the 8th International Conference on Model-Driven Engineering and Software Development-Volume 1: MODELSWARD, pp. 307–318. INSTICC, SciTePress (2020). https://doi.org/10.5220/0008928403070318

20.

Fowler, M.: Domain Specific Languages, 1st edn. Addison-Wesley Professional, Boston (2010)

21.

Glässer, U., Gotzhein, R., Prinz, A.: The formal semantics of SDL-2000: status and perspectives. Comput. Netw. 42(3), 343–358 (2003). https://doi.org/10.1016/S1389-1286(03)00247-0CrossRefMATH

22.

Gurevich, Y.: Evolving algebras 1993: lipari guide. In: Specification and Validation Methods, pp. 231–243. Oxford University Press (1995)

23.

Gurevich, Y.: Sequential abstract-state machines capture sequential algorithms. ACM Trans. Comput. Log. (TOCL) 1(1), 77–111 (2000). https://doi.org/10.1145/343369.343384MathSciNetCrossRefMATH

24.

Harel, D., Rumpe, B.: Meaningful modeling: what’s the semantics of “semantics”? Computer 37(10), 64–72 (2004). https://doi.org/10.1109/MC.2004.172CrossRef

25.

Jouault, F., Allilaire, F., Bézivin, J., Kurtev, I.: ATL: a model transformation tool. Sci. Comput. Program. 72(1–2), 31–39 (2008). https://doi.org/10.1016/j.scico.2007.08.002MathSciNetCrossRefMATH

26.

Kahn, G.: Natural semantics. In: Brandenburg, F.J., Vidal-Naquet, G., Wirsing, M. (eds.) STACS 1987. LNCS, vol. 247, pp. 22–39. Springer, Heidelberg (1987). https://doi.org/10.1007/BFb0039592CrossRef

27.

Kleppe, A., Warmer, J.: MDA Explained. Addison-Wesley, Boston (2003)

28.

Konat, G., Kats, L., Wachsmuth, G., Visser, E.: Declarative name binding and scope rules. In: Czarnecki, K., Hedin, G. (eds.) SLE 2012. LNCS, vol. 7745, pp. 311–331. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36089-3_18CrossRef

29.

Lindholm, T., Yellin, F., Bracha, G., Buckley, A.: The Java Virtual Machine Specification, Java SE 8 Edition, 1st edn. Addison-Wesley Professional, Boston (2014)

30.

Madsen, O.L., Møller-Pedersen, B.: This is not a model. In: Margaria, T., Steffen, B. (eds.) ISoLA 2018. LNCS, vol. 11244, pp. 206–224. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03418-4_13CrossRef

31.

Minsky, M.L.: Computation: Finite and Infinite Machines. Prentice-Hall Inc., Englewood Cliffs (1967)MATH

32.

Mu, L., Gjøsæter, T., Prinz, A., Tveit, M.S.: Specification of modelling languages in a flexible meta-model architecture. In: Proceedings of the Fourth European Conference on Software Architecture: Companion Volume, ECSA 2010, pp. 302–308. Association for Computing Machinery, New York (2010). https://doi.org/10.1145/1842752.1842807

33.

von Neumann, J.: First draft of a report on the EDVAC. In: Randell, B. (ed.) The Origins of Digital Computers. MCS, pp. 383–392. Springer, Heidelberg (1982). https://doi.org/10.1007/978-3-642-61812-3_30CrossRef

34.

Ouimet, M., Lundqvist, K.: The timed abstract state machine language: abstract state machines for real-time system engineering. J. UCS 14, 2007–2033 (2008)MathSciNet

35.

Plotkin, G.D.: A structural approach to operational semantics. J. Log. Algebraic Program. 60–61, 17–139 (2004). https://doi.org/10.1016/j.jlap.2004.05.001. Structural Operational SemanticsMathSciNetCrossRefMATH

36.

Prinz, A.: Distributed computing on distributed memory. In: Khendek, F., Gotzhein, R. (eds.) SAM 2018. LNCS, vol. 11150, pp. 67–84. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-01042-3_5CrossRef

37.

Prinz, A., Møller-Pedersen, B., Fischer, J.: Object-oriented operational semantics. In: Grabowski, J., Herbold, S. (eds.) SAM 2016. LNCS, vol. 9959, pp. 132–147. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-46613-2_9CrossRef

38.

Prinz, A., Sherratt, E.: Distributed ASM - pitfalls and solutions. In: Aït-Ameur, Y., Schewe, K.D. (eds.) ABZ 2014. LNCS, vol. 8477, pp. 210–215. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43652-3_18 CrossRef

39.

Scheidgen, M., Fischer, J.: Human comprehensible and machine processable specifications of operational semantics. In: Akehurst, D.H., Vogel, R., Paige, R.F. (eds.) ECMDA-FA 2007. LNCS, vol. 4530, pp. 157–171. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-72901-3_12CrossRef

40.

Schewe, K.-D., Wang, Q.: A simplified parallel ASM thesis. In: Derrick, J., et al. (eds.) ABZ 2012. LNCS, vol. 7316, pp. 341–344. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-30885-7_27CrossRef

41.

Sipser, M.: Introduction to the Theory of Computation, 3rd edn. Course Technology, Boston (2013)MATH

42.

Stone, H.S.: Introduction to Computer Organization and Data Structures. McGraw-Hill, New York (1972)

43.

Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem. Proc. Lond. Math. Soc. s2-42(1), 230–265 (1937). https://doi.org/10.1112/plms/s2-42.1.230. https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/plms/s2-42.1.230

44.

Warren, D.S.: WAM for everyone: a virtual machine for logic programming, pp. 237–277. Association for Computing Machinery and Morgan & Claypool (2018). https://doi.org/10.1145/3191315.3191320

Title: What is the Natural Abstraction Level of an Algorithm?
Author: Andreas Prinz
Publisher: Springer International Publishing
Book: Logic, Computation and Rigorous Methods
Print ISBN: 978-3-030-76019-9

Electronic ISBN: 978-3-030-76020-5

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-76020-5_12

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner