skip to main content
article
Open Access

Combining Algebraic and Algorithmic Reasoning: An Approach to the Schorr-Waite Algorithm

Authors Info & Claims
Published:01 July 1982Publication History
First page image

References

  1. 1 BACKUS, J. Can programming be liberated from the von Neumann style? A functional style and its algebra of programs. Commun. ACM 21, 8 (Aug. 1978), 613-641. Google ScholarGoogle Scholar
  2. 2 BAUER, F.L., PARTSCH, H., PEPPER, P., AND WOSSNER, H. Techniques for program development. In INFOTECH State of the Art Report 34: Software Engineering Techniques. Infotech. Int. Ltd., Maidenhead, England, 1977, pp. 25-50.Google ScholarGoogle Scholar
  3. 3 BAUER, F.L., AND WOSSNER, H. Algorithmic Language and Program Development. To be published by Springer-Verlag, New York. Google ScholarGoogle Scholar
  4. 4 BROY, M., GNATZ, R., AND WIRSlNG, M. Problemspezifikation--Eine Grundlage ffir die Programmentwicklung. In Applied Computer Science, vol. 14: Workshop on Reliable Software: 2nd Meeting of the German Chapter of the ACM, Bonn, 1978, P. Raulefs (Ed.). Carl Hanser Verlag, Munich, 1979, pp. 235-246.Google ScholarGoogle Scholar
  5. 5 BROY, M., MOLLER, B., PEPPER, P., AND WIRSING, M. A model-independent approach to implementations of abstract data types. To appear in Lecture Notes in Computer Science: Proceedings of the Symposium on Algorithmic Logic and the Programming Language LOGAN, Poszran, 1980, A. Salwicki (Ed.). Springer-Verlag, New York.Google ScholarGoogle Scholar
  6. 6 BROY, M., AND PEPPER, P. Program development as a formal activity. IEEE Trans. Softw. Eng. SE-7, 1 (1980), 14-22.Google ScholarGoogle Scholar
  7. 7 BURSTALL, R.M., AND DARLINGTON, J. A transformation system for developing recursive programs. J. ACM24, I (Jan. 1977), 44-67. Google ScholarGoogle Scholar
  8. 8 DERoEvER, W.P. On backtracking and greatest fixpoints. In Lecture Notes in Computer Science, vol. 52: Proceedings of the 4th International Conference on Automata, Languages and Programming, A. Salomaa and M. Steinby (Eds.). Springer-Verlag, New York, pp. 412-429. Google ScholarGoogle Scholar
  9. 9 DERSCHOW~TZ, N. The Schorr-Waite marking algorithm revisited. Inf. Process. Lett. 11, 3 (1980), 141-143.Google ScholarGoogle Scholar
  10. 10 GERHART, S.L. A derivation-oriented proof of the Schorr-Waite graph marking algorithm. In Lecture Notes in Computer Science, vol. 69: Program Construction; Lecture Notes of the International Summer School on Program Construction, Marktoberdorf, 1978, F.L. Bauer and M. Broy (Eds.). Springer-Verlag, New York, 1979, pp. 472-492. Google ScholarGoogle Scholar
  11. 11 GRIES, D. The Schorr-Waite graph marking algorithm. Acta Inf. 11, 3 (1979), 223-232; also in Lecture Notes in Computer Science, vol. 69: Program Construction; Lecture Notes of the International Summer School on Program Construction, Marktoberdorf, 1978, F.L. Bauer and M. Broy (Eds.). Springer-Verlag, New York, 1979, pp. 58-69. Google ScholarGoogle Scholar
  12. 12 GRIFFITHS, M. Development of the Schorr-Waite algorithm. In Lecture Notes in Computer Science, vol. 69: Program Construction; Lecture Notes of the International Summer School on Program Construction, Marktoberdorf, 1978, F.L. Bauer and M. Broy (Eds.). Springer-Verlag, New York, 1979, pp. 464-471. Google ScholarGoogle Scholar
  13. 13 JONKERS, H.B.M. Deriving algorithms by adding and removing variables. IW 34/80, Dep. of Computer Science, Mathematisch Centrum, Amsterdam, Apr. 1980.Google ScholarGoogle Scholar
  14. 14 LAUT, A. Safe procedural implementations of algebraic types. Inf. Process. Lett. 11, 4, 5 (1980), 147-151.Google ScholarGoogle Scholar
  15. 15 LEE, S., DEROEVER, W. P., AND GERItART, S.L. The evolution of list-copying algorithms and the need for structured program verification. In Conference Record of the 6th Annual ACM Symposium on Principles of Programming Languages, San Antonio, Tex., Jan. 29-31, 1979, pp. 53-67. Google ScholarGoogle Scholar
  16. 16 LINDS?ROM, G. Copying list structures using bounded workspace. Commun. ACM 17, 4 (Apr. 1974), 198-202. Google ScholarGoogle Scholar
  17. 17 PEPPER, P. Specification languages and program transformation. In Relationship Between Numerical Computation and Programming Languages: Proceedings of the IFIP WG2.5 Conference, Boulder, Aug. 3-7, 1981, J.K. Reid (Ed.). Elsevier North-HoUand, New York, 1981.Google ScholarGoogle Scholar
  18. 18 PEPPER, P. A Study on Transformational Semantics. Ph.D. dissertation, Technische Universitfit Miinchen, 1979; also in Lecture Notes in Computer Science, vol. 69: Program Construction; Lecture Notes of the International Summer School on Program Construction, Marktoberdorf, 1978, F.L. Bauer and M. Broy (Eds.). Springer-Verlag, New York, 1978, pp. 322-405. Google ScholarGoogle Scholar
  19. 19 PEPPER, P., AND PARTBCH, H. A transformation algorithm for recursion removal. Institut fiir Informatik, Technische Universitiit M'unchen, to appear.Google ScholarGoogle Scholar
  20. 20 SCHORR, H., AND WAI?E, W.M. An efficient machine-independent procedure for garbage collection in various list structures. Commun. ACM 10, 8 (Aug. 1967), 501-506. Google ScholarGoogle Scholar
  21. 21 TOPOR, R.W. The correctness of the Schorr-Waite list marking algorithm. Acta Inf. 11, 3 (1979), 211-222.Google ScholarGoogle Scholar
  22. 22 WIRSlNC, M., PEPPER, P., PARTSCH, H., DOSCH, W., AND BROY, M. On hierarchies of abstract data types. TUM-I8007, Institut ftir Informatik, Technische Universit~it M/inchen, 1980.Google ScholarGoogle Scholar
  23. 23 YELOWITZ, L., ANO DUNCAN, A.G. Abstractions, instantiations, and proofs of marking algorithins. In Proceedings of the Symposium on Artificial Intelligence and Programming Languages, University of Rochester, Rochester, N.Y., Aug. 15-17, 1977. Appeared as combined issue: SIG- PLAN Notices (ACM) 12, 8 (Aug. 1977), and SIGART Newsl. (ACM) 64 (Aug. 1977), 13-21. Google ScholarGoogle Scholar

Index Terms

  1. Combining Algebraic and Algorithmic Reasoning: An Approach to the Schorr-Waite Algorithm

        Recommendations

        Comments

        Login options

        Check if you have access through your login credentials or your institution to get full access on this article.

        Sign in

        Full Access

        • Published in

          cover image ACM Transactions on Programming Languages and Systems
          ACM Transactions on Programming Languages and Systems  Volume 4, Issue 3
          July 1982
          199 pages
          ISSN:0164-0925
          EISSN:1558-4593
          DOI:10.1145/357172
          Issue’s Table of Contents

          Copyright © 1982 ACM

          Publisher

          Association for Computing Machinery

          New York, NY, United States

          Publication History

          • Published: 1 July 1982
          Published in toplas Volume 4, Issue 3

          Permissions

          Request permissions about this article.

          Request Permissions

          Check for updates

          Qualifiers

          • article

        PDF Format

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader