On probabilistic pushdown automata
type: Item
instance of: scholarly article
title: On probabilistic pushdown automata
zbMATH Open document ID: 1205.68202
author: Juraj Hromkovič
author: Georg Schnitger
published in: Information and Computation
publication date: 2010-08-19T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q87
zbMATH DE Number: 5773136
zbMATH Keywords: pushdown automata
zbMATH Keywords: determinism
zbMATH Keywords: nondeterminism
zbMATH Keywords: randomization
MaRDI profile type: Publication
full work available at URL: j.ic.2009.11.001
OpenAlex ID: W2140852079
cites work: Exact lower time bounds for computing Boolean functions on CREW PRAMs
cites work: On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata
cites work: Language recognition using probabilistic Turing machines in real time, and automata with a push-down store
cites work: Projections of languages recognizable by probabilistic and alternating finite multitape automata
cites work: Q5592246
cites work: Q4337605
cites work: Q4788609
cites work: On the power of Las Vegas II: Two-way finite automata
cites work: On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata
cites work: Q4737913
cites work: Q4449165
cites work: The Probabilistic Communication Complexity of Set Intersection
cites work: Communication Complexity
cites work: Properties of probabilistic pushdown automata
cites work: On the distributional complexity of disjointness
cites work: On the size of randomized OBDDs and read-once branching programs for \(k\)-stable functions
DOI: 10.1016/J.IC.2009.11.001
description: scientific article; zbMATH DE number 5773136