Extensions of MSO and the monadic counting hierarchy
type: Item
instance of: scholarly article
title: Extensions of MSO and the monadic counting hierarchy
zbMATH Open document ID: 1215.68105
author: Juha Kontinen
author: Hannu Niemistö
published in: Information and Computation
publication date: 2011-01-13T00:00:00Z
review text: The paper studies the expressive power of first-order logic extended with the unary second-order qualifier Most\(^1\). The authors first consider monadic second-order logic with first-order Rescher quantifier over unary vocabularies, and show that it corresponds to Presburger arithmetic. Then they extend this result to monadic second-order logic with the vectorization of the Rescher quantifier by proving its correspondence to the \(\Delta_0\)-fragment of arithmetic. The paper next shows that every vectorization of the first-order Rescher quantifier is definable in the logic FO(Most\(^1\)) and that FO(Most\(^1\)) collapses to uniform-TC\(^0\) on unary vocabularies. The collapse follows a separation result for first-order logic with the binary second-order majority quantifier and FO(Most\(^1\)) over the empty vocabulary. On strings, however, the logic FO(Most\(^1\)) captures the linear fragment of the counting hierarchy, and over a non-unary vocabulary, it can define complete problems for every level of the counting hierarchy.
reviewed by: Galina Jirásková
Mathematics Subject Classification ID: 68Q19
Mathematics Subject Classification ID: 03C80
zbMATH DE Number: 5835734
zbMATH Keywords: counting hierarchy
zbMATH Keywords: monadic second-order logic
zbMATH Keywords: majority quantifier
zbMATH Keywords: second-order generalized quantifier
MaRDI profile type: Publication
full work available at URL: j.ic.2010.09.002
OpenAlex ID: W2039822084
cites work: A logical characterization of the counting hierarchy
cites work: Q4058132
cites work: The polynomial-time hierarchy
cites work: On monadic NP vs monadic co-NP
cites work: The monadic quantifier alternation hierarchy over grids and graphs
cites work: The complexity of combinatorial problems with succinct input representation
cites work: Complexity classes defined by counting quantifiers
cites work: Nonerasing, counting, and majority over the linear time hierarchy
cites work: Rudimentary Languages and Second‐Order Logic
cites work: Q3113046
cites work: On second-order generalized quantifiers and finite structures
cites work: Definability of second order generalized quantifiers
cites work: On uniformity within \(NC^ 1\)
cites work: Uniform constant-depth threshold circuits for division and iterated multiplication.
cites work: Rudimentary Predicates and Relative Computation
cites work: Rudimentary relations and primitive recursion: A toolbox
cites work: Turing machines and the spectra of first-order formulas
cites work: Q4227581
cites work: Arithmetic, first-order logic, and counting quantifiers
cites work: PP is as Hard as the Polynomial-Time Hierarchy
cites work: On the expressive power of monadic least fixed point logic
cites work: Complete Problems for Higher Order Logics
cites work: Parallel computation with threshold functions
cites work: Q4267800
DOI: 10.1016/J.IC.2010.09.002
description: scientific article; zbMATH DE number 5835734