The Complexity of the Equivalence Problem for Simple Programs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The Complexity of the Equivalence Problem for Simple Programs

Full text

Pdf (1.39 MB)

Source

Journal of the ACM (JACM) archive
Volume 28 , Issue 3 (July 1981) table of contents

Pages: 535 - 560

Year of Publication: 1981

ISSN:0004-5411

Authors

Eitan M. Gurari	Department of Computer Science, SUNY at Buffalo, 4226 Ridge Lea Road, Amherst, New York
Oscar H. Ibarra	Department of Computer Science, University of Minnesota, 136 Lind Hall, Minneapolis, Minnesota

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	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/322261.322270 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	BAKER, B., AND BOOK, R. Reversal-bounded mulupushdown machines. J. Comput. Syst. Set. 8 (1974), 315-332.
	3	CHERNIAVSKY, J.C.Stmple programs realize exactly Presburger formulas. SlAM J. Comput 5 (1976), 666-677
	4	John C. Cherniavsky , Samuel N. Kamin, A Complete and Consistent Hoare Axiomatics for a Simple Programming Language, Journal of the ACM (JACM), v.26 n.1, p.119-128, Jan. 1979 [doi>10.1145/322108.322120]
	5	Robert L. Constable , Allan B. Borodin, Subrecursive Programming Languages, Part I: efficiency and program structure, Journal of the ACM (JACM), v.19 n.3, p.526-568, July 1972 [doi>10.1145/321707.321721]
	6	CONSTABLE, R.L., HUNT, H iii, AND SAHNI, S. On the computauonal complexity of scheme eqmvalence. Proc 8th Ann Prmceton Conf. on Information Sciences Systems, Princeton, N.J., 1974.
	7	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]
	8	M. J. Fischer , M. O. Rabin, SUPER-EXPONENTIAL COMPLEXITY OF PRESBURGER ARITHMETIC, Massachusetts Institute of Technology, Cambridge, MA, 1974
	9	GINSBURG, S, AND SPANIER, E.Semigroups, Presburger formulas, and languages. Pacific ~ Math. 16 (1966), 285-296
	10	GURARI, E M., AND IBARRA, O.H The complexity of the equwalence problem for two characterizauons of Presburger sets. Theol. Comput. Sc~. 13 (1981), 295-314
	11	HILBERT, D.Mathemausche Probleme. Vortrag, gehalten auf dem mternauonalen Mathemauker- Kongress zu Paris 1900. Nachr. Akad. Wiss Gottingen Math.-Phys. (1900), 253-297 {Enghsh translanon: Bull. Am Math. Soc. 8 (1901-1902), 437-479}
	12	Oscar H. Ibarra, Reversal-Bounded Multicounter Machines and Their Decision Problems, Journal of the ACM (JACM), v.25 n.1, p.116-133, Jan. 1978 [doi>10.1145/322047.322058]
	13	KARP, R Reducibility among combinatorial problems In Complexity of Computer Computatwns, R Miller and J. Thatcher, Eds., Plenum Press, New York, 1972, pp. 85-104.
	14	MATIIASEVIC, Y. Enumerable sets are Dlophantine. Dodl Akad. Nauk. SSSR 191 (1970), 279-282
	15	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]
	16	D. Tsichritzis, The Equivalence Problem of Simple Programs, Journal of the ACM (JACM), v.17 n.4, p.729-738, Oct. 1970 [doi>10.1145/321607.321621]

CITED BY 2

	Eitan M. Gurari, Decidable problems for powerful programs, Journal of the ACM (JACM), v.32 n.2, p.466-483, April 1985
	A. T. Berztiss, Data processing and computer science theory, ACM SIGCSE Bulletin, v.15 n.1, p.72-76, February 1983