P-printable sets

Eric W. Allender; Roy S. Rubinstein

doi:10.1137/0217075

P-printable sets

Eric W. Allender, Roy S. Rubinstein

School of Arts and Sciences, Computer Science

Research output: Contribution to journal › Article › peer-review

64 Scopus citations

Abstract

P-printable sets arise naturally in the studies of generalized Kolmogorov complexity and data compression, as well as in other areas. We present new characterization of the P-printable sets and present necessary and sufficient conditions for the existence of sparse sets in P that are not P-printable. As a corollary to one of our results, we show that the class of sets of small generalized Kolmogorov complexity is exactly the class of sets which are P-isomorphic to a tally language.

Original language	English (US)
Pages (from-to)	1193-1202
Number of pages	10
Journal	SIAM Journal on Computing
Volume	17
Issue number	6
DOIs	https://doi.org/10.1137/0217075
State	Published - 1988

All Science Journal Classification (ASJC) codes

Computer Science(all)
Mathematics(all)

Access to Document

10.1137/0217075

Cite this

@article{c0acdad057e74c0099fc04fa39722771,

title = "P-printable sets",

abstract = "P-printable sets arise naturally in the studies of generalized Kolmogorov complexity and data compression, as well as in other areas. We present new characterization of the P-printable sets and present necessary and sufficient conditions for the existence of sparse sets in P that are not P-printable. As a corollary to one of our results, we show that the class of sets of small generalized Kolmogorov complexity is exactly the class of sets which are P-isomorphic to a tally language.",

author = "Allender, {Eric W.} and Rubinstein, {Roy S.}",

year = "1988",

doi = "10.1137/0217075",

language = "English (US)",

volume = "17",

pages = "1193--1202",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "6",

}

TY - JOUR

T1 - P-printable sets

AU - Allender, Eric W.

AU - Rubinstein, Roy S.

PY - 1988

Y1 - 1988

N2 - P-printable sets arise naturally in the studies of generalized Kolmogorov complexity and data compression, as well as in other areas. We present new characterization of the P-printable sets and present necessary and sufficient conditions for the existence of sparse sets in P that are not P-printable. As a corollary to one of our results, we show that the class of sets of small generalized Kolmogorov complexity is exactly the class of sets which are P-isomorphic to a tally language.

AB - P-printable sets arise naturally in the studies of generalized Kolmogorov complexity and data compression, as well as in other areas. We present new characterization of the P-printable sets and present necessary and sufficient conditions for the existence of sparse sets in P that are not P-printable. As a corollary to one of our results, we show that the class of sets of small generalized Kolmogorov complexity is exactly the class of sets which are P-isomorphic to a tally language.

UR - http://www.scopus.com/inward/record.url?scp=0024138281&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0024138281&partnerID=8YFLogxK

U2 - 10.1137/0217075

DO - 10.1137/0217075

M3 - Article

AN - SCOPUS:0024138281

SN - 0097-5397

VL - 17

SP - 1193

EP - 1202

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 6

ER -

P-printable sets

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this