Browse Prior Art Database

Non-Uniform Complexity and the Randomness of Certain Complete Languages

IP.com Disclosure Number: IPCOM000128018D
Original Publication Date: 1985-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 14 page(s) / 42K

Publishing Venue

Software Patent Institute

Related People

Dung T. Huynh: AUTHOR [+3]

Abstract

This paper contains further study of the randomness properties of languages. The connection between time-/space- bounded Kolmogorov complexity and non-uniform complexity defined by grammar and automata size is investigated. We show that certain languages that are complete under non-uniform one-way log-space reductions are weakly random with respect to other language classes contained in P. For examples, it will be shown that every context-free language that is complete under non-uniform one-way log-space reductions is weakly random with respect to the class of deterministic context-free languages, and every deterministic context-free language that is complete under non-uniform one-way log-space reductions is weakly random with respect to the class of linear languages.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Non-Uniform Complexity and the Randomness of Certain Complete Languages

Dung T. Huynh Iowa State University Computer Science Department Ames, Iowa 50011

TR 85-34 December 1985

Abstract.

This paper contains further study of the randomness properties of languages. The connection between time-/space- bounded Kolmogorov complexity and non-uniform complexity defined by grammar and automata size is investigated. We show that certain languages that are complete under non-uniform one-way log-space reductions are weakly random with respect to other language classes contained in P. For examples, it will be shown that every context-free language that is complete under non-uniform one-way log-space reductions is weakly random with respect to the class of deterministic context-free languages, and every deterministic context-free language that is complete under non-uniform one-way log-space reductions is weakly random with respect to the class of linear languages.

Key words. Kolmogorov complexity, non-uniform complexity, randomness, complete language, reducibility, automaton, grammar.

0. Introduction

Randomness is a notion that has received much attention in recursive function theory and computational complexity theory. The concept of an infinite random sequence intro-duced by Church ([Chu)) has been brought into the framework of polynomial complexity theory in [Wlb). On the other hand, the concept of a finite random string, as defined by Kolmogorov ([Kol)) and Chaitin ((Cha]), has been refined by several researchers, including Hartmanis ([Har)), Ko ([KoK)), Sipser ([Sill), and applied in various settings. In [Hull and [Hu2), following Church's and Kolmogorov's approaches, we introduced several notions of random languages, arid investigated properties of complete languages in terms of these notions of randomness. The motivation of our work is to study randomness proper-ties of languages that are complete under various kinds of reducibilities from the complexity-theoretic point of view rather than what is being done in research in cryptog-raphy. The purpose of the present paper is to investigate further the randomness properties of certain complete languages accepted in polynomial time. According to [Hull, a language L is said to be weakly random with respect to a language class L' iff for any L' E L' , the symmetric difference

(Equation Omitted)

is exponentially dense (i.e. there exists some e > 0 so that the number of strings of length K, n in A ( L, L' ) is at least 2e ` for all except at most finitely many n.) A principal motivation of this work is the following question : Is every hardest context-free language (in the sense of S. Greibach) weakly random with respect to the class of deterministic context-free languages ? It turns out that this question can be answered affirmatively. This result has a practical

Iowa State University Page 1 Dec 31, 1985

Page 2 of 14

Non-Uniform C...