Extensions of MSO and the monadic counting hierarchy
From MaRDI portal
Publication:617710
DOI10.1016/j.ic.2010.09.002zbMath1215.68105OpenAlexW2039822084MaRDI QIDQ617710
Publication date: 13 January 2011
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2010.09.002
Related Items (7)
Dependence logic with a majority quantifier ⋮ On counting propositional logic and Wagner's hierarchy ⋮ On Second-Order Monadic Groupoidal Quantifiers ⋮ A characterization of definability of second-order generalized quantifiers with applications to non-definability ⋮ Unnamed Item ⋮ A remark on collective quantification ⋮ Counting of Teams in First-Order Team Logics
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the expressive power of monadic least fixed point logic
- Definability of second order generalized quantifiers
- The complexity of combinatorial problems with succinct input representation
- Parallel computation with threshold functions
- Rudimentary relations and primitive recursion: A toolbox
- The polynomial-time hierarchy
- On second-order generalized quantifiers and finite structures
- Nonerasing, counting, and majority over the linear time hierarchy
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- On monadic NP vs monadic co-NP
- The monadic quantifier alternation hierarchy over grids and graphs
- On uniformity within \(NC^ 1\)
- PP is as Hard as the Polynomial-Time Hierarchy
- Complete Problems for Higher Order Logics
- Rudimentary Predicates and Relative Computation
- Complexity classes defined by counting quantifiers
- Rudimentary Languages and Second‐Order Logic
- Turing machines and the spectra of first-order formulas
- Arithmetic, first-order logic, and counting quantifiers
- A logical characterization of the counting hierarchy
This page was built for publication: Extensions of MSO and the monadic counting hierarchy
