Counting modulo quantifiers on finite structures

DOI10.1006/inco.1999.2842zbMath1005.03036MaRDI QIDQ1854352

Juha Nurmonen

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/3b983e440fbe48e67447a9e1549078c183dc3346

zbMATH Keywords

elementary equivalence; ordered graphs; counting modulo quantifiers

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

03C13: Model theory of finite structures

68Q19: Descriptive complexity and finite models

Related Items

Solutions and query rewriting in data exchange, Game-based notions of locality over finite models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Regular languages in \(NC\)
• Unary quantifiers on finite models
• The monadic second-order logic of graphs. X: Linear orderings
• Logical hierarchies in PTIME
• Definability hierarchies of generalized quantifiers
• Regular languages defined with generalized quantifiers
• Generalized quantifiers and pebble games on finite structures
• On monadic NP vs monadic co-NP
• On winning Ehrenfeucht games and monadic NP
• On uniformity within \(NC^ 1\)
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• On winning strategies with unary quantifiers
• Parity, circuits, and the polynomial-time hierarchy
• Relational queries computable in polynomial time
• Hierarchies of monadic generalized quantifiers
• Decidability of Second-Order Theories and Automata on Infinite Trees