Title :
A Two-Way Automaton with Fewer States than Any Equivalent One-Way Automaton
fDate :
4/1/1971 12:00:00 AM
Abstract :
This correspondence presents an example of a two-way automaton which has significantly fewer states than any one-way automaton accepting the same set of tapes. Thus, in this particular case, memory space can be saved by using a two-way automaton. This savings in space, however, is accompanied by an increase in recognition time.
Keywords :
Finite automaton, one-way automaton, regular sets, two-way automaton.; Ash; Automata; Circuits and systems; Codes; Decoding; Error correction; Hamming distance; Information theory; Laboratories; Upper bound; Finite automaton, one-way automaton, regular sets, two-way automaton.;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/T-C.1971.223273
