P-Printable Sets
- 1 December 1988
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 17 (6) , 1193-1202
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 characterizations 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.Keywords
This publication has 22 references indexed in Scilit:
- Sets with small generalized Kolmogorov complexityActa Informatica, 1986
- The complexity of sparse sets in P1986
- On sparse oracles separating feasible complexity classes1986
- Uniform characterizations of non-uniform complexity measuresInformation and Control, 1985
- Sparse sets in NP-P: EXPTIME versus NEXPTIMEInformation and Control, 1985
- Comparison of the active visiting and the crossing complexitiesLecture Notes in Computer Science, 1977
- The contextsensitivity bounds of contextsensitive grammars and languages1977
- A Theory of Program Size Formally Identical to Information TheoryJournal of the ACM, 1975
- Characterizations of Pushdown Machines in Terms of Time-Bounded ComputersJournal of the ACM, 1971
- On the Length of Programs for Computing Finite Binary SequencesJournal of the ACM, 1966