Arithmetic, first-order logic, and counting quantifiers

DOI10.1145/1071596.1071602zbMath1407.03050OpenAlexW1988899858WikidataQ130887631 ScholiaQ130887631MaRDI 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 logicquantifier eliminationPresburger arithmeticcounting quantifiers

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Logic with extra quantifiers and operators (03C80) Basic properties of first-order languages and structures (03C07) Quantifier elimination, model completeness, and related topics (03C10) Descriptive complexity and finite models (68Q19)

Related Items (15)

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

This page was built for publication: Arithmetic, first-order logic, and counting quantifiers