Space-Efficient Deterministic Simulation of Probabilistic Automata

DOI10.1137/S0097539793253851MaRDI QIDQ4388881zbMATH OpenFDO

Authors Ioan I. Macarie

Publication date 10 May 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539793253851

zbMATH Keywords

deterministic simulationmatrix inversionprobabilistic Turing machinesresidue representationspace-bounded complexity classesstochastic languages

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45) Discrete mathematics in relation to computer science (68R99) Distributed algorithms (68W15)

Cited in

(15)

• Theory of one-tape linear-time Turing machines
• On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• Division in logspace-uniform NC
• Language Recognition Power and Succinctness of Affine Automata
• scientific article; zbMATH DE number 3887666 (Why is no real title available?)
• Factoring and Testing Primes in Small Space
• Parallel computation for well-endowed rings and space-bounded probabilistic machines
• scientific article; zbMATH DE number 3967918 (Why is no real title available?)
• Space-bounded probabilistic game automata
• scientific article; zbMATH DE number 1445805 (Why is no real title available?)
• The online space complexity of probabilistic languages
• Language recognition power and succinctness of affine automata
• Computational limitations of affine automata and generalized affine automata
• Decreasing the bandwidth of a transition matrix

This page was built for publication: Space-Efficient Deterministic Simulation of Probabilistic Automata

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