The Pattern-of-Calls Expansion Is the Canonical Fixpoint for Recursive Definitions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The Pattern-of-Calls Expansion Is the Canonical Fixpoint for Recursive Definitions

Full text

Pdf (1.30 MB)

Source

Journal of the ACM (JACM) archive
Volume 29 , Issue 2 (April 1982) table of contents

Pages: 577 - 602

Year of Publication: 1982

ISSN:0004-5411

Authors

Michael A. Arbib	Department of Computer and Information Science, University of Massachusetts, Amherst, MA
Ernest G. Manes	Department of Mathematics and Statistics, University of Massachusetts, Amherst, MA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 20, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322307.322325 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Michael A. Arbib , Ernest G. Manes, Partially-Additive Monoids, Graph-Growing, and the Algebraic Semantics of Recursive Calls, Proceedings of the International Workshop on Graph-Grammars and Their Application to Computer Science and Biology, p.127-138, October 30-November 03, 1978
	2	Arbib, M A., AND MA..'~S, E.G. Partaally-add~dve categories and flow-diagram semantics, d. Algebra 62 09so), 203-227.
	3	Arnold, A., ANn NrvAr, M.The metric space of inf'mite trees: Algebraic and topological properties. Tech. Pep. 323, IRIA Laboria, 78150 Le Chesnay, France, 1978.
	4	Edward Ashcroft , Zohar Manna , Amir Pnueli, Decidable Properties of Monadic Functional Schemas, Journal of the ACM (JACM), v.20 n.3, p.489-499, July 1973 [doi>10.1145/321765.321780]
	5	John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
	6	BLOOM, S.L.Varieties of ordered algebras. ~ Comput. Syst. Scf. 13 (1976), 203-212.
	7	BLOOM, S.L.lterative and metric algebraic theories. Pteprint, Dep. of Pure and Applied Mathematics, Stevens Institute of Technology, Hoboken, N,J., 1977.
	8	Chomsky, N,, AND SCHUTZI~NBF, J~.GEE~, M.The algebraic theory of exmtext-frt~ languages. In Computer Programming and Formal Systems, P. Brat'ford and D. Hirsehberg, Eds., North-Holland, Amsterdam, 1963, pp. 118-161.
	9	Corn% P.M. Universal Algebra. Harper and Row, New York, 1965.
	10	DE BAKK~, J W., AND M.EERTILMS, L.G. On the completeness of the inductive assertion method. J. Comput. Syst. Scl. 11 (1975), 323-357.
	11	DE RoLwva~, W.P. Jr,Reeursive program schemes: Semantics and proof theory. Mathematical Centre Tracts 70, Mathemattsch Centmm, Amsterdam, 1976.
	12	Edsger W. Dijkstra, Guarded commands, nondeterminacy and formal derivation of programs, Communications of the ACM, v.18 n.8, p.453-457, Aug. 1975 [doi>10.1145/360933.360975]
	13	Samuel Eilenberg, Automata, Languages, and Machines, Academic Press, Inc., Orlando, FL, 1974
	14	ELOOT, C.C. Monadic computation and iterative algebraic theories. In Logic Co#oqumm "73, Studies in Logic 80, H.E. Rose aad~ J.C. Sh~epherdson, Eds., North Holland, Amsterdam, 1975, pp. 175-230.
	15	Joost Engelfriet, Simple Program Schemes and Formal Languages, Springer-Verlag New York, Inc., Secaucus, NJ, 1974
	16	GInali, S. Iterative algebraic theories, infinite trees, and program schemata. Ph.D. Dissertation, Univ. of Chicago, Chicago, Ill., 1976.
	17	Seymour Ginsburg , H. Gordon Rice, Two Families of Languages Related to ALGOL, Journal of the ACM (JACM), v.9 n.3, p.350-371, July 1962 [doi>10.1145/321127.321132]
	18	GOGtmN, J.A., TttA~cI~t, J.W, WAON~L, E G., AND W~GH'r, J.B. Some fundamentals of orderalgebraic semantics. In Mathematical Foundations of Computer ScJence, Lecture Notes in Computer Science 45, G. Goos and J. Hartmams, Eds., Springer-Verlag, Berlin, Hetdelberg, New York, 1976, pp. 153-168.
	19	J. A. Goguen , J. W. Thatcher , E. G. Wagner , J. B. Wright, Initial Algebra Semantics and Continuous Algebras, Journal of the ACM (JACM), v.24 n.1, p.68-95, Jan. 1977 [doi>10.1145/321992.321997]
	20	KAL~t~lq, R.E., FALe, P.L., ~.r~o ARBm, M A. Topics m Mathematical System Theory. McGraw-Hall, New York, 1969.
	21	KAmN, S. Rationalizing many-sorted algebratc theories. Res. Pep. RC7574, IBM Thomas J Watson Research Center, Yorktown Heights, N.Y., 1979.
	22	KARP, R,M. Some applications of logical syntax to digital computer programming. Ph.D. Dtssertation, Harvard Univ., Cambridge, Mass., 1959.
	23	Kleene~ Introductton to Maamathematics. Van Nostrand, 1952.
	24	KNASTER, B. Ula th6or~me sure les fonctions des ensembles. Ann. Soc. Polort Math. 6 (1928), 133--134.
	25	Luckham, D.C., PARK, D.M.R., AND P^rERSON, M S. On formalized computer programs. ~ Comput. Syst. ScL 4 (1970), 220-249.
	26	MANES, E.G. Partialty-addiuve semantics: A progress report. In Fundamentals of Computatwn Theory, FCT'79, L. Budach, F..d., Akademie-Verlag, Berlin, 1979, 279-290.
	27	Zohar Manna, Introduction to Mathematical Theory of Computation, McGraw-Hill, Inc., New York, NY, 1974
	28	Zohar Manna , Stephen Ness , Jean Vuillemin, Inductive methods for proving properties of programs, Communications of the ACM, v.16 n.8, p.491-502, Aug. 1973 [doi>10.1145/355609.362336]
	29	Mxhq~^, Z., AND Sn~tm, A. The convergence of functions to fixedpoints of recursive det'mitions. Theor. Comput. Set 6 (1978), 109-141.
	30	Robert Milne , C. Strachey, A Theory of Programming Language Semantics, Halsted Press, New York, NY, 1977
	31	Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
	32	SChutzenberger, M.P. On a theorem of R. Jungen. Proc. Amer. Math. So~., 1962.
	33	Scott, D. Outline of a mathematical theory of computation. Tech. Mon. PRG-2, Oxford Umv. Computing Laboratory, 1970.
	34	ScoTt, D. The lattice of flow diagrams. In Symposmm on Semantics of Algorithmic Languages, Lecture Notes in Mathematics 188, E. Engeler, Ed, Sprmger-Verlag, Berlin, Heidelberg, New York, 1971, pp. 311-366.
	35	ScoTT, D. Data types as lattices. SIAM 3:. Comput. 5 (1976), 523-587.
	36	STOY, J.E. Denotatwnal Semantics. MIT Press, Cambridge, Mass., 1977.
	37	Tarski, A. Lattice-theoretical fixpoint theorem and its applicauons. Proc. ~ Math. 5 (1955), 285-309.
	38	R. D. Tennent, The denotational semantics of programming languages, Communications of the ACM, v.19 n.8, p.437-453, Aug. 1976 [doi>10.1145/360303.360308]
	39	Truryn, J. Fixed-points and algebras wtth infinitely long expressions, II. In Fundamentals of Computation Theory, Lecture Notes in Computer Science 56, G. Goos and .t. Hartmanis, Eds., Springer-Verlag, Berlin, Heidelberg, New York, 1977, pp. 332-339.
	40	WAgner e.G., WRmtrr, J.B., Am) T~rcmn~, $.W. Many-sorted and ordered algebraic theories. Res. Pep. RC7595, IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y, 1979.
	41	WAND, M Fixed-point constructions in order-enriched categories Tech. Pep. 23, Computer Science Dep., Indiana Univ., Bloomington, Ind., 1977.
	42	H. Paul Zeiger, Formal models for some features of programming languages, Proceedings of the first annual ACM symposium on Theory of computing, p.211-215, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805435]

CITED BY 4

	Corrado Böhm, Combinatory foundation of functional programming, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.29-36, August 15-18, 1982, Pittsburgh, Pennsylvania, United States
	Richard B. Kieburtz, Precise typing of abstract data type specifications, Proceedings of the 10th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.109-116, January 24-26, 1983, Austin, Texas
	D. J. Cooke , M. H. J. Al-Noufaly, The programming language MINO and its formal definition, ACM SIGPLAN Notices, v.19 n.2, p.47-57, February 1984
	Michael Mislove , Dusko Pavlovic , James Worrell, Labelled Markov Processes as Generalised Stochastic Relations, Electronic Notes in Theoretical Computer Science (ENTCS), 172, p.459-478, April, 2007