Kolmogorov Complexity and Deterministic Context-Free Languages

DOI10.1137/S0097539702417754zbMath1053.68052MaRDI QIDQ4429692

Oliver Glier

Publication date: 28 September 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

Kolmogorov complexityformal language theorydeterministic context-free languages

Mathematics Subject Classification ID

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

Related Items (2)

Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata ⋮ A pumping lemma for regular closure of prefix-free languages

This page was built for publication: Kolmogorov Complexity and Deterministic Context-Free Languages