Real-Time Definable Languages
- 1 October 1967
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 14 (4) , 645-662
- https://doi.org/10.1145/321420.321423
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.Keywords
This publication has 4 references indexed in Scilit:
- Ambiguity in context free languagesJournal of the ACM, 1966
- Classes of languages and linear-bounded automataInformation and Control, 1964
- Quotients of Context-Free LanguagesJournal of the ACM, 1963
- A variant of a recursively unsolvable problemBulletin of the American Mathematical Society, 1946