Two-way automata with more than one storage medium
type: Item
instance of: scholarly article
title: Two-way automata with more than one storage medium
zbMATH Open document ID: 0604.68055
DOI: 10.1016/0304-3975(85)90142-2
author: Jörg Vogel
author: K. W. Wagner
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: This paper is concerned with the computational power of two-way automata with more than one subrecursive storage medium. Two-way automata with a stack (a nonerasing stack or a pushdown store, respectively) and an arbitrary number of checking stacks are of special interest. They are able to accept exactly those sets which are elementary in the sense of Kalmár. If the number of checking stacks is fixed, then the computational power of the corresponding restricted classes of automata can also be characterized in terms of time and space complexity classes.
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3976341
zbMATH Keywords: computational power of two-way automata
zbMATH Keywords: subrecursive storage medium
zbMATH Keywords: Two-way automata with a stack
zbMATH Keywords: checking stacks
zbMATH Keywords: complexity classes
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90142-2
OpenAlex ID: W2077637024
cites work: Time and tape complexity of pushdown automaton languages
cites work: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
cites work: Counter machines and counter languages
cites work: Two-way pushdown automata
cites work: Nonerasing stack automata
cites work: Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
cites work: Recursive unsolvability of Post's problem of ''Tag'' und other topics in theory of Turing machines
cites work: Classes of Predictably Computable Functions
description: scientific article; zbMATH DE number 3976341