Multiple Usage of Random Bits in Finite Automata

DOI10.1007/978-3-642-29952-0_50zbMath1354.68153MaRDI QIDQ2898066

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

68Q45: Formal languages and automata

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

Related Items

One-way reversible and quantum finite automata with advice, Advice hierarchies among finite automata

Cites Work

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