The complexity of probabilistic versus deterministic finite automata

DOI10.1007/BFB0009499MaRDI QIDQ6487443zbMATH OpenFDO

Authors Andris Ambainis

Publication date 25 January 2023

Full work available at URL https://doi.org/10.1007/BFB0009499

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 1960351
• scientific article; zbMATH DE number 20623
• scientific article; zbMATH DE number 17834
• scientific article; zbMATH DE number 1809724
• Probabilism versus Alternation for Automata
• The complexity of probabilistic versus quantum finite automata
• scientific article; zbMATH DE number 1452987
• Probabilistic automata on finite words: decidable and undecidable problems
• On the Complexity of the Equivalence Problem for Probabilistic Automata
• On the computational complexity of approximating distributions by probabilistic automata

Cites work

• Probabilistic automata
• Some aspects of probabilistic automata

Cited in

(27)

• The complexity properties of probabilistic automata with isolated cut point
• On the computational complexity of approximating distributions by probabilistic automata
• Improved constructions for succinct affine automata
• Probabilistic automata with isolated cut-points
• Complexity of promise problems on classical and quantum automata
• The complexity of probabilistic versus quantum finite automata
• scientific article; zbMATH DE number 3862442 (Why is no real title available?)
• Note on the complexity of Las Vegas automata problems
• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• Efficient Computation of the Relative Entropy of Probabilistic Automata
• scientific article; zbMATH DE number 3963203 (Why is no real title available?)
• scientific article; zbMATH DE number 3982547 (Why is no real title available?)
• scientific article; zbMATH DE number 4064485 (Why is no real title available?)
• scientific article; zbMATH DE number 8012 (Why is no real title available?)
• scientific article; zbMATH DE number 17834 (Why is no real title available?)
• scientific article; zbMATH DE number 20623 (Why is no real title available?)
• scientific article; zbMATH DE number 1949657 (Why is no real title available?)
• Lower Bounds for Las Vegas Automata by Information Theory
• scientific article; zbMATH DE number 1747446 (Why is no real title available?)
• On a conjecture by Christian Choffrut
• Lower bounds for the state complexity of probabilistic languages and the language of prime numbers
• Non-constructive Methods for Finite Probabilistic Automata
• Artin’s Conjecture and Size of Finite Probabilistic Automata
• A lower bound for probabilistic algorithms for finite state machines
• Probabilism versus Alternation for Automata
• On the complexity of minimizing probabilistic and quantum automata
• Probabilistic input-driven pushdown automata

This page was built for publication: The complexity of probabilistic versus deterministic finite automata

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