Space-Efficient Deterministic Simulation of Probabilistic Automata
From MaRDI portal
Publication:4388881
DOI10.1137/S0097539793253851zbMath0907.68081MaRDI QIDQ4388881
Publication date: 10 May 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
matrix inversion; probabilistic Turing machines; deterministic simulation; residue representation; stochastic languages; space-bounded complexity classes
68Q45: Formal languages and automata
68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
68R99: Discrete mathematics in relation to computer science
68W15: Distributed algorithms
Related Items
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-uniformNC1, Factoring and Testing Primes in Small Space