A New Approach to Formal Language Theory by Kolmogorov Complexity

DOI10.1137/S009753979324485XzbMath0827.68057MaRDI QIDQ4834389

Paul M. B. Vitányi, Ming Li

Publication date: 30 May 1995

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

zbMATH Keywords

Kolmogorov complexityChomsky hierarchy

Mathematics Subject Classification ID

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

Related Items (5)

Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata ⋮ The frequent paucity of trivial strings ⋮ The computational power of parsing expression grammars ⋮ Random Subgroups of Rationals ⋮ A pumping lemma for regular closure of prefix-free languages

This page was built for publication: A New Approach to Formal Language Theory by Kolmogorov Complexity