## Abstract

Closure under length-preserving homomorphisms is interesting because of its similarity to nondeterminism. We give a characterization of NP in terms of length-preserving homomorphisms and present related complexity results. However, we mostly study the case of two-way finite automata: Let l.p.hom[n state 2DFA] denote the class of languages that are length-preserving homomorphic images of languages recognized by n-state 2DFAs. We give a machine characterization of this class. We show that any language accepted by an n-state two-way alternating finite automaton (2AFA), or by a 1-pebble 2NFA, belongs to l.p.hom[O(n^{2}) state 2DFA]. Moreover, there are languages in l.p.hom[n state 2DFA] whose smallest 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 are hard in these two classes. We also give a new proof that alternating 1-pebble machines recognize only regular languages (which was first proved by Goralčik et al.).

Original language | English (US) |
---|---|

Pages (from-to) | 191-226 |

Number of pages | 36 |

Journal | Mathematical Systems Theory |

Volume | 29 |

Issue number | 3 |

State | Published - May 1996 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- General Mathematics
- Computational Theory and Mathematics