Space-Efficient Deterministic Simulation of Probabilistic Automata

DOI10.1137/S0097539793253851zbMath0907.68081MaRDI QIDQ4388881

Ioan I. Macarie

Publication date: 10 May 1998

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

zbMATH Keywords

matrix inversionprobabilistic Turing machinesdeterministic simulationresidue representationstochastic languagesspace-bounded complexity classes

Mathematics Subject Classification ID

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

Related Items

Uniform constant-depth threshold circuits for division and iterated multiplication. ⋮ Language recognition power and succinctness of affine automata ⋮ Computational limitations of affine automata and generalized affine automata ⋮ Division in logspace-uniformNC¹ ⋮ Factoring and Testing Primes in Small Space ⋮ Language Recognition Power and Succinctness of Affine Automata ⋮ On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits ⋮ Theory of one-tape linear-time Turing machines