Title :
Relativized limitations of left set technique and closure classes of sparse sets
Author_Institution :
Comput. Sci. Group, Tata Inst. of Funamental Res., Bombay, India
Abstract :
A number of theorems are proved by introducing the notion of k -families of sets of strings, and an algorithm which outputs the sets of certain k-families is given. The algorithm is used to disjunctively reduce the left set (or 1wdsr set) to a sparse set. The set output by the algorithm on an input corresponds to the set queried by the disjunctive reduction on the input
Keywords :
computational complexity; formal languages; set theory; closure classes; computational complexity; disjunctive reduction; k-families; left set technique; sets of strings; sparse sets; Automatic logic units; Circuits; Complexity theory; Computer science; Polynomials; Size measurement; Time measurement;
Conference_Titel :
Structure in Complexity Theory Conference, 1993., Proceedings of the Eighth Annual
Conference_Location :
San Diego, CA
Print_ISBN :
0-8186-4070-7
DOI :
10.1109/SCT.1993.336524
