Decreasing the bandwidth of a transition matrix

DOI10.1016/0020-0190(94)00218-NMaRDI QIDQ673904zbMATH OpenOpenAlexFDO

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

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)

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)

Cites work

• scientific article; zbMATH DE number 3934409 (Why is no real title available?)
• scientific article; zbMATH DE number 3723866 (Why is no real title available?)
• scientific article; zbMATH DE number 3765145 (Why is no real title available?)
• scientific article; zbMATH DE number 3568040 (Why is no real title available?)
• scientific article; zbMATH DE number 3428547 (Why is no real title available?)
• Complexity of probabilistic versus deterministic automata
• Computational Complexity of Probabilistic Turing Machines
• Multihead two-way probabilistic finite automata
• On tape-bounded probabilistic Turing machine acceptors
• Parallel computation for well-endowed rings and space-bounded probabilistic machines
• Relationships between nondeterministic and deterministic tape complexities
• Space-bounded hierarchies and probabilistic computations

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
• scientific article; zbMATH DE number 3934409 (Why is no real title available?)

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)