Multihead two-way probabilistic finite automata
From MaRDI portal
Publication:675857
DOI10.1007/BF02679455zbMath0870.68100MaRDI QIDQ675857
Publication date: 11 March 1997
Published in: Theory of Computing Systems (Search for Journal in Brave)
Related Items (max. 100)
Bits and relative order from residues, space efficiently ⋮ Complexity Bounds of Constant-Space Quantum Computation ⋮ The complexity of debate checking ⋮ Decreasing the bandwidth of a transition matrix ⋮ Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines ⋮ A note on two-dimensional probabilistic Turing machines ⋮ Properties of probabilistic pushdown automata ⋮ A note on two-dimensional probabilistic finite automata ⋮ Amplification of slight probabilistic advantage at absolutely no cost in space
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Decreasing the bandwidth of a transition matrix
- Making a fair roulette from a possibly biased coin
- Space-bounded hierarchies and probabilistic computations
- The method of forced enumeration for nondeterministic automata
- Alternating multihead finite automata
- On tape-bounded complexity classes and multihead finite automata
- Space-bounded reducibility among combinatorial problems
- Transformational methods and their application to complexity problems
- Techniques for separating space complexity classes
- Relating refined space complexity classes
- Relationships between nondeterministic and deterministic tape complexities
- On non-determinacy in simple computing devices
- On two-way multihead automata
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Nondeterministic Space is Closed under Complementation
- New problems complete for nondeterministic log space
- Computational Complexity of Probabilistic Turing Machines
- k + 1 Heads Are Better than k
- On the Tape Complexity of Deterministic Context-Free Languages
- Finite state verifiers I
- Complexity of probabilistic versus deterministic automata
- On the Computational Complexity of Algorithms
- Probabilistic Turing Machines and Computability
- Computability by Probabilistic Turing Machines
This page was built for publication: Multihead two-way probabilistic finite automata
