A logical characterization of the counting hierarchy

DOI10.1145/1459010.1459017zbMath1367.68106OpenAlexW2085743552MaRDI QIDQ5277825

Juha Kontinen

Publication date: 12 July 2017

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1459010.1459017

zbMATH Keywords

quantifier eliminationcounting hierarchy0-1 lawmajority quantifiers

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Related Items (6)

Dependence logic with a majority quantifier ⋮ Extensions of MSO and the monadic counting hierarchy ⋮ On counting propositional logic and Wagner's hierarchy ⋮ Descriptive complexity of \#P functions: a new perspective ⋮ A characterization of definability of second-order generalized quantifiers with applications to non-definability ⋮ Counting of Teams in First-Order Team Logics

This page was built for publication: A logical characterization of the counting hierarchy