Decreasing the bandwidth of a transition matrix

DOI10.1016/0020-0190(94)00218-NzbMATH Open0875.68419OpenAlexW2009402581MaRDI QIDQ673904FDOQ673904

Authors: 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

Recommendations

• scientific article; zbMATH DE number 3934409
• Multihead two-way probabilistic finite automata
• Space-Efficient Deterministic Simulation of Probabilistic Automata
• Multihead two-way probabilistic finite automata (extended abstract)

zbMATH Keywords

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

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Title not available (Why is that?)
• Space-bounded hierarchies and probabilistic computations
• Relationships between nondeterministic and deterministic tape complexities
• Computational Complexity of Probabilistic Turing Machines
• Title not available (Why is that?)
• Multihead two-way probabilistic finite automata
• Complexity of probabilistic versus deterministic automata
• On tape-bounded probabilistic Turing machine acceptors
• Title not available (Why is that?)
• Parallel computation for well-endowed rings and space-bounded probabilistic machines
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (5)

• Bandwidth reduction of rectangular matrices
• Multihead two-way probabilistic finite automata (extended abstract)
• Multihead two-way probabilistic finite automata
• Bandwidth constraints on problems complete for polynomial time
• Title not available (Why is that?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q673904)