Arithmetic, first-order logic, and counting quantifiers

DOI10.1145/1071596.1071602zbMath1407.03050MaRDI QIDQ5277734

Nicole Schweikardt

Publication date: 12 July 2017

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1071596.1071602

zbMATH Keywords

first-order logic; quantifier elimination; Presburger arithmetic; counting quantifiers

Mathematics Subject Classification ID

03F30: First-order arithmetic and fragments

03C80: Logic with extra quantifiers and operators

03C07: Basic properties of first-order languages and structures

03C10: Quantifier elimination, model completeness, and related topics

68Q19: Descriptive complexity and finite models

Related Items

Unnamed Item, Model-Checking Counting Temporal Logics on Flat Structures, On Presburger arithmetic extended with non-unary counting quantifiers, Theories of initial segments of standard models of arithmetics and their complete extensions, Extensions of MSO and the monadic counting hierarchy, The exact complexity of projective image matching, On the expressive power of monadic least fixed point logic, An Ehrenfeucht-Fraïssé game approach to collapse results in database theory, Ehrenfeucht-Fraïssé games in finite set theory, Secret, verifiable auctions from elections, First-order expressibility of languages with neutral letters or: The Crane Beach conjecture, Bounded minimalisation and bounded counting in argument-bounded idc's, Extensional Uniformity for Boolean Circuits