One-way bounded-error probabilistic pushdown automata and Kolmogorov complexity (preliminary report)

DOI10.1007/978-3-319-62809-7_27zbMath1494.68151OpenAlexW2737881550MaRDI QIDQ2408814

Tomoyuki Yamakami

Publication date: 13 October 2017

Full work available at URL: https://doi.org/10.1007/978-3-319-62809-7_27

zbMATH Keywords

Kolmogorov complexitypalindromesprobabilistic pushdown automatabounded error probabilityBPCFL

Mathematics Subject Classification ID

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

Related Items (1)

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

This page was built for publication: One-way bounded-error probabilistic pushdown automata and Kolmogorov complexity (preliminary report)