## Abstract

Properties of L-printable sets are considered, and it is shown that two sets A and B that are L-printable and have similar density are L-isomorphic. L-printable sets are characterized as those sets L-isomorphic to tally sets in L, and as subsets of KS[k log n, k log n]. Several classes of L-printable sets are given, including sparse regular and context-free sets; a characterization of sparse regular sets is given. The relationship of the sparse sets in L to the sparse L-rankable and L-printable sets is considered, and strong indications are given that these classes are all different. An oracle is constructed relative to which there are sparse L-rankable sets that are in L and not L-printable, and L-rankable sets of similar density that are not L-isomorphic.

Original language | English |
---|---|

Pages (from-to) | 97-106 |

Number of pages | 10 |

Journal | Proceedings of the Annual IEEE Conference on Computational Complexity |

State | Published - 1996 |

Event | Proceedings of the 1996 11th Annual IEEE Conference on Computational Complexity - Philadelphia, PA, USA Duration: May 24 1996 → May 27 1996 |

## ASJC Scopus subject areas

- Software
- Theoretical Computer Science
- Computational Mathematics