Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata (Q2164011)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata |
scientific article |
Statements
Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata (English)
0 references
11 August 2022
0 references
The paper deals with languages accepted by deterministic push-down automata which take an advice via an additional input track. It presents two lemmata showing necessary conditions using Kolmogorov complexity for those languages. These lemmata are used to show that certain languages accepted by adviced non-deterministic push-down automata are not accepted by deterministic ones. For the entire collection see [Zbl 1492.68017].
0 references
pushdown automata
0 references
Kolmogorov complexity
0 references
0 references
