Kolmogorov Complexity and Deterministic Context-Free Languages

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

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)

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)