Real-Time Definable Languages

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Real-Time Definable Languages

Full text

Pdf (1.10 MB)

Source

Journal of the ACM (JACM) archive
Volume 14 , Issue 4 (October 1967) table of contents

Pages: 645 - 662

Year of Publication: 1967

ISSN:0004-5411

Author

Arnold L. Rosenberg

IBM Watson Research Center, Yorktown Heights, New York

Publisher

ACM New York, NY, USA

Bibliometrics

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

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

ABSTRACT

The closure properties of the class of languages defined by real-time, online, multi-tape Turing machines are proved. The results obtained are, for the most part, negative and, as one would expect, asymmetric. It is shown that the results remain valid for a broad class of real-time devices. Finally, the position of the class of real-time definable languages in the “classical” linguistic hierarchy is established.

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	COLE, S.N. real-time computation by iterative arrays of finite-state machines. Doctoral thesis, Rep. BL-36 by Staff of ttarvard Computation Lab. to Bell Telephone Labs., 1964.
	2	GlNSBURG S., aND GREBACH, S. A. DeterraiIlistic context free languages. IEEE Conference Record on Switching Circuit Theory and Logical Design, IEEE Pub. 16C13, 1965, pp. 293-220
	3	Seymour Ginsburg , Edwin H. Spanier, Quotients of Context-Free Languages, Journal of the ACM (JACM), v.10 n.4, p.487-492, Oct. 1963 [doi>10.1145/321186.321191]
	4	Seymour Ginsburg , Joseph Ullian, Ambiguity in context free languages, Journal of the ACM (JACM), v.13 n.1, p.62-89, Jan. 1966 [doi>10.1145/321312.321318]
	5	HARTMANIS, J,, AND STEARNS, R. E. On the computational complexity of algorithms. Trans. Amer. Mash. Soc. 117, 5 (May 1965), 285-306
	6	KuRoDA, S, Classes of lANguages and linear-boutded automata. Inform. and Contr. 7 (1964) 207-223
	7	PosT E. A variant of a recursively unsolvable problern. Bull. Amer. Math. Soc. 82 (1946), 264.-268.
	8	RABIN, M. O, Real time computation. Israel J. Math. I (1963), 203-211.
	9	ROSENBERG, A.L. On the nonelosure of the real-time definable sets under concatenation, closure, ad reversal. IBM Res. Rep RC-1572, 1966.
	10	---. A remark on real-time definable languages. IBM Res. Note NC-616, 1966.

CITED BY 12

	Chandra M. R. Kintala , Patrick C. Fischer, Computations with a restricted number of nondeterministic steps (Extended Abstract), Proceedings of the ninth annual ACM symposium on Theory of computing, p.178-185, May 04-04, 1977, Boulder, Colorado, United States
	Patrick C. Fischer , Albert R. Meyer , Arnold L. Rosenberg, Real-Time Simulation of Multihead Tape Units, Journal of the ACM (JACM), v.19 n.4, p.590-607, Oct. 1972
	Seymour Ginsburg , Michael A. Harrison, One-way nondeterministic real-time list-storage languages, Journal of the ACM (JACM), v.15 n.3, p.428-446, July 1968
	Sheila A. Greibach, Jump PDA's, deterministic context-free languages principal AFDLs and polynomial time recognition—(Extended Abstract), Proceedings of the fifth annual ACM symposium on Theory of computing, p.20-28, April 30-May 02, 1973, Austin, Texas, United States
	Ronald V. Book , Sheila A. Greibach, Quasi-realtime languages (Extended Abstract), Proceedings of the first annual ACM symposium on Theory of computing, p.15-18, May 05-07, 1969, Marina del Rey, California, United States
	Sheila A. Greibach, An Infinite Hierarchy of Context-Free Languages, Journal of the ACM (JACM), v.16 n.1, p.91-106, Jan. 1969
	Arnold L. Rosenberg, On the Independence of Real-Time Definability and Certain Structural Properties of Context-Free Languages, Journal of the ACM (JACM), v.15 n.4, p.672-679, Oct. 1968
	Ronald V. Book , Sheila A. Greibach , Ben Wegbreit, Tape- and time-bounded Turing acceptors and AFLs (Extended Abstract), Proceedings of the second annual ACM symposium on Theory of computing, p.92-99, May 04-06, 1970, Northampton, Massachusetts, United States
	Véronique Terrier, Characterization of real time iterative array by alternating device, Theoretical Computer Science, v.290 n.3, p.2075-2084, 3 January 2003
	Martin Kutrib, Refining nondeterminism below linear time, Journal of Automata, Languages and Combinatorics, v.7 n.4, p.533-547, September 2002
	Andreas Klein , Martin Kutrib, Deterministic Turing machines in the range between real-time and linear-time, Theoretical Computer Science, v.289 n.1, p.253-275, 23 October 2002
	Patrick C. Fischer, Theory of computing in computer science education, Proceedings of the November 16-18, 1971, fall joint computer conference, November 16-18, 1971, Las Vegas, Nevada