2-WAY AUTOMATA AND LENGTH-PRESERVING HOMOMORPHISMS

Closure under length-preserving homomorphisms is interesting because o f its similarity to nondeterminism. We give a characterization of NP i n terms of length-preserving homomorphisms and present related complex ity results. However, we mostly study the case of two-way finite autom ata: Let l.p.hom[n state 2DFA] denote the class of languages that are length-preserving homomorphic images of languages recognized by n-stat e 2DFAs. We give a machine characterization of this class. We show tha t any language accepted by an n-state two-way alternating finite autom aton (2AFA), or by a 1-pebble 2NFA, belongs to l.p.hom[O(n(2)) state 2 DFA]. Moreover, there are languages in l.p.hom[n state 2DFA] whose sma llest accepting 2NFA has at least c(n) states (for some constant c > 1 ). So for two-way finite automata, the closure under length-preserving homomorphisms is much more powerful than nondeterminism. We disprove two conjectures (of Meyer and Fischer, and of Chrobak) about the state -complexity of unary languages. Finally, we show that the equivalence problems for 2AFAs (resp. 1-pebble 2NFAs) are in PSPACE, and that the equivalence problem for 1-pebble 2AFAs is in EXPSPACE (thus answering a question of Jiang and Ravikumar); it was known that these problems a re hard in these two classes. We also give a new proof that alternatin g 1-pebble machines recognize only regular languages (which was first proved by Goralcik et al.).