Counting modulo quantifiers on finite structures

DOI10.1006/INCO.1999.2842MaRDI QIDQ1854352zbMATH OpenOpenAlexFDO

Authors 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 equivalenceordered graphscounting modulo quantifiers

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Definability of Languages by Generalized First-Order Formulas over $(\mathbb{N},+)$
• Definability of Languages by Generalized First-Order Formulas over (N,+)
• Languages defined with modular counting quantifiers
• scientific article; zbMATH DE number 1136081
• scientific article

Cites work

• scientific article; zbMATH DE number 4180775 (Why is no real title available?)
• scientific article; zbMATH DE number 4008383 (Why is no real title available?)
• scientific article; zbMATH DE number 475414 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 1995174 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• scientific article; zbMATH DE number 3266604 (Why is no real title available?)
• scientific article; zbMATH DE number 3368555 (Why is no real title available?)
• scientific article; zbMATH DE number 3400884 (Why is no real title available?)
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Definability hierarchies of generalized quantifiers
• Generalized quantifiers and pebble games on finite structures
• Hierarchies of monadic generalized quantifiers
• Logical hierarchies in PTIME
• On monadic NP vs monadic co-NP
• On uniformity within \(NC^ 1\)
• On winning Ehrenfeucht games and monadic NP
• On winning strategies with unary quantifiers
• Parity, circuits, and the polynomial-time hierarchy
• Regular languages defined with generalized quantifiers
• Regular languages in \(NC\)
• Relational queries computable in polynomial time
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The monadic second-order logic of graphs. X: Linear orderings
• Unary quantifiers on finite models
• \(\Sigma_ 1^ 1\)-formulae on finite structures

Cited in

(12)

• Counting classes: Thresholds, parity, mods, and fewness
• scientific article; zbMATH DE number 1163932 (Why is no real title available?)
• Arithmetic, first-order logic, and counting quantifiers
• scientific article; zbMATH DE number 1192199 (Why is no real title available?)
• scientific article; zbMATH DE number 1453077 (Why is no real title available?)
• Modular Counting and Substitution of Structures
• Game-based notions of locality over finite models
• Describing realizable Gauss diagrams using the concepts of parity or bipartite graphs
• Gaifman normal forms for counting extensions of first-order logic
• scientific article; zbMATH DE number 6930501 (Why is no real title available?)
• Modulo counting on words and trees
• Solutions and query rewriting in data exchange

This page was built for publication: Counting modulo quantifiers on finite structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1854352)