Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata
From MaRDI portal
Publication:2164011
DOI10.1007/978-3-031-05578-2_25OpenAlexW4285165515MaRDI QIDQ2164011
Publication date: 11 August 2022
Full work available at URL: https://doi.org/10.1007/978-3-031-05578-2_25
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