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)

Full work available at URL https://doi.org/10.1137/S0097539796300441

zbMATH Keywords

\(L\)-isomorphismscomputational complexitycontext-free languagesKolmogorov complexitylogspacerankingregular languagessparse sets

Mathematics Subject Classification ID

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

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

(5)

• NL-printable sets and nondeterministic Kolmogorov complexity
• Self-P-Printability and Polynomial Time Turing Equivalence to a Tally Set
• A relation between sparse and printable sets in \(\text{NSPACE}(\log n)\)
• P-Printable Sets
• 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)