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

Jean Camille Birget

doi:10.1016/0022-0000(92)90045-K

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

Jean Camille Birget

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	154-179
Number of pages	26
Journal	Journal of Computer and System Sciences
Volume	45
Issue number	2
DOIs	https://doi.org/10.1016/0022-0000(92)90045-K
State	Published - Oct 1992

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1016/0022-0000(92)90045-K

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

@article{509ab6c5d63344999dad0dea83eea155,

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

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.",

author = "Birget, {Jean Camille}",

year = "1992",

month = oct,

doi = "10.1016/0022-0000(92)90045-K",

language = "English (US)",

volume = "45",

pages = "154--179",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Positional simulation of two-way automata

T2 - Proof of a conjecture of R. Kannan and generalizations

AU - Birget, Jean Camille

PY - 1992/10

Y1 - 1992/10

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0026940235&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026940235&partnerID=8YFLogxK

U2 - 10.1016/0022-0000(92)90045-K

DO - 10.1016/0022-0000(92)90045-K

M3 - Article

AN - SCOPUS:0026940235

VL - 45

SP - 154

EP - 179

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

IS - 2

ER -