Decreasing the bandwidth of a transition matrix

DOI10.1016/0020-0190(94)00218-NzbMath0875.68419OpenAlexW2009402581MaRDI QIDQ673904

Ioan I. Macarie

Publication date: 28 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(94)00218-n

zbMATH Keywords

Computational complexityCompetitions methodLog-space complete problemUnbounded-error probabilistic Turing machines

Mathematics Subject Classification ID

Related Items (2)

Multihead two-way probabilistic finite automata ⋮ Multihead two-way probabilistic finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Multihead two-way probabilistic finite automata
• Space-bounded hierarchies and probabilistic computations
• On tape-bounded probabilistic Turing machine acceptors
• Relationships between nondeterministic and deterministic tape complexities
• Parallel computation for well-endowed rings and space-bounded probabilistic machines
• Computational Complexity of Probabilistic Turing Machines
• Complexity of probabilistic versus deterministic automata

This page was built for publication: Decreasing the bandwidth of a transition matrix