A lower bound for probabilistic algorithms for finite state machines

DOI10.1016/0022-0000(86)90045-0zbMath0625.68039OpenAlexW2073696431MaRDI QIDQ579936

Alan Weiss, Albert G. Greenberg

Publication date: 1986

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(86)90045-0

zbMATH Keywords

2-way probabilistic finite automatonbehavior of random walks controlled by Markov chainsdensities of regular sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Sums of independent random variables; random walks (60G50) Formal languages and automata (68Q45)

Related Items (14)

Affine automata verifiers ⋮ On some variations of two-way probabilistic finite automata models ⋮ Lower space bounds for randomized computation ⋮ SOME LANGUAGES RECOGNIZED BY TWO-WAY FINITE AUTOMATA WITH QUANTUM AND CLASSICAL STATES ⋮ Promise problems solved by quantum and classical finite automata ⋮ A note on two-way probabilistic automata ⋮ Group Input Machine ⋮ Probabilistic rebound Turing machines ⋮ Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines ⋮ A note on two-dimensional probabilistic Turing machines ⋮ A note on two-dimensional probabilistic finite automata ⋮ CLOSURE PROPERTY OF PROBABILISTIC TURING MACHINES AND ALTERNATING TURING MACHINES WITH SUBLOGARITHMIC SPACES ⋮ Two-way finite automata with quantum and classical states. ⋮ Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata

Cites Work

• Correlated random walks
• Non-negative matrices and Markov chains. 2nd ed
• THE GAMBLER'S RUIN PROBLEM WITH CORRELATION
• Alternating Pushdown and Stack Automata
• Finite Continuous Time Markov Chains
• Probabilistic automata
• Random walks with internal degrees of freedom
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A lower bound for probabilistic algorithms for finite state machines