scientific article; zbMATH DE number 4117885

MaRDI QIDQ4732131zbMATH OpenFDO

Authors Paul M. B. Vitányi, Ming Li

Publication date 1989

zbMATH Keywords

Chomsky hierarchyformal languageKolmogorov complexity

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Undecidability and degrees of sets of sentences (03D35) Formal languages and automata (68Q45) Information theory (general) (94A15)

Recommendations

• A New Approach to Formal Language Theory by Kolmogorov Complexity
• Kolmogorov Complexity and Deterministic Context-Free Languages
• Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata
• Kolmogorov complexity as a language
• Kolmogorov complexity and non-determinism

Cited in

(7)

• On space-bounded synchronized alternating Turing machines
• Measures of nondeterminism for pushdown automata
• Kolmogorov complexity as a language
• scientific article; zbMATH DE number 4112041 (Why is no real title available?)
• scientific article; zbMATH DE number 58302 (Why is no real title available?)
• Kolmogorov Complexity and Deterministic Context-Free Languages
• A New Approach to Formal Language Theory by Kolmogorov Complexity

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4732131)