On the autoreducibility of random sequences

DOI10.1007/3-540-44612-5_29MaRDI QIDQ4536369zbMATH OpenFDO

Authors Todd Ebert, Heribert Vollmer

Publication date 23 March 2004

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

Full work available at URL https://doi.org/10.1007/3-540-44612-5_29

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the Autoreducibility of Random Sequences
• Infinitely‐Often Autoreducible Sets
• On Languages Reducible to Algorithmically Random Languages
• On the construction of effective random sets
• Autoreducibility of random sets: A sharp bound on the density of guessed bits

Cited in

(7)

• Hat problem: a new strategy based on quantum stabilizer codes
• Randomness of formal languages via automatic martingales
• Autonomous automata and t(n)-generic language
• On Languages Reducible to Algorithmically Random Languages
• On the Autoreducibility of Random Sequences
• scientific article; zbMATH DE number 1497861 (Why is no real title available?)
• Autoreducibility of random sets: A sharp bound on the density of guessed bits

This page was built for publication: On the autoreducibility of random sequences

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