🚀 go-pugleaf

In article <5409@burdvax.PRC.Unisys.COM> dowding@macbeth.PRC.Unisys.COM (John Dowding) writes:
>
>Is there a name for the class of automata that only move
>left-to-right  through the  input string?   

Well, the complement of this class of automata are referred to as "two-way
automata" (as in 2DFA, 2NFA, 2PDA, etc..), so "one-way automata" would 
probably be OK (but redundant for most of these classes of machines).
There are classes of machines characterized as "one-way stack automata".

> What
>properties  does  the class  of languages  accepted by  this class of
>automata have?  

Well, to phrase it slightly differently:

2DFA's and 2NFA's both accept exactly the regular languages.

2DPDA's are known to accept non-CF languages (e.g. {0^n1^n2^n | n >= 1}).
Any language accepted by a 2DPDA is recognizable in linear time on a
computer.  As of 1979 (my edition of Hopcroft and Ullman), the existence 
of a CFL not accepted by a 2DPDA was an open question.

I don't know anything about "1TM"s....

-- Jim Lewis
   U.C. Berkeley