Two-way automata and length-preserving homomorphisms

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

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 1.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 1.p.hom[O(n2) state 2DFA]. Moreover, there are languages in I.p.hom[n state 2DFA] whose smallest accepting 2NFA has at least cn 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 2 AFAs (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čík et al.).

Original languageEnglish (US)
Pages (from-to)191-226
Number of pages36
JournalTheory of Computing Systems
Volume29
Issue number3
DOIs
StatePublished - 1996
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Two-way automata and length-preserving homomorphisms'. Together they form a unique fingerprint.

Cite this