L-Printable sets

Lance Fortnow, Judy Goldsmith, Matthew A. Levy, Stephen Mahaney

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


A language is L-printable if there is a logspace algorithm which, on input 1n, 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 languageEnglish
Pages (from-to)137-151
Number of pages15
JournalSIAM Journal on Computing
Issue number1
StatePublished - 1998


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

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'L-Printable sets'. Together they form a unique fingerprint.

Cite this