Two-Way Counter Machines and Diophantine Equations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Two-Way Counter Machines and Diophantine Equations

Full text

Pdf (561 KB)

Source

Journal of the ACM (JACM) archive
Volume 29 , Issue 3 (July 1982) table of contents

Pages: 863 - 873

Year of Publication: 1982

ISSN:0004-5411

Authors

Eitan M. Gurari	Department of Computer Science, SUNY at Buffalo, 4226 Ridge Lea Road, Amherst, NY
Oscar H. Ibarra	Department of Computer Science, University of Minnesota, Minneapolis, MN

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 27, Citation Count: 7

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/322326.322340 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	DAvis, M., MATIJA~EVI~, Y, AND ROBINSON, J Hflbert's tenth problem. Dlophamme equations Posmve aspects of a negative solution, Proc Syrup. Pure Math 28 (1976), 323-378
	2	GINSBURG, S, AND SPANIER, E Bounded Algol-like languages Trans Am. Math Soc 113 (1964), 333-368
	3	GURARI, E.M Transducers with decidable equivalence problem TR-CS-79-4, University of Wisconsin, Milwaukee, Wis, 1979
	4	GURAR1. ~ M, AND IBARRA, O.H.Smaple counter machines and number-theoreuc problems ~ Comput. Syst Sct. 19 (1979), 145-162
	5	Eitan M. Gurari , Oscar H. Ibarra, An NP-Complete Number-Theoretic Problem, Journal of the ACM (JACM), v.26 n.3, p.567-581, july 1979 [doi>10.1145/322139.322152]
	6	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]
	7	LrvsmTz, L.The Diophantine problem for addition and dlvlmbdlty Trans. Am. Math. Soc, 235 (1978), 271-283
	8	LIPSHITZ, L Private communlcatton.
	9	MINSKY, M. Recursive unsolvabdtty of Post's problem of Tag astd other toptcs m the ~eory of Turmg machines. Ann. Math. 74 (1961), 437-455
	10	Rohit J. Parikh, On Context-Free Languages, Journal of the ACM (JACM), v.13 n.4, p.570-581, Oct. 1966 [doi>10.1145/321356.321364]

CITED BY 7

	Oscar H. Ibarra , Jianwen Su, On the containment and equivalence of database queries with linear constraints (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.32-43, May 11-15, 1997, Tucson, Arizona, United States
	Oscar H. Ibarra , Zhe Dang, On two-way FA with monotonic counters and quadratic Diophantine equations, Theoretical Computer Science, v.312 n.2-3, p.359-378, 30 January 2004
	Zhe Dang , Oscar H. Ibarra , Zhi-Wei Sun, On two-way nondeterministic finite automata with one reversal-bounded counter, Theoretical Computer Science, v.330 n.1, p.59-79, 31 January 2005
	Tomohiro Yamasaki , Hirotada Kobayashi , Hiroshi Imai, Quantum versus deterministic counter automata, Theoretical Computer Science, v.334 n.1-3, p.275-297, 11 April 2005
	H. Petersen, Two-way one-counter automata accepting bounded languages, ACM SIGACT News, v.25 n.3, p.102-105, Sept. 1994
	M. V. Panduranga Rao, Interference automata, Theoretical Computer Science, v.403 n.1, p.89-103, August, 2008
	Marius Bozga , Radu Iosif , Yassine Lakhnech, Flat Parametric Counter Automata, Fundamenta Informaticae, v.91 n.2, p.275-303, April 2009