Kolmogorov Complexity and Deterministic Context-Free Languages
From MaRDI portal
Publication:4429692
DOI10.1137/S0097539702417754zbMATH Open1053.68052MaRDI QIDQ4429692FDOQ4429692
Authors: Oliver Glier
Publication date: 28 September 2003
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
- Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata
- A structural lemma for deterministic context-free languages
- A New Approach to Formal Language Theory by Kolmogorov Complexity
- scientific article; zbMATH DE number 4117885
- A pumping lemma for deterministic context-free languages
Formal languages and automata (68Q45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)
Cited In (10)
- A pumping lemma for regular closure of prefix-free languages
- A structural lemma for deterministic context-free languages
- Refined Bounds on Kolmogorov Complexity for ω-Languages
- Title not available (Why is that?)
- Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata
- A New Approach to Formal Language Theory by Kolmogorov Complexity
- Title not available (Why is that?)
- Title not available (Why is that?)
- Cover complexity of finite languages
- On the context-free production complexity of finite languages
This page was built for publication: Kolmogorov Complexity and Deterministic Context-Free Languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4429692)