[comp.theory] regularity conditions

varricchio%pc346%astrom.hepnet@VM1.NODAK.EDU (06/06/90)

It is well known that if a language L is accepted in linear time by a
deterministic one-tape Turing Machine then L is regular.(cf. Hennie F.
C. , One-tape off-line Turing Machine computations, Information and
Control, 1965,8:6, 553-578).
  I wonder whether the same result holds for languages accepted in linear
time by a non-deterministic one-tape Turing Machine.

                                     Stefano Varricchio
                                Dipartimento di Matematica
                                Universita dell`Aquila
                             67100 L`Aquila Italy.