Pseudorandom generators against advised context-free languages

DOI10.1016/j.tcs.2015.10.026zbMath1333.68175OpenAlexW2962893111MaRDI QIDQ899305

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

context-free languagepseudorandom generatoradvicepushdown automatonpseudorandom languageswapping property

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata ⋮ One-way reversible and quantum finite automata with advice

Cites Work

• Unnamed Item
• One-way reversible and quantum finite automata with advice
• Immunity and pseudorandomness of context-free languages
• A taxonomy of complexity classes of functions
• Hardness vs randomness
• Oracle Pushdown Automata, Nondeterministic Reducibilities, and the Hierarchy over the Family of Context-Free Languages
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• The Roles of Advice to One-Tape Linear-Time Turing Machines and Finite Automata (Extended Abstract)
• Quantitative Relativizations of Complexity Classes
• Foundations of Cryptography
• Computational Complexity
• SOFSEM 2004: Theory and Practice of Computer Science

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