Properties of probabilistic pushdown automata
type: Item
instance of: scholarly article
title: Properties of probabilistic pushdown automata
zbMATH Open document ID: 0912.68136
DOI: 10.1016/S0304-3975(98)00059-0
author: Ioan I. Macarie
author: Ogihara, Mitsunori
published in: Theoretical Computer Science
publication date: 1999-01-12T00:00:00Z
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1238734
zbMATH Keywords: pushdown automata
zbMATH Keywords: probabilistic computation
zbMATH Keywords: models of computation
zbMATH Keywords: space-bounded computation
zbMATH Keywords: Arthur-Merlin games
zbMATH Keywords: games against nature
MaRDI profile type: Publication
cites work: Depth reduction for noncommutative arithmetic circuits
cites work: On relativizing auxiliary pushdown machines
cites work: Alternation
cites work: Q5536271
cites work: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
cites work: Q4145647
cites work: Computational Complexity of Probabilistic Turing Machines
cites work: On non-determinacy in simple computing devices
cites work: Q3862379
cites work: Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
cites work: Alternating multihead finite automata
cites work: Alternating Pushdown and Stack Automata
cites work: On the structure of log-space probabilistic complexity classes
cites work: Multihead two-way probabilistic finite automata
cites work: Transformational methods and their application to complexity problems. Corrigenda
cites work: Tree-size bounded alternation
cites work: On tape-bounded complexity classes and multihead finite automata
cites work: On the Tape Complexity of Deterministic Context-Free Languages
cites work: Properties that characterize LOGCFL
description: scientific article; zbMATH DE number 1238734