L-Printable Sets

DOI10.1137/S0097539796300441zbMATH Open0915.68067MaRDI QIDQ4210140FDOQ4210140

Stephen R. Mahaney, Lance Fortnow, Matthew A. Levy, J. Goldsmith

Publication date: 21 September 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Recommendations

• P-Printable Sets
• NL-printable sets and nondeterministic Kolmogorov complexity
• Self-P-Printability and Polynomial Time Turing Equivalence to a Tally Set

zbMATH Keywords

computational complexityrankingcontext-free languagesKolmogorov complexitysparse setsregular languageslogspace\(L\)-isomorphisms

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30)

Cited In (3)

• P-Printable Sets
• NL-printable sets and Nondeterministic Kolmogorov Complexity
• NL-printable sets and nondeterministic Kolmogorov complexity

This page was built for publication: L-Printable Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210140)