On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
type: Item
instance of: scholarly article
title: On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
zbMATH Open document ID: 1069.68061
author: Pavol Ďuriš
author: Juraj Hromkovič
author: Katsushi Inoue
published in: Journal of Computer and System Sciences
publication date: 2004-08-10T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q10
zbMATH DE Number: 2085641
zbMATH Keywords: Two-dimensional finite automata
zbMATH Keywords: Las Vegas randomization
zbMATH Keywords: Nondeterminism
zbMATH Keywords: Complexity
MaRDI profile type: Publication
full work available at URL: j.jcss.2003.11.007
OpenAlex ID: W2091661846
cites work: Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations
cites work: Exact lower time bounds for computing Boolean functions on CREW PRAMs
cites work: Classes of bounded nondeterminism
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: On measuring nondeterminism in regular languages
cites work: On the relation between ambiguity and nondeterminism in finite automata
cites work: Lower bounds for language recognition on two-dimensional alternating multihead machines
cites work: Q4337605
cites work: Q4788609
cites work: Q2754144
cites work: Q4501529
cites work: Q4228510
cites work: Q4938639
cites work: Two-dimensional alternating turing machines with only universal states
cites work: Non-deterministic communication complexity with few witnesses
cites work: Q4258580
cites work: Communication Complexity
cites work: Amounts of nondeterminism in finite automata
cites work: Amplification of slight probabilistic advantage at absolutely no cost in space
cites work: Communication complexity
cites work: Q4418659
DOI: 10.1016/J.JCSS.2003.11.007
description: scientific article; zbMATH DE number 2085641