Nonuniform complexity and the randomness of certain complete languages (Q1184988): Difference between revisions

The author continues his investigations of the randomness properties of various languages. Using basic approaches of A. Church on infinite random sequences and A. N. Kolmogorov on finite random strings, the author exploits his earlier results on several concepts of random languages and properties of complete languages in terms of these randomness concepts from the complexity viewpoint rather than, say, the cryptography viewpoint. The author proves several interesting results that clarify the difficult relationships between resource-bounded Kolmogorov complexity and other non-uniform complexity measures defined by grammars or automata size. In the process, the author vindicates the naturalness of the use of the notion of weakly random languages.