Counting modulo quantifiers on finite structures
From MaRDI portal
Publication:1854352
DOI 10.1006/inco.1999.2842</link>zbMath 1005.03036</link>OpenAlex W2046731783</link>MaRDI QID Q1854352</link>
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
- \(\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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Counting modulo quantifiers on finite structures
