Abstract
The quasi-realtime languages are seen to be the languages accepted by nondeterministic multitape Turing machines in real time. The family of quasi-realtime languages forms an abstract family of languages closed under intersection, linear erasing, and reversal. It is identical with the family of languages accepted by nondeterministic multitape Turing machines in linear time. Every quasi-realtime language can be accepted in real time by a nondeterministic one stack, one pushdown store machine, and can be expressed as the length-preserving homomorphic image of the intersection of three context-free languages.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R. Book, Grammars with time functions, Dissertation, Harvard University, 1969. Also appears as Mathematical Linguistics and Automatic Translation, Report No. NSF-23, The Computation Laboratory, Harvard University, 1969.
N. Chomsky andM. P. Schützenberger, The algebraic theory of context-free languages,Computer Programming and Formal Systems, North Holland, Amsterdam, 1963.
J. Evey, The theory and application of pushdown store machines, Dissertation, Harvard University, 1963. Also appears as Mathematical Linguistics and Automatic Translation, Report No. NSF-10, The Computation Laboratory, Harvard University, 1963.
M. Fischer, Private communication.
P. C. Fischer, Turing machines with restricted memory access,Information and Control 9 (1966), 364–379.
P. C. Fischer, A. R. Meyer andA. L. Rosenberg, Counter machines and counter languagesMath. Systems Theory 2 (1968), 265–283.
S. Ginsburg,The Mathematical Theory of Context-Free Languages, McGraw-Hill, New York, 1966.
S. Ginsburg andS. A. Greibach, Abstract families of languages,Mem. Amer. Math. Soc., to appear.
S. Ginsburg andS. A. Greibach, Multitape abstract families of automata, in preparation.
S. Ginsburg andS. A. Greibach, Principal AFL, in preparation.
S. Ginsburg, S. A. Greibach andM. A. Harrison, One-way stack automata,J. Assoc. Comput. Mach. 14 (1967), 389–418.
S. Ginsburg andM. A. Harrison, One-way nondeterministic real-time list-storage languages,J. Assoc. Comput. Mach. 15 (1968), 428–446.
S. A. Greibach, Inverses of phrase structure generators, Dissertation, Harvard University, 1963. Also appears as Mathematical Linguistics and Automatic Translation, Report No. NSF-11, The Computation Laboratory, Harvard University, 1963.
S. A. Greibach, An infinite hierarchy of context-free languages,J. Assoc. Comput. Mach. 16 (1969), 91–106.
S. A. Greibach andJ. E. Hopcroft, Scattered context grammars,J. Comput. System Sci. 3 (1969), 233–247.
J. Hartmanis andR. E. Stearns, On the computational complexity of algorithms,Trans. Amer. Math. Soc. 117 (1965), 285–306.
J. E. Hopcroft andJ. D. Ullman, An approach to a unified theory of automata,Bell System Tech. J. 46 (1967), 1793–1829.
A. R. Meyer, A. L. Rosenberg andP. C. Fischer, Multitape simulation of multihead Turing machines, IBM Research Report RC 1891, 15 August 1967.
A. L. Rosenberg, Real-time definable languages,J. Assoc. Comput. Mach. 14 (1967), 645–662.
Author information
Authors and Affiliations
Additional information
The research reported in this paper was announced at the ACM Symposium on the Theory of Computing, Marina del Rey, California, May, 1969. This research has been supported in part by Air Force Cambridge Research Laboratories, Office of Aerospace Research, USAF, under Contract F19628-68-C-0029.
Rights and permissions
About this article
Cite this article
Book, R.V., Greibach, S.A. Quasi-realtime languages. Math. Systems Theory 4, 97–111 (1970). https://doi.org/10.1007/BF01705890
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01705890