scientific article; zbMATH DE number 3858415

MaRDI QIDQ3326840zbMATH OpenFDO

Authors Rūsiņš Freivalds

Publication date 1983

zbMATH Keywords

one-way Turing machineprobabilistic recognitionprobabilistic Turing machineregularityreversal complexityspace complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 3887666
• scientific article; zbMATH DE number 18635
• Probabilistic rebound Turing machines
• Deterministic one-way Turing machines with sublinear space
• scientific article; zbMATH DE number 3850478

Cited in

(14)

• On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
• A survey of space complexity
• One-way bounded-error probabilistic pushdown automata and Kolmogorov complexity (preliminary report)
• A space lower bound for acceptance by one-way _2-alternating machines
• Deterministic one-way Turing machines with sublinear space
• Weak and strong one-way space complexity classes
• scientific article; zbMATH DE number 3887666 (Why is no real title available?)
• There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator
• scientific article; zbMATH DE number 18635 (Why is no real title available?)
• Space-Efficient Deterministic Simulation of Probabilistic Automata
• Complexity of probabilistic versus deterministic automata
• Lower space bounds for randomized computation
• Lower time bounds for randomized computation
• Alternating space is closed under complement and other simulations for sublogarithmic space

This page was built for publication:

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