Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines
From MaRDI portal
Publication:1818780
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)
closure propertyprobabilistic Turing machinesspace-bounded computationtwo-dimensional Turing machines
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