Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata

DOI10.1007/978-3-031-05578-2_25OpenAlexW4285165515MaRDI QIDQ2164011

Tomoyuki Yamakami

Publication date: 11 August 2022

Full work available at URL: https://doi.org/10.1007/978-3-031-05578-2_25

zbMATH Keywords

Kolmogorov complexitypushdown automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cites Work

• Immunity and pseudorandomness of context-free languages
• Intersection and union hierarchies of deterministic context-free languages and pumping lemmas
• Turing machines that take advice
• Pseudorandom generators against advised context-free languages
• Theory of one-tape linear-time Turing machines
• A structural lemma for deterministic context-free languages
• One-way bounded-error probabilistic pushdown automata and Kolmogorov complexity (preliminary report)
• THE ROLES OF ADVICE TO ONE-TAPE LINEAR-TIME TURING MACHINES AND FINITE AUTOMATA
• Automata that take advice
• An “Interchange Lemma” for Context-Free Languages
• Kolmogorov Complexity and Deterministic Context-Free Languages
• A New Approach to Formal Language Theory by Kolmogorov Complexity
• An infinite hierarchy of intersections of context-free languages
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata