On some variations of two-way probabilistic finite automata models
From MaRDI portal
Publication:880179
DOI10.1016/j.tcs.2007.01.017zbMath1111.68063OpenAlexW1972193441MaRDI QIDQ880179
Publication date: 11 May 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2007.01.017
Related Items
Cites Work
- A lower bound for probabilistic algorithms for finite state machines
- A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
- There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Shuffling Cards and Stopping Times
- On the power of two-way random generators and the impossibility of deterministic poly-space simulation
- Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
- Finite state verifiers I
- The knowledge complexity of interactive proof-systems
- On the Power of Finite Automata with both Nondeterministic and Probabilistic States
- Probabilistic automata
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
