Alternating multicounter machines with constant number of reversals
type: Item
instance of: scholarly article
title: Alternating multicounter machines with constant number of reversals
zbMATH Open document ID: 0579.68033
DOI: 10.1016/0020-0190(85)90100-0
author: Juraj Hromkovič
published in: Information Processing Letters
publication date: 1985-01-01T00:00:00Z
review text: The alternating multicounter machines with constant number of reversals are investigated in relation to Turing machines. It is shown that two-way and one-way versions of these machines working in polynomial time define precisely the class P of languages recognized by Turing machines in deterministic polynomial time. Further, it is proved that one-way alternating 4-counter machines with one reversal allowed for each counter are as powerful as Turing machines.
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3928352
zbMATH Keywords: alternation
zbMATH Keywords: multihead automata
zbMATH Keywords: Turing machines
zbMATH Keywords: polynomial time
MaRDI profile type: Publication
full work available at URL: 0020-0190(85)90100-0
OpenAlex ID: W2067825920
cites work: Alternation
cites work: Q4089754
cites work: The Hardest Context-Free Language
cites work: Remarks on the complexity of nondeterministic counter languages
cites work: Q3687716
cites work: Q3704912
cites work: Reversal-Bounded Multicounter Machines and Their Decision Problems
cites work: Alternating multihead finite automata
description: scientific article; zbMATH DE number 3928352