Data Linkage Algebra, Data Linkage Dynamics, and Priority Rewriting

• Autorzy: Bergstra J.A. , Middelburg C.A.
• Języki publikacji: EN

Abstrakty

EN

We introduce an algebra of data linkages. Data linkages are intended for modelling the states of computations in which dynamic data structures are involved. We present a simple model of computation in which states of computations are modelled as data linkages and state changes take place by means of certain actions. We describe the state changes and replies that result from performing those actions by means of a term rewriting system with rule priorities. The model in question is an upgrade of molecular dynamics. The upgrading is mainly concerned with the features to deal with values and the features to reclaim garbage.

Słowa kluczowe

EN

data linkage algebra; data linkage dynamics; garbage collection; priority rewrite system

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 128, nr 4
• Strony: 367--412
• Opis fizyczny: Bibliogr. 47 poz., tab.

Twórcy

autor

Bergstra J.A.

• Informatics Institute, University of Amsterdam, Science Park 904, 1098 XH Amsterdam, the Netherlands

autor

Middelburg C.A.

• Informatics Institute, University of Amsterdam, Science Park 904, 1098 XH Amsterdam, the Netherlands

Bibliografia

• [1] Arnold, K., Gosling, J., Holmes, D.: The Java Programming Language, Fourth edition, Addison-Wesley, Reading, MA, 2005.
• [2] Baeten, J. C. M., Bergstra, J. A., Klop, J. W., Weijland, W. P.: Term-Rewriting Systems with Rule Priorities, Theoretical Computer Science, 67(2-3), 1989, 283-301.
• [3] Bergstra, J. A., Bethke, I.: Molecular Dynamics, Journal of Logic and Algebraic Programming, 51(2), 2002, 193-214.
• [4] Bergstra, J. A., Bethke, I.: Polarized Process Algebra and Program Equivalence, Proceedings 30th ICALP (J. C. M. Baeten, J. K. Lenstra, J. Parrow, G. J. Woeginger, Eds.), 2719, Springer-Verlag, 2003.
• [5] Bergstra, J. A., Bethke, I., Ponse, A.: Cancellation Meadows: A Generic Basis Theorem and Some Applications, Computer Journal, 56(1), 2013, 3-14.
• [6] Bergstra, J. A., Klop, J. W.: Conditional Rewrite Rules: Confluence and Termination, Journal of Computer and System Sciences, 32(3), 1986, 323-362.
• [7] Bergstra, J. A., Loots, M. E.: Program Algebra for Sequential Code, Journal of Logic and Algebraic Programming, 51(2), 2002, 125-156.
• [8] Bergstra, J. A., Middelburg, C. A.: Programming an Interpreter Using Molecular Dynamics, Scientific Annals of Computer Science, 17, 2007,47-81.
• [9] Bergstra, J. A., Middelburg, C. A.: Thread Algebra for Strategic Interleaving, Formal Aspects of Computing, 19(4), 2007, 445-474.
• [10] Bergstra, J. A., Middelburg, C. A.: Data Linkage Dynamics with Shedding, Fundamenta Informaticae, 103(1-4), 2010, 31-52.
• [11] Bergstra, J. A., Middelburg, C. A.: A Thread Calculus with Molecular Dynamics, Information and Computation,, 208(7), 2010, 817-844.
• [12] Bergstra, J. A., Middelburg, C. A.: Instruction Sequences for Computer Science, vol. 2 of Atlantis Studies in Computing, Atlantis Press, Amsterdam, 2012.
• [13] Bergstra, J. A., Ponse, A.: Combining Programs and State Machines, Journal of Logic and Algebraic Programming, 51(2), 2002, 175-192.
• [14] Bergstra, J. A., Tucker, J. V.: Equational Specifications, Complete Term Rewriting, and Computable and Semicomputable Algebras, Journal of the ACM, 42(6), 1995, 1194-1230.
• [15] Bergstra, J. A., Tucker, J. V.: Elementary Algebraic Specifications of the Rational Complex Numbers, Goguen Festschrift (K. Futatsugi, et al., Eds.), 4060, Springer-Verlag, 2006.
• [16] Bergstra, J. A., Tucker, J. V.: The Rational Numbers as an Abstract Data Type, Journal of the ACM, 54(2), 2007, Article 7.
• [17] Bethke, I., Rodenburg, P. H.: Some Properties of Finite Meadows, arXiv:0712.0917v1 [math.RA], December 2007.
• [18] van den Brand, M. G. J., Klint, P., Verhoef, C.: Term Rewriting for Sale, Electronic Notes in Theoretical Computer Science, 15, 1998, 218-241.
• [19] Carlisle, M. C.: Olden: Parallelizing Programs with Dynamic Data Structures on Distributed-Memory Machines, Ph.D. Thesis, Department of Computer Science, Princeton University, Princeton, 1996.
• [20] Corbera, F., Asenjo, R., Zapata, E. L.: A Framework to Capture Dynamic Data Structures in Pointer-Based Codes, IEEE Transactions on Parallel and Distributed Systems, 15(2), 2004, 151-166.
• [21] Dershowitz, N., Jouannaud, J. P.: Rewrite Systems, in: Handbook of Theoretical Computer Science (J. van Leeuwen, Ed.), vol. B, Elsevier, Amsterdam, 1990, 243-320.
• [22] Flajolet, P., Francon, J., Vuillemin, J.: Towards Analysing Sequences of Operations for Dynamic Data Structures, Foundations of Computer Science 1979, IEEE Computer Society Press, 1979.
• [23] Gnaedig, I.: Termination of Priority Rewriting, LATA 2009 (A. H. Dediu, A. M. Ionescu, C. Martin-Vide, Eds.), 5457, Springer-Verlag, 2009.
• [24] Gosling, J., Joy, B., Steele, G., Bracha, G.: The Java Language Specification, Third edition, Addison-Wesley, Reading, MA, 2005.
• [25] Hejlsberg, A., Torgersen, M., Wiltamuth, S., Golde, P.: The C# Programming Language, Fourth edition, Addison-Wesley, Reading, MA, 2011.
• [26] Hejlsberg, A., Wiltamuth, S., Golde, P.: C# Language Specification, Addison-Wesley, Reading, MA, 2003.
• [27] Hummell, J., Hendren, L. J., Nicolau, A.: A General Data Dependence Test for Dynamic, Pointer-Based Data Structures, ACM SIGPLANNotices, 29(6), 1994, 218-229.
• [28] Jones, C. B.: Systematic Software Development Using VDM, second edition, Prentice-Hall, 1990.
• [29] Jouannaud, J. P., Kirchner, H.: Completion of a Set of Rules Modulo a Set of Equations, SIAM Journal of Computing, 15(4), 1986, 1155-1194.
• [30] Jouannaud, J. P., Marche, C.: Termination and Completion Modulo Associativity, Commutativity and Identity, Theoretical Computer Science, 104(1), 1992, 29-51.
• [31] Kirchner, C., Kirchner, H., de Oliveira, A. S.: Analysis of Rewrite-Based Access Control Policies, Electronic Notes in Theoretical Computer Science, 234, 2009, 55-75.
• [32] Klop, J. W.: Term Rewriting Systems, in: Handbook of Logic in Computer Science (S. Abramsky, D. Gabbay, T. Maibaum, Eds.), vol. 2, Oxford University Press, Oxford, 1992, 1-116.
• [33] Klop, J. W., de Vrijer, R.: First-Order Term Rewriting Systems, in: Term Rewriting Systems (Terese, Ed.), vol. 55 of Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, Cambridge, 2003, 24-59.
• [34] Knuth, D. E.: Deletions That Preserve Randomness, IEEE Transactions on Software Engineering, 3(5), 1977, 351-359.
• [35] McCarthy, J.: Recursive Functions of Symbolic Expressions and Their Computation by Machine, Communications of the ACM, 3(4), 1960, 184-195.
• [36] McCarthy, J., Abrahams, P. W., Edwards, D. J., Hart, T. P., Levin, M. I.: LISP 1.5 Programmer’s Manual, MIT Press, Cambridge, MA, 1962.
• [37] Mohan, C. K.: Priority Rewriting: Semantics, Confluence, and Conditionals, RTA’89 (N. Dershowitz, Ed.), 355, Springer-Verlag, 1989.
• [38] Overmars, M. H., van Leeuwen, J.: Dynamic Multi-Dimensional Data Structures Based on Quad- and K-D Trees, Acta Informatica, 17(3), 1982, 267-285.
• [39] Pheng, S., Verbrugge, C.: Dynamic Data Structure Analysis for Java Programs, Program Comprehension 2006, IEEE Computer Society Press, 2006.
• [40] van der Pol, J.: Operational Semantics of Rewriting with Priorities, Theoretical Computer Science, 200(1-2), 1998, 289-312.
• [41] Rogers, A., Carlisle, M. C., Reppy, J. H., Hendren, L. J.: Supporting Dynamic Data Structures on Distributed- Memory Machines, ACM Transactions on Programming Languages and Systems, 17(2), 1995, 233-263.
• [42] Sakai, M., Toyama, Y.: Semantics and Strong Sequentiality of Priority Term Rewriting Systems, Theoretical Computer Science, 208(1-2), 1998, 87-110.
• [43] Sannella, D., Tarlecki, A.: Algebraic Preliminaries, in: Algebraic Foundations of Systems Specification (E. Astesiano, H.-J. Kreowski, B. Krieg-Briickner, Eds.), Springer-Verlag, Berlin, 1999, 13-30.
• [44] Tamassia, R.: A Dynamic Data Structure for Planar Graph Embedding, ICALP’88 (T. Lepisto, A. Salomaa, Eds.), 317, Springer-Verlag, 1988.
• [45] Ulidowski, I., Yuen, S.: Generating Priority Rewrite Systems for OSOS Process Languages, Information and Computation, 207(2), 2009, 120-145.
• [46] Wirsing, M.: Algebraic Specification, in: Handbook of Theoretical Computer Science (J. van Leeuwen, Ed.), vol. B, Elsevier, Amsterdam, 1990, 675-788.
• [47] Zantema, H.: Termination, in: Term Rewriting Systems (Terese, Ed.), vol. 55 of Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, Cambridge, 2003, 181-259.