Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations
type: Item
instance of: scholarly article
title: Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations
zbMATH Open document ID: 0769.68019
DOI: 10.1016/0022-0000(92)90045-K
published in: Journal of Computer and System Sciences
publication date: 1993-01-17T00:00:00Z
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 20M35
zbMATH DE Number: 97374
zbMATH Keywords: non-deterministic two-way finite automaton
zbMATH Keywords: deterministic two-way finite automaton
zbMATH Keywords: finite monoids
zbMATH Keywords: alternating two-way finite automata
zbMATH Keywords: alternating one-tape linear-time Turing machines
zbMATH Keywords: one-pebble automata
Wikidata QID: Q123298544
author: J.-C. Birget
MaRDI profile type: Publication
cites work: Arbitrary vs. regular semigroups
cites work: Concatenation of inputs in a two-way automaton
cites work: On equations for regular languages, finite automata, and sequential networks
cites work: Alternation
cites work: Q4198056
cites work: Q4133162
cites work: One-tape, off-line Turing machine computations
cites work: Q3862379
cites work: Alternating Pushdown and Stack Automata
cites work: Q3741089
cites work: Q5526130
cites work: Q5541340
cites work: Nondeterminism and the size of two way finite automata
full work available at URL: 0022-0000(92)90045-k
OpenAlex ID: W2079856360
description: scientific article; zbMATH DE number 97374