Immunity and pseudorandomness of context-free languages

DOI10.1016/J.TCS.2011.07.013MaRDI QIDQ653340zbMATH OpenOpenAlexFDO

Authors Tomoyuki Yamakami

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

zbMATH Keywords

computational complexitycontext-free languagespseudorandomnessimmunityCFLREG

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Pseudorandom generators against advised context-free languages
• scientific article; zbMATH DE number 1688372
• Two complexity measures for context-free languages
• Random Generation for Finitely Ambiguous Context-free Languages
• Analytic models and ambiguity of context-free languages

Cites work

• scientific article; zbMATH DE number 3883611 (Why is no real title available?)
• scientific article; zbMATH DE number 3174044 (Why is no real title available?)
• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 4121422 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A New Interpretation of the von Mises' Concept of Random Sequence
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• A note on balanced immunity
• Bi-immune sets for complexity classes
• Completeness, Approximation and Density
• Computational Complexity
• Foundations of Cryptography
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Immunity, Relativizations, and Nondeterminism
• On certain formal properties of grammars
• On the structure of one-tape nondeterministic Turing machine time hierarchy
• One-tape, off-line Turing machine computations
• Oracle-dependent properties of the lattice of NP sets
• Recursively enumerable sets of positive integers and their decision problems
• Resource bounded immunity and simplicity
• Resource-bounded balanced genericity, stochasticity and weak randomness
• Some Recursively Unsolvable Problems in ALGOL-Like Languages
• Theory of one-tape linear-time Turing machines
• Three models for the description of language
• Towards the Actual Relationship Between NP and Exponential Time

Cited in

(6)

• Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata
• Advice hierarchies among finite automata
• Power of counting by nonuniform families of polynomial-size finite automata
• Randomness of formal languages via automatic martingales
• Finite automata with advice tapes
• Pseudorandom generators against advised context-free languages

Describes a project that uses

Uses Software

• ALGOL 60

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)