Multiple usage of random bits in finite automata

DOI10.1007/978-3-642-29952-0_50MaRDI QIDQ2898066zbMATH OpenOpenAlexFDO

Authors Rūsiņš Freivalds

Publication date 16 July 2012

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-29952-0_50

Mathematics Subject Classification ID

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

Recommendations

• On read-once vs. multiple access to randomness in logspace
• Stochasticity of the languages acceptable by two-way finite probabilistic automata
• On the power of Las Vegas II: Two-way finite automata
• A lower bound for probabilistic algorithms for finite state machines
• scientific article; zbMATH DE number 3850478

Cites work

• A unified approach to the definition of random sequences
• Amount of nonconstructivity in deterministic finite automata
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Communication Theory of Secrecy Systems*
• Complexity of probabilistic versus deterministic automata
• Finite state verifiers I
• Generalisations of disjunctive sequences
• scientific article; zbMATH DE number 3765145 (Why is no real title available?)
• scientific article; zbMATH DE number 3474957 (Why is no real title available?)
• scientific article; zbMATH DE number 3489016 (Why is no real title available?)
• scientific article; zbMATH DE number 3573787 (Why is no real title available?)
• scientific article; zbMATH DE number 1254648 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• NON-CONSTRUCTIVE METHODS FOR FINITE PROBABILISTIC AUTOMATA
• On?-Languages whose syntactic monoid is trivial
• Polynomial time quantum computation with advice
• Private vs. common random bits in communication complexity
• Probabilistic automata
• Process complexity and effective random tests
• The definition of random sequences
• The knowledge complexity of interactive proof-systems
• THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA
• Theory of one-tape linear-time Turing machines
• Turing machines that take advice

Cited in

(3)

• On read-once vs. multiple access to randomness in logspace
• Advice hierarchies among finite automata
• Entropy and Expected Acceptance Counts for Finite Automata

This page was built for publication: Multiple usage of random bits in finite automata

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