Pseudorandom generators against advised context-free languages

DOI10.1016/J.TCS.2015.10.026MaRDI QIDQ899305zbMATH OpenOpenAlexFDO

Authors Tomoyuki Yamakami

Publication date 28 December 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.10.026

zbMATH Keywords

advicecontext-free languagepushdown automatonpseudorandom generatorpseudorandom languageswapping property

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Immunity and pseudorandomness of context-free languages
• A Pseudorandom Generator from any One-way Function
• On the Existence of Pseudorandom Generators
• scientific article; zbMATH DE number 1688372
• Pseudorandom generators and the frequency of simplicity

Cites work

• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• A taxonomy of complexity classes of functions
• Computational Complexity
• Foundations of Cryptography
• Hardness vs randomness
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Immunity and pseudorandomness of context-free languages
• Oracle pushdown automata, nondeterministic reducibilities, and the hierarchy over the family of context-free languages
• Quantitative Relativizations of Complexity Classes
• SOFSEM 2004: Theory and Practice of Computer Science
• The roles of advice to one-tape linear-time Turing machines and finite automata (extended abstract)

Cited in

(4)

• Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata
• Immunity and pseudorandomness of context-free languages
• Power of counting by nonuniform families of polynomial-size finite automata
• Random Generation for Finitely Ambiguous Context-free Languages

This page was built for publication: Pseudorandom generators against advised context-free languages

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