scientific article; zbMATH DE number 3887666

MaRDI QIDQ3222174zbMATH OpenFDO

Authors Rūsiņš Freivalds

Publication date 1985

zbMATH Keywords

probabilistic Turing machinesspace complexity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 3858415
• scientific article; zbMATH DE number 18635
• Probabilistic rebound Turing machines
• Space-Efficient Deterministic Simulation of Probabilistic Automata
• scientific article; zbMATH DE number 3984575

Cited in

(14)

• 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 3858415 (Why is no real title available?)
• scientific article; zbMATH DE number 3967918 (Why is no real title available?)
• scientific article; zbMATH DE number 18635 (Why is no real title available?)
• Space-Efficient Deterministic Simulation of Probabilistic Automata
• scientific article; zbMATH DE number 1948497 (Why is no real title available?)
• Lower space bounds for randomized computation
• Lower time bounds for randomized computation
• A NOTE ON REBOUND TURING MACHINES
• Probabilistic rebound Turing machines
• On the complexity of 1-tape ATMs and off-line 1-tape ATMs running in constant reversals

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 Q3222174)