## Abstract

A language is L-printable if there is a logspace algorithm which, on input 1^{n}, prints all members in the language of length n. Following the work of Allender and Rubinstein [SIAM J. Comput., 17 (1988), pp. 1193-1202] on P-printable sets, we present some simple properties of the L-printable sets. This definition of "L-printable" is robust and allows us to give alternate characterizations of the L-printable sets in terms of tally sets and Kolmogorov complexity. In addition, we show that a regular or context-free language is L-printable if and only if it is sparse, and we investigate the relationship between L-printable sets, L-rankable sets (i.e., sets A having a logspace algorithm that, on input x, outputs the number of elements of A that precede x in the standard lexicographic ordering of strings), and the sparse sets in L. We prove that under reasonable complexity-theoretic assumptions, these three classes of sets are all different. We also show that the class of sets of small generalized Kolmogorov space complexity is exactly the class of sets that are L-isomorphic to tally languages.

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

Pages (from-to) | 137-151 |

Number of pages | 15 |

Journal | SIAM Journal on Computing |

Volume | 28 |

Issue number | 1 |

DOIs | |

State | Published - 1998 |

## Keywords

- Computational complexity
- Context-free languages
- Kolmogorov complexity
- L-isomorphisms
- Logspace
- Ranking
- Regular languages
- Sparse sets

## ASJC Scopus subject areas

- General Computer Science
- General Mathematics