L-Printable Sets

DOI10.1137/S0097539796300441MaRDI QIDQ4210140zbMATH OpenFDO

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

Publication date 21 September 1998

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

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)

Recommendations

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

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)