Immunity and pseudorandomness of context-free languages
From MaRDI portal
Publication:653340
DOI10.1016/j.tcs.2011.07.013zbMath1230.68140OpenAlexW1849715658MaRDI QIDQ653340
Publication date: 9 January 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.07.013
Related Items (6)
Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata ⋮ Randomness of formal languages via automatic martingales ⋮ Pseudorandom generators against advised context-free languages ⋮ One-way reversible and quantum finite automata with advice ⋮ Advice hierarchies among finite automata ⋮ FINITE AUTOMATA WITH ADVICE TAPES
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Oracle-dependent properties of the lattice of NP sets
- Theory of one-tape linear-time Turing machines
- On the structure of one-tape nondeterministic Turing machine time hierarchy
- Resource bounded immunity and simplicity
- On certain formal properties of grammars
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Immunity, Relativizations, and Nondeterminism
- Bi-immune sets for complexity classes
- Completeness, Approximation and Density
- A note on balanced immunity
- Towards the Actual Relationship Between NP and Exponential Time
- Foundations of Cryptography
- Resource-bounded balanced genericity, stochasticity and weak randomness
- Computational Complexity
- Some Recursively Unsolvable Problems in ALGOL-Like Languages
- A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
- Three models for the description of language
- A New Interpretation of the von Mises' Concept of Random Sequence
- One-tape, off-line Turing machine computations
- Recursively enumerable sets of positive integers and their decision problems
This page was built for publication: Immunity and pseudorandomness of context-free languages
