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

DOI10.1007/3-540-60246-1_120MaRDI QIDQ3569006zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

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)