Reversal-bounded nondeterministic multicounter machines and complementation
type: Item
instance of: scholarly article
title: Reversal-bounded nondeterministic multicounter machines and complementation
zbMATH Open document ID: 0631.68069
DOI: 10.1016/0304-3975(87)90040-5
author: Juraj Hromkovič
published in: Theoretical Computer Science
publication date: 1987-01-01T00:00:00Z
review text: It is proved, for any function \(f(n)=o(n)\) and any function \(\g(n)geq n\), that the family of languages recognized by one-way \(\g(n)\)-time bounded nondeterministic multicounter machines with \(f(n)\) counter reversals is not closed under complementation. Considering real-time and constant number of reversals this solves an open problem of \textit{K. Wagner} and \textit{G. Wechsung} [Computational complexity. Berlin: VEB Deutscher Verlag der Wissenschaften (1986; Zbl 0584.68062)].
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 4026855
zbMATH Keywords: nondeterminism
zbMATH Keywords: closure properties
zbMATH Keywords: reversal complexity
zbMATH Keywords: nondeterministic multicounter machines
MaRDI profile type: Publication
full work available at URL: 0304-3975(87)90040-5
OpenAlex ID: W2053405063
cites work: On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store
cites work: One-way simple multihead finite automata are not closed under concatenation
cites work: Q4089754
cites work: Remarks on blind and partially blind one-way multicounter machines
cites work: Q3704912
cites work: Q3702514
cites work: Q3742753
cites work: Reversal-Bounded Multicounter Machines and Their Decision Problems
cites work: Q3707407
description: scientific article; zbMATH DE number 4026855