Path: utzoo!ncc!alberta!ihnp4!ucbvax!ernie.Berkeley.EDU!jwl
From: jwl@ernie.Berkeley.EDU (James Wilbur Lewis)
Newsgroups: comp.theory
Subject: Re: automata
Keywords: classes of automata
Message-ID: <22899@ucbvax.BERKELEY.EDU>
Date: 6 Feb 88 04:54:30 GMT
References: <5409@burdvax.PRC.Unisys.COM>
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: jwl@ernie.Berkeley.EDU.UUCP (James Wilbur Lewis)
Organization: University of California, Berkeley
Lines: 27

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