Multi-tape and infinite-state automata

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Multi-tape and infinite-state automata—a survey

Full text

Pdf (1.20 MB)

Source

Communications of the ACM archive
Volume 8 , Issue 12 (December 1965) table of contents

Pages: 799 - 805

Year of Publication: 1965

ISSN:0001-0782

Author

Patrick C. Fischer

Harvard Univ., Cambridge, MA

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/365691.365962 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	ATRUBIN, A .J . An iterative one-dimensional real-time multiplier. Paper for Appl. Math., Harvard U., Cambridge, Mass., 1962. (ditto)
	2	AXT, P. On a subreeursive hierarchy and primitive reeursive degrees. Trans. Amer. Math. Soc. 92 (1959), 85-105.
	3	----. Enumeration and the Grzegorczyk hierarchy. Z. Math. Logik Grundlagen Math. 9 (1963), 53-65.
	4	BAR-HILLEL, Y. Language and Information. John Wiley, New York, 1964.
	5	----, PERLES, M., AND SHAMIR, E. Oil formal properties of simple phase structure grammars. Z. Phonetik, Sprachwiss. Kommunikationsforsch. 14 (1961), 143-172; also reprinted in {4}.
	6	BECVAR, J. ReaLtime and complexity problems in automata theory. Submitted for publication.
	7	BLUM. M., A inaehine-htdependent theory of reeursive functions. Doctoral thesis, Massachusetts Institute of Technology, Cambridge, Mass., 1964.
	8	CHOMSKY, N. On certain formal properties of grammars. Lnform. Contr. 2 (1959), 137-167.
	9	----. Formal properties of grammars. Hcndbook of Mathematical Psychology, Vol. 2. John Wiley, New York, 1963, 323-418.
	10	----. AND SCHUTZENBERGER, M. P . The algebraic theory of eontext-free languages. In Computer Programming and Forreal Systems, North-Holland, Amsterdam, 1963, 118-161.
	11	CLEAVE, J .P . A hierarchy of primitive reeursive functions. Z. Math. Logik Grunglagen Math. 9 (1963), 331-345.
	12	COLE, S .N . Real-time computation by iterative arrays of finite-state machines. Doctoral thesis, Rep. BL-36, Harvard U., Cambridge, Mass., 1964.
	13	DAVIS, M. Computability and Unsolvability. McGraw-Hill, New York, 1958.
	14	EGGAN, L .C . Transition graphs and the star-height of regular events. Mich. Math. J. 10 (1963), 385-397.
	15	ELGOT, C. C., AND MEZEI, J. E. On finite relations defined by generalized automata. IBM J. Res. Develop. 9 (1965), 47-68.
	16	Calvin C. Elgot , Abraham Robinson, Random-Access Stored-Program Machines, an Approach to Programming Languages, Journal of the ACM (JACM), v.11 n.4, p.365-399, Oct. 1964 [doi>10.1145/321239.321240]
	17	C. C. Elgot , J. D. Rutledge, RS -Machines with Almost Blank Tape, Journal of the ACM (JACM), v.11 n.3, p.313-337, July 1964 [doi>10.1145/321229.321235]
	18	EVEY, J. The theory and applications of pushdown-store machines. Doctoral thesis, Rep. NSF-1O, Harvard U., Cambridge, Mass., 1963.
	19	FABIAN, R .J . Hierarchies of general recursive functions and ordinal reeursion. Tech. Rep., Case Institute of Technology, Clevehmd, Ohio, 1964.
	20	FISCHER, P. C. Theory of provable reeursive functions. Trans. Amer. Math. Soc. 117 (1965), 494-520.
	21	---- . On computability by certain classes of restricted Turing machines. Prec. Fourth Ann. Symp. Switching Circult Theory and Logical Design, Chicago, 1963, pp. 23-32.
	22	Patrick C. Fischer, Generation of Primes by a One-Dimensional Real-Time Iterative Array, Journal of the ACM (JACM), v.12 n.3, p.388-394, July 1965 [doi>10.1145/321281.321290]
	23	Patrick C. Fischer, On Formalisms for Turing Machines, Journal of the ACM (JACM), v.12 n.4, p.570-580, Oct. 1965 [doi>10.1145/321296.321308]
	24	----. AND ROSENBERG, A. L. Further results on nondeterministic n-tape automata. Abstr. 65T-48, Amer. Math. Soc. Notices 12 (1965), 139-140.
	25	Seymour Ginsburg, Introduction to Mathematical Machine Theory, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1982
	26	---- AND GREIBACH, S. Deterministic context-free languages. Abstr. 65T-.155, Amer. Math. Soc. Notices 12 (1965), 246.
	27	---- AND SPANIER. E .H . Mappings of languages by two-tape devices. Proe. Fifth Ann. Syrup. Switching Circuit Theory and Logical Design, Princeton, 1964, pp. 57-67.
	28	GRZEGORCZYK, A, Solile classes of recursive functions, in Rozprawy Matematcyzne. Warsaw, 1953, pp. 1-45.
	29	HAINES, L. Generation and recognition of formal languages. Doctoral thesis, Massachusetts Institute of Technology, Cambridge, Mass., 1965.
	30	HARTMANIS, J., LEWIS, P. M., AND STEARNS, R. E. Classifications of computations by time and memory requirements. Prec. IFIP Int. Congr. Vol. 1, 1965, pp. 31-36.
	31	----. AND STEARNS, R. E. On the computational complexity of algorithms. Trans. Amer, Math. Soc. 117 (1965), 285-306.
	32	HENNIE, F. C. Iterative Arrays of Logical Circuits. MIT Press, Cambridge, Mass., 1961.
	33	----. One-tape off line Turing machine computations. Submitted for publication.
	34	---- AND STEARNS, R. E. Two tape simulation of multitape Turing machines. Submitted for publication.
	35	KLEENE, S. C. Introduction to Metamathematics. Van Nostrand, Princeton, N. J., 1952.
	36	----. Representation of events in nerve nets and finite automata. In C. E. Shannon and J. McCarthy (Eds.), Automata Studies, pp. 3-41, Princeton U. Press, Princeton, N. J., 1956.
	37	KREIDER, D. L., aND RITCHIE, R.W. Predictably computable functionals and definition by reeursion. Z. Math. Logik Grundlagen Math. 10 (1964), 65-80.
	38	---- AND ----. A universal two-way automaton. Submitted for publication.
	39	KURODA, S.-Y. Classes of languages and linear bounded automata, lnformat. Contr. 7 (1964), 207-223.
	40	LANDWEBER, P.S. Three theorems on phase structure grammars of Type I. Informat. Contr. 6 (1963), 131-137.
	41	C. Y. Lee, Categorizing Automata by W-Machine Programs, Journal of the ACM (JACM), v.8 n.3, p.384-399, July 1961 [doi>10.1145/321075.321082]
	42	McNAUGHTON, R. The theory of automata, a survey. In Advances in Computers, Vol. 2. Academic Press, New York, 1961, 379 421.
	43	MEYER, A.M. Depth of nesting and the Grzegorczyk hierarchy. Abstr. 622-56, Amer. Math. Soc. Notices 13 (1965), 342.
	44	MINSKY, M. L. Recursive unsolvability of Post's problem of tag and other topics in theory of Turing machines. Ann. Math. 74 (1961), 437-455.
	45	Edward F. Moore, Sequential Machines: Selected Papers, Addison-Wesley Longman Ltd., Essex, UK, 1964
	46	MYHILL, J. Linear bounded automata. Wadd Tech. Note 60-165, Wright-Patterson AFB, Ohio, 1960.
	47	OETTINGER, A. G. Automatic syntactic analysis and the pushdown store. Prec. Syrup. Appl. Math., Voh 12, Amer. Math. See. Providence, R. I., 1961.
	48	PAPERT, S., AND McNAUGHTON, R. On topological events. Submitted for publication.
	49	PERLES, M., RABIN, M. O., AND SHAMIR, E. Theory of definite antomata. IEEE Trans. EC-12 (1963), 233-243.
	50	RABIN, M. O. Real-time computation. Israel J. Math. 1 (1963), 203-211.
	51	---- AND SCOTT, D. Finite automata and their decision problems. IBM J. Reg. Develop. 3 (1959), 115-125.
	52	RITCHIE, D. M. Complexity classification ef primitive reeursive functions by their machine programs. Abstr. 622-59, Amer. Math. Soc. Notices 13 (1965), 343.
	53	RITCHIE, R. W. Classes of predictably computable functions. Trans. Amer. Math. Soc. 106 (1963), 139-173.
	54	ROSENBERG, A. L. On n-tape finite-state acceptors. Proe. Fifth Mm. Syrup. Switehitlg Cireuit Theory and Logical Design, Princeton, 1964, pp. 76 -81.
	55	SCHEINBERG, S. Note on the Boolean properties of contextfree languages. Inform. Contr. 3 (1960), 372-375.
	56	SCHUTZENBERGER, M. P. A remark on finite transducers. Inform,. Contr. 4 (1961), 185-196.
	57	----. On the definition of a family of automaea. Inform. Contr. 4 (1961), 245-270.
	58	----. Finite counting automata. Inform. Contr. 5 (1962), 91-107.
	59	----. Certain elementary families of automata. Proc. Syrup. Mathematical Theory of Automata, Polyteeh. Inst. of Brooklyn, 1962, 139-154.
	60	----. On context-tree languages and pushdown automata. Inform, Contr. 6 (1963), 246-264.
	61	J. C. Shepherdson , H. E. Sturgis, Computability of Recursive Functions, Journal of the ACM (JACM), v.10 n.2, p.217-255, April 1963 [doi>10.1145/321160.321170]
	62	SIEGEL, J. Some theorems about Yamada's restricted class of recursive functions. IBM Res. Pap. RC-510, T. J. Watson Iles. Ctr., Yorktown Hts., N. Y., 1961.
	63	TRAHTENBROT, B, A. Turing computations with logarithmic delay. Algebra i logika 8 (1964), 33-48 (in Russian).
	64	TURING, A.M. On computable numbers, with an application to the Entscheidlmgsproblem. Pron. Londmt Math. Son., Ser. 2-42, 1936, 230-265.
	65	Hao Wang, A Variant to Turing's Theory of Computing Machines, Journal of the ACM (JACM), v.4 n.1, p.63-92, Jan. 1957 [doi>10.1145/320856.320867]
	66	YAMADA, H. Counting by a class of growing automata. Doctoral thesis, U. of Pennsylvania, Philadelphia, Pa., 1960.
	67	----. Real-time computation and recursive functions not real-time computable. IRE Trans. EC-11 (1962), 753-760.

CITED BY 5

	William F. Atchison , Samuel D. Conte , John W. Hamblen , Thomas E. Hull , Thomas A. Keenan , William B. Kehl , Edward J. McCluskey , Silvio O. Navarro , Werner C. Rheinboldt , Earl J. Schweppe , William Viavant , David M. Young, Jr., Curriculum 68: Recommendations for academic programs in computer science: a report of the ACM curriculum committee on computer science, Communications of the ACM, v.11 n.3, p.151-197, March 1968
	J. Hartmanis , J. E. Hopcroft, An Overview of the Theory of Computational Complexity, Journal of the ACM (JACM), v.18 n.3, p.444-475, July 1971
	William F. Atchison , Samuel D. Conte , John W. Hamblen , Thomas E. Hull , Thomas A. Keenan , William B. Kehl , Edward J. McCluskey , Silvio O. Navarro , Werner C. Rheinboldt , Earl J. Schweppe , William Viavant , David M. Young, Jr., Curriculum 68: Recommendations for academic programs in computer science: a report of the ACM curriculum committee on computer science, Communications of the ACM, v.11 n.3, p.151-197, March 1968
	George Anton Kiraz, Multitiered nonlinear morphology using multitape finite automata: a case study on Syriac and Arabic, Computational Linguistics, v.26 n.1, p.77-105, March 2000
	Michal Armoni , Mordechai Ben-Ari, The concept of nondeterminism: its development and implications for teaching, ACM SIGCSE Bulletin, v.41 n.2, June 2009