<p>In a 1967 pager, Al Rosenberg gave the example of a language which is deterministic linear time but not deterministic quasi-realtime that Book &amp; Greibach probably refer to. 
Rosenberg mentions that such examples were published previously by himself and Cole.</p>

CC BY-SA 4.0
2019-08-12T20:42:02.620Z
2019-08-12T20:42:02.620Z
Yossi Gil
<p>Book and Greibach <a href="https://link.springer.com/content/pdf/10.1007%2FBF01705890.pdf" rel="nofollow noreferrer">(V. Book, Ronald &amp; A. Greibach, Sheila. (1970). Quasi-realtime languages. Theory of Computing Systems. 4. 97-111. 10.1007/BF01705890.)</a> prove that non-deterministic linear time Turing machines are equivalent to quasi-real-time such machines.</p>

<p>The authors say: " For deterministic machines, linear time is strictly more powerful than real-time; here we show that for nondeterministic machines linear time and real-time have the same power. "
However, they do not cite or prove the claim that linear time deterministic machines are more expressive than realtime deterministic such machines. </p>

<automata-theory>
Deterministic Realtime Languages
Yossi Gil
# Deterministic Realtime Languages

(Asked by: username_0 on 2019-08-12)

Book and Greibach [(V. Book, Ronald & A. Greibach, Sheila. (1970). Quasi-realtime languages. Theory of Computing Systems. 4. 97-111. 10.1007/BF01705890.)](https://link.springer.com/content/pdf/10.1007%2FBF01705890.pdf) prove that non-deterministic linear time Turing machines are equivalent to quasi-real-time such machines.

The authors say: " For deterministic machines, linear time is strictly more powerful than real-time; here we show that for nondeterministic machines linear time and real-time have the same power. "
However, they do not cite or prove the claim that linear time deterministic machines are more expressive than realtime deterministic such machines.

**Tags:** automata-theory

---

## 1 answers

### Answer by username_0 on 2019-08-12. Score: 3

In a 1967 pager, Al Rosenberg gave the example of a language which is deterministic linear time but not deterministic quasi-realtime that Book & Greibach probably refer to.
Rosenberg mentions that such examples were published previously by himself and Cole.


---

