4
$\begingroup$

Book and Greibach (V. Book, Ronald & A. Greibach, Sheila. (1970). Quasi-realtime languages. Theory of Computing Systems. 4. 97-111. 10.1007/BF01705890.) 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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.