DocumentCode
2200364
Title
Relativized limitations of left set technique and closure classes of sparse sets
Author
Saluja, Sanjeev
Author_Institution
Comput. Sci. Group, Tata Inst. of Funamental Res., Bombay, India
fYear
1993
fDate
18-21 May 1993
Firstpage
215
Lastpage
222
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Structure in Complexity Theory Conference, 1993., Proceedings of the Eighth Annual
Conference_Location
San Diego, CA
Print_ISBN
0-8186-4070-7
Type
conf
DOI
10.1109/SCT.1993.336524
Filename
336524
Link To Document