Kolmogorov Complexity and Deterministic Context-Free Languages

DOI10.1137/S0097539702417754MaRDI QIDQ4429692zbMATH OpenFDO

Authors 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)

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

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
• Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata
• scientific article; zbMATH DE number 4117885 (Why is no real title available?)
• A New Approach to Formal Language Theory by Kolmogorov Complexity
• scientific article; zbMATH DE number 4187790 (Why is no real title available?)
• Cover complexity of finite languages
• scientific article; zbMATH DE number 1361492 (Why is no real title available?)
• 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)