A lower bound for probabilistic algorithms for finite state machines

DOI10.1016/0022-0000(86)90045-0MaRDI QIDQ579936zbMATH OpenOpenAlexFDO

Authors A. G. Greenberg, Alan Weiss

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

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

Recommendations

• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• scientific article; zbMATH DE number 3850478
• scientific article; zbMATH DE number 176733
• scientific article; zbMATH DE number 1318511
• The complexity of probabilistic versus deterministic finite automata

Cites work

• scientific article; zbMATH DE number 3756646 (Why is no real title available?)
• scientific article; zbMATH DE number 3765145 (Why is no real title available?)
• scientific article; zbMATH DE number 3588051 (Why is no real title available?)
• scientific article; zbMATH DE number 3613145 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3319130 (Why is no real title available?)
• Alternating Pushdown and Stack Automata
• Correlated random walks
• Finite Continuous Time Markov Chains
• Non-negative matrices and Markov chains. 2nd ed
• Probabilistic automata
• Random walks with internal degrees of freedom
• THE GAMBLER'S RUIN PROBLEM WITH CORRELATION

Cited in

(28)

• scientific article; zbMATH DE number 1857649 (Why is no real title available?)
• Lower bounds on the area of finite-state machines
• Promise problems solved by quantum and classical finite automata
• Probabilistic rebound Turing machines
• Automata recognizing no words: a statistical approach
• On the power of finite automata with both nondeterministic and probabilistic states (preliminary version)
• A note on two-dimensional probabilistic finite automata
• scientific article; zbMATH DE number 4119632 (Why is no real title available?)
• Lower bounds for the state complexity of probabilistic languages and the language of prime numbers
• Two-way finite automata with quantum and classical states.
• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• On some variations of two-way probabilistic finite automata models
• Group Input Machine
• Infinite vs. finite size-bounded randomized computations
• Lower Bounds for Las Vegas Automata by Information Theory
• scientific article; zbMATH DE number 3850478 (Why is no real title available?)
• Some languages recognized by two-way finite automata with quantum and classical states
• Affine automata verifiers
• A note on two-way probabilistic automata
• Multiple usage of random bits in finite automata
• Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines
• A note on two-dimensional probabilistic Turing machines
• Limits of exact algorithms for inference of minimum size finite state machines
• Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
• Lower bound for the number of states of purposeful deterministic automata
• Closure property of probabilistic Turing machines and alternating Turing machines with sublogarithmic spaces
• Lower space bounds for randomized computation
• scientific article; zbMATH DE number 18635 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q579936)