Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations

Research output: Contribution to journalArticle

8 Scopus citations

Abstract

R. Kannan conjectured that every non-deterministic two-way finite automaton can be positionally simulated by a deterministic two-way finite automaton. The conjecture is proved here by reduction to a similar problem about finite monoids. The method and the result are then generalized to alternating two-way finite automata, certain alternating one-tape linear-time Turing machines, and one-pebble automata.

Original languageEnglish (US)
Pages (from-to)154-179
Number of pages26
JournalJournal of Computer and System Sciences
Volume45
Issue number2
DOIs
StatePublished - Oct 1992
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Networks and Communications
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations'. Together they form a unique fingerprint.

  • Cite this