Comparing counting classes for logspace, one-way logspace, and first-order

DOI10.1007/3-540-60246-1_120zbMATH Open1193.68113OpenAlexW1516455116MaRDI QIDQ3569006FDOQ3569006

Authors: Hans-Jörg Burtschick 

Publication date: 17 June 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60246-1_120

Recommendations

• A very hard log-space counting class
• Logical definability of counting functions
• scientific article; zbMATH DE number 176518
• Counting classes and the fine structure between {\textsf{NC}}\(^{1}\) and {\textsf{L}}
• On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (2)

• A very hard log-space counting class
• Nondeterministic \(NC^1\) computation

This page was built for publication: Comparing counting classes for logspace, one-way logspace, and first-order

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