Logical definability of counting functions

DOI10.1006/JCSS.1996.0069MaRDI QIDQ1816735zbMATH OpenOpenAlexFDO

Authors Kevin J. Compton, Erich Grädel

Publication date 31 March 1997

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jcss.1996.0069

zbMATH Keywords

computational complexitylogical languages

Mathematics Subject Classification ID

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

Recommendations

• Descriptive complexity of \(\#\)P functions
• scientific article; zbMATH DE number 515737
• On the expressive power of counting
• On fixed-point logic with counting

Cited in

(8)

• Definability for model counting
• Functions definable by numerical set-expressions
• Comparing counting classes for logspace, one-way logspace, and first-order
• Definability of combinatorial functions and their linear recurrence relations
• scientific article; zbMATH DE number 4041901 (Why is no real title available?)
• Descriptive complexity for counting complexity classes
• A logical characterization of the counting hierarchy
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

This page was built for publication: Logical definability of counting functions

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