Decidable Properties of Monadic Functional Schemas

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Decidable Properties of Monadic Functional Schemas

Full text

Pdf (711 KB)

Source

Journal of the ACM (JACM) archive
Volume 20 , Issue 3 (July 1973) table of contents

Pages: 489 - 499

Year of Publication: 1973

ISSN:0004-5411

Authors

Edward Ashcroft	Computer Science Department, University of Waterloo, Waterloo, Ontario, Canada
Zohar Manna	Applied Mathematics Department, The Weizmann Institute of Science, Rehovot, Israel and Stanford University, Stanford, California
Amir Pnueli	Applied Mathematics Department, The Weizmann Institute of Science, Rehovot, Israel

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 17, Citation Count: 7

Additional Information:

abstract 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/321765.321780 What is a DOI?

ABSTRACT

A class of (monadic) functional schemas which properly includes “Ianov” flowchart schemas is defined. It is shown that the termination, divergence, and freedom problems for functional schemas are decidable. Although it is possible to translate a large class of non-free functional schemas into equivalent free functional schemas, it is shown that in general this cannot be done. It is also shown that the equivalence problem for free functional schemas is decidable. Most of the results are obtained from well-known results in formal languages and automata theory.

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	DEBAKKER, J. W , AND SCOTT, D A theory of programs Unpub. notes, IBM Seminar, Vienna, Austria, Aug. 1969
	2	John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
	3	IANOV, Y I The logical schemes of algorithms In Problems zn Cybernetics, Vol. I, A. A. Lyapunov, it Goodman, and A D. Booth (Eds), Pergamon Press, New York, 1960, pp. 82-140.
	4	~ORENJAK, A J , AND HOPCROI~T, J E Simple deterministic languages IEEE Seventh Annual Symp on Switching and Automata Theory, U oi Cahforma at Berkeley, 1966, pp. 36-46.
	5	LUCKHAM, D. C , PARK, D. M R , AND PATERSON, M S. On formahzed computer programs J Comput and Syst. Scz ~, 3 (June 1970), 220-249.
	6	McCARTHY, J. A basis for a mathematical theory of computation. In Computer Programm~g and Formal Systems, P. Braffort and D Hirschberg (Eds)., North-Holland Pub. Co , Amsterdam, 1963, pp 33-70.
	7	PATFRSON, M. S A szmple monadzc recurslve schema which is not equivalent to any program schema. Unpub memo, MIT, Project MAC, Dec 1970.
	8	I~OSENKRANTZ, D. J, AND STE ~RNS, 1~. E. Propertms oi deterministic top-down grammars. Inform and Contr. I7 (1970), 226-256
	9	J. D. Rutledge, On Ianov's Program Schemata, Journal of the ACM (JACM), v.11 n.1, p.1-9, Jan. 1964 [doi>10.1145/321203.321204]

CITED BY 7

	A. V. Aho , S. C. Johnson , J. D. Ullman, Deterministic parsing of ambiguous grammars, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-21, October 01-03, 1973, Boston, Massachusetts
	Ashok K. Chandra, On the decision problems of program schemas with commutative and invertible functions, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.235-242, October 01-03, 1973, Boston, Massachusetts
	H. B. Hunt, III , D. J. Rosenkrantz, Efficient algorithms for structural similarity of grammars, Proceedings of the 7th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.213-219, January 28-30, 1980, Las Vegas, Nevada
	Ashok K. Chandra, Degrees of translatability and canonical forms in program schemas: Part I, Proceedings of the sixth annual ACM symposium on Theory of computing, p.1-12, April 30-May 02, 1974, Seattle, Washington, United States
	H. B. Hunt, III , D. J. Rosenkrantz, Computational parallels between the regular and context-free languages, Proceedings of the sixth annual ACM symposium on Theory of computing, p.64-74, April 30-May 02, 1974, Seattle, Washington, United States
	Michael A. Arbib , Ernest G. Manes, The Pattern-of-Calls Expansion Is the Canonical Fixpoint for Recursive Definitions, Journal of the ACM (JACM), v.29 n.2, p.577-602, April 1982
	Serge Abiteboul , Paris C. Kanellakis , Emmanuel Waller, Method schemas, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.16-27, April 02-04, 1990, Nashville, Tennessee, United States