Immunity and pseudorandomness of context-free languages
From MaRDI portal
Publication:653340
DOI10.1016/J.TCS.2011.07.013zbMATH Open1230.68140OpenAlexW1849715658MaRDI QIDQ653340FDOQ653340
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
Recommendations
Cites Work
- Title not available (Why is that?)
- Computational Complexity
- Three models for the description of language
- Title not available (Why is that?)
- Title not available (Why is that?)
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Title not available (Why is that?)
- Foundations of Cryptography
- Title not available (Why is that?)
- On certain formal properties of grammars
- A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
- Recursively enumerable sets of positive integers and their decision problems
- Theory of one-tape linear-time Turing machines
- On the structure of one-tape nondeterministic Turing machine time hierarchy
- One-tape, off-line Turing machine computations
- Completeness, Approximation and Density
- Resource bounded immunity and simplicity
- Title not available (Why is that?)
- Immunity, Relativizations, and Nondeterminism
- Bi-immune sets for complexity classes
- A note on balanced immunity
- Towards the Actual Relationship Between NP and Exponential Time
- Resource-bounded balanced genericity, stochasticity and weak randomness
- Title not available (Why is that?)
- Some Recursively Unsolvable Problems in ALGOL-Like Languages
- A New Interpretation of the von Mises' Concept of Random Sequence
- Oracle-dependent properties of the lattice of NP sets
Cited In (7)
- Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata
- One-way reversible and quantum finite automata with advice
- Pseudorandom generators against advised context-free languages
- Advice hierarchies among finite automata
- Randomness of formal languages via automatic martingales
- Power of counting by nonuniform families of polynomial-size finite automata
- FINITE AUTOMATA WITH ADVICE TAPES
Uses Software
This page was built for publication: Immunity and pseudorandomness of context-free languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q653340)
