On the Complexity of Flowchart and Loop Program Schemes and Programming Languages

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the Complexity of Flowchart and Loop Program Schemes and Programming Languages

Full text

Pdf (934 KB)

Source

Journal of the ACM (JACM) archive
Volume 29 , Issue 1 (January 1982) table of contents

Pages: 228 - 249

Year of Publication: 1982

ISSN:0004-5411

Author

H. B. Hunt, III

Department of Computer Science, State University of New York at Albany, 1400 Washington Street, Albany, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 46, Citation Count: 2

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/322290.322304 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	CONSTABLE, R L, AND MUCHNICK, S.S Subrecurswe program schemata 1, II. J Comput. Syst Sct. 6 (1972), 480-537
	3	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	4	GAREY, M R., AND JOHNSON, D.S Computers and Intraenbday. Freeman, San Franctsco, 1979.
	5	Sheila A. Greibach, Theory of Program Structures: Schemes, Semantics, Verification, Springer-Verlag New York, Inc., Secaucus, NJ, 1985
	6	John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
	7	HUNT, H B III, CONSTABLE, R L, AND SAHNI, S On the computational complexity of program scheme equivalence SIAM J Comput 9 (1979), 396--416
	8	IANOV,On logical algorithm schemata C),bernettcs Problems I Pergamon Press, Helmsford, NY, 1958, pp 82-140 (English translation)
	9	IBARRA. O. Personal communication, October 1978
	10	Neil D. Jones , Steven S. Muchnick, Even Simple Programs Are Hard To Analyze, Journal of the ACM (JACM), v.24 n.2, p.338-350, April 1977 [doi>10.1145/322003.322016]
	11	LUCKHAM, D C, PARK, D M R., AND PATERSON, M.S On formahzed computer programs. J Comput Syst Scl 4 (1969), 220-249
	12	Zohar Manna, Introduction to Mathematical Theory of Computation, McGraw-Hill, Inc., New York, NY, 1974
	13	Albert R. Meyer , Dennis M. Ritchie, The complexity of loop programs, Proceedings of the 1967 22nd national conference, p.465-469, January 1967, Washington, D.C., United States [doi>10.1145/800196.806014]
	14	PATERSON, M S Equwalence problems in a model of computation Tech Memo No 1, Arttficlal Intelligence Lab, M IT, Cambridge, Mass, 1970

CITED BY 2

	P. A. Bloniarz , H. B. Hunt, III , D. J. Rosenkrantz, Algebraic Structures with Hard Equivalence and Minimization Problems, Journal of the ACM (JACM), v.31 n.4, p.879-904, Oct. 1984
	Lane A. Hemaspaandra , Mayur Thakur, Lower bounds and the hardness of counting properties, Theoretical Computer Science, v.326 n.1-3, p.1-28, 20 October 2004