Counting modulo quantifiers on finite structures
From MaRDI portal
Publication:1854352
DOI10.1006/inco.1999.2842zbMath1005.03036MaRDI 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
03D15: Complexity of computation (including implicit computational complexity)
03C13: Model theory of finite structures
68Q19: Descriptive complexity and finite models
Related Items
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