Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!tut.cis.ohio-state.edu!ucbvax!VM1.NODAK.EDU!varricchio%pc346%astrom.hepnet
From: varricchio%pc346%astrom.hepnet@VM1.NODAK.EDU
Newsgroups: comp.theory
Subject: regularity conditions
Message-ID: <9006052055.AA12840@irt.watson.ibm.com>
Date: 5 Jun 90 20:55:05 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Reply-To: varricchio%pc346%astrom.hepnet@VM1.NoDak.EDU
Lines: 11

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.