A Two-Way Automaton with Fewer States than Any Equivalent One-Way Automaton

1 April 1971

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. C-20 (4) , 474-475
https://doi.org/10.1109/T-C.1971.223273

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

MEMORY
CORRESPONDENCE
TAPES
STATES THAN
TWO WAY AUTOMATON
FEWER STATES
AUTOMATON WITH FEWER
THAN ANY EQUIVALENT

This publication has 0 references indexed in Scilit: