A lower bound for probabilistic algorithms for finite state machines

DOI10.1016/0022-0000(86)90045-0zbMATH Open0625.68039OpenAlexW2073696431MaRDI QIDQ579936FDOQ579936

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

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

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)

Cites Work

• Title not available (Why is that?)
• Probabilistic automata
• Non-negative matrices and Markov chains. 2nd ed
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Finite Continuous Time Markov Chains
• Title not available (Why is that?)
• THE GAMBLER'S RUIN PROBLEM WITH CORRELATION
• Alternating Pushdown and Stack Automata
• Title not available (Why is that?)
• Random walks with internal degrees of freedom
• Correlated random walks

Cited In (28)

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

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)