Skip to main content
Springer Nature Link
Log in

Dynamic abstract data types based on algebraic graph transformations

  • Contributed Papers
  • Conference paper
  • First Online:
Recent Trends in Data Type Specification (ADT 1994, COMPASS 1994)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 906))

Abstract

The concept of dynamic abstract data types was recently proposed by two of the authors as a dynamic extension of the well-known concept of abstract data types, motivated by several recent approaches in the areas of algebraic specifications, object-orientation, evolving algebras and graph transformations. The basic idea of dynamic abstract data types is to extend abstract data types by dynamic operations which are transformations between abstract data types. In this paper we consider a specific kind of dynamic abstract data types where the transformations are defined by rules in the sense of algebraic graph transformations. The concept of attributed graph transformations is used to define this new version of dynamic abstract data types and to show some important properties of the corresponding transition category. The constructions are illustrated by a small example from the area of data bases.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Astesiano, E., Zucca, E.: A Semantic Model for Dynamic Systems. Springer Workshops in Computing, 1992/93, pp. 63–80

    Google Scholar 

  2. Astesiano, E., Zucca, E.: D-oids: A Model for Dynamic Data Types. Special Issue of MSCS, accepted for publication 1994

    Google Scholar 

  3. Bardohl. R., Ehrig, H.: Specification of Shipping Software Using Dynamic Abstract Data Types. In preparation (1994)

    Google Scholar 

  4. Corradini, A., Ehrig, H., Löwe, M., Montanari, U., Rossi, F.: Abstract Graph Derivations in the Double-Pushout Approach. Proc. Graph Grammar Workshop Dagstuhl 1993, Springer LNCS 776 (1994), pp. 86–103

    Google Scholar 

  5. Claßen, I., Löwe, M., Waßerroth, S., Wortmann, J.: Static and Dynamic Semantics of Entity-Relationship Models Bassed on Algebraic Methods, Proc. IFIP-Congress and GI-Fachgespräche, Hamburg 1994, to appear

    Google Scholar 

  6. Dauchy, P., Gaudel, M.G.: Algebraic Specifications with Implicit State. Techn. Report, Univ. Paris-Sud, 1994

    Google Scholar 

  7. Ehrig, H.: Introduction to the algebraic theory of graph grammars (A Survey) in: Graph Grammars and Their Application to Computer Science and Biology, Springer LNCS 73, (1979), 1–69

    Google Scholar 

  8. Ehrich, H.D.: Modular Semantics for Concurrent Families of Sequential Objects, Lecture at ADT-COMPASS Workshop, Santa Margharita Ligure, 1994

    Google Scholar 

  9. Ehrig, H., Löwe, M.: The ESPRIT BRWG COMPUGRAPH “Computing by Graph Transformations”: A Survey. TCS 109 (1993), pp. 3–6

    Article  Google Scholar 

  10. Ehrig, H., Mahr, B.: Fundamentals of Algebraic Specification 1. Equations and Initial Semantics. EATCS Monographs on Theoretical Computer Science, Vol. 6, Springer (1985)

    Google Scholar 

  11. Ehrig, H.; Mahr, B.: Fundamentals of Algebraic Specification 2. Module Specifications and Constraints. EATCS Monographs on Theoretical Computer Science, Vol. 21, Springer-Verlag (1990)

    Google Scholar 

  12. Ehrig, H., Orejas, F.: Dynamic Abstract Data Types: An Informal Proposal, Bull. EATCS 53 (1994), pp. 162–169

    Google Scholar 

  13. Gottlieb, G., Kappel, G., Scheff, M.: Semantics of Object Oriented Data Models — The Evolving Algebra Approach. Springer LNCS 504 (1992), pp. 144–160

    Google Scholar 

  14. Gogolla, M.: An Algebraic Semantics for the Object Specification Language TROLL-light. Lecture at ADT-COMPASS Workshop, Santa Margharita Ligure, 1994

    Google Scholar 

  15. Große-Rhode, M.: Towards Object-Oriented Algebraic Specifications. Recent Trends in Data Type Specifications, Springer LNCS 534, 1990, pp. 98–116

    Google Scholar 

  16. Große-Rhode, M.: Specification of Parallel State Dependent Systems. TU Berlin, 1994, in preparation

    Google Scholar 

  17. Gurevitch, Y.: Evolving Algebras, A Tutorial Introduction. Bull. EATCS 43 (1991), pp. 264–284

    Google Scholar 

  18. Gurevitch, Y.: Evolving Algebra 1993. In Boerger (ed.): Specification and Validation Methods, Oxford University Press, to appear 1994

    Google Scholar 

  19. Heckel, R., Müller, J., Taentzer, G., Wagner A.: Attributed Graph Transformations with Controlled Application of Rules, Proc. Graph Grammar Workshop, Mallorca 1994, to appear

    Google Scholar 

  20. Korff, M.: Single Pushout Transformations of Equationally Defined Graph Structures with Applications to Actor Systems. Proc. Graph Grammar Workshop Dagstuhl 1993, Springer LNCS 776, 1994, pp. 234–247

    Google Scholar 

  21. M. Löwe, H. Ehrig: Algebraic Approach to Graph Transformation Based on Single Pushout Derivations, in: 16th Int. Workshop on Graph-Theoretic Concepts in Comp. Sci., Springer LNCS 484, pp. 338–353, 1991.

    Google Scholar 

  22. Löwe, M., Korff, M., Wagner, A.: An Algebraic Framework for the Transformation of Attributed Graphs. In M.R. Sleep et.al. (eds.) Term Graph Rewriting: Theory and Practice, Wiley, London (1993), pp. 185–199

    Google Scholar 

  23. Löwe, M.: Extended Algebraic Graph Transformations, PhD thesis, TU Berlin 1990, short version in TCS 109, pp. 181–224

    Google Scholar 

  24. Padberg, J.: Abstract Data Type Semantics for Algebraic High-Level Nets Using Dynamic Abstract Data Types, Proc. Int. Workshop on Quality of Communication Based Systems, Berlin 1994, to appear

    Google Scholar 

  25. Pierantonio, A.: Making Static Dynamic: Towards an Axiomatization for Dynamic ADT's. Proc. Int. Workshop on Quality of Communication Based Systems, Berlin 1994, to appear

    Google Scholar 

  26. Parisi-Presicce, F., Pierantonio, A.: An Algebraic Approach to Inheritance and Subtyping. Proc. ESEC 1991, Springer LNCS 550, 1991, pp. 364–379

    Google Scholar 

  27. Pierantonio, A., Parisi-Presicce, F.: On the Algebraic Specification of Object Dynamics in Object-Oriented Systems. Lecture at joint COMPASS-ISCORE workshop, Lisbon 1994, paper in preparation 1994

    Google Scholar 

  28. Reichel, H.: An Approach to Object Semantics Based on Terminal Co-Algebras. Special Issue of MSCS, to appear 1994

    Google Scholar 

  29. Wagner, E.: On Declarations; Springer LNCS 393, 1989, pp. 261–277

    Google Scholar 

  30. Weber, H., Ehrig, H.: Specification of Concurrently Executable Modules and Distributed Modular Systems. Proc. Workshop Future Trends of Distr. Comp. Systems in the 1990's, HongKong, 1988, pp. 202–215

    Google Scholar 

  31. agner, A., Gogolla, M.: Defining Operational Behaviour of Object Specifications by Attributed Graph Transformations. Internal Report, 1994

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. TU, Berlin

    Hartmut Ehrig

  2. ISST, Berlin

    Michael Löwe

  3. Univ. of Catalunya, Spain

    Fernando Orejas

Authors
  1. Hartmut Ehrig
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michael Löwe
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Fernando Orejas
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Egidio Astesiano Gianna Reggio Andrzej Tarlecki

Rights and permissions

Reprints and permissions

Copyright information

© 1995 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Ehrig, H., Löwe, M., Orejas, F. (1995). Dynamic abstract data types based on algebraic graph transformations. In: Astesiano, E., Reggio, G., Tarlecki, A. (eds) Recent Trends in Data Type Specification. ADT COMPASS 1994 1994. Lecture Notes in Computer Science, vol 906. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0014431

Download citation

  • DOI: https://doi.org/10.1007/BFb0014431

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-59132-0

  • Online ISBN: 978-3-540-49198-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation