Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines

DOI10.1016/S0020-0255(98)10084-1zbMath0943.03032MaRDI QIDQ1818780

Yue Wang, Akira Ito, Tokio Okazaki, Katsushi Inoue

Publication date: 5 September 2000

Published in: Information Sciences (Search for Journal in Brave)

zbMATH Keywords

closure propertyprobabilistic Turing machinesspace-bounded computationtwo-dimensional Turing machines

Mathematics Subject Classification ID

Turing machines and related notions (03D10)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower bound for probabilistic algorithms for finite state machines
• Multihead two-way probabilistic finite automata
• Two-dimensional alternative Turing machines
• On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
• A note on closure properties of the classes of sets accepted by tape- bounded two-dimensional Turing machines
• Closure properties of three-way and four-way tape-bounded two-dimensional Turing machines
• Non-negative matrices and Markov chains. 2nd ed
• A note on two-way probabilistic automata
• A note on two-dimensional probabilistic finite automata
• Turing machines with sublogarithmic space
• Computational Complexity of Probabilistic Turing Machines
• Finite state verifiers I
• Probabilistic automata
• Picture languages with array rewriting rules

This page was built for publication: Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines