Counting modulo quantifiers on finite structures
From MaRDI portal
Publication:1854352
DOI10.1006/inco.1999.2842zbMath1005.03036OpenAlexW2046731783MaRDI QIDQ1854352
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
Complexity of computation (including implicit computational complexity) (03D15) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)
Related Items (5)
Solutions and query rewriting in data exchange ⋮ Describing realizable Gauss diagrams using the concepts of parity or bipartite graphs ⋮ Unnamed Item ⋮ Game-based notions of locality over finite models ⋮ Unnamed Item
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
This page was built for publication: Counting modulo quantifiers on finite structures
