On the locality of arb-invariant first-order formulas with modulo counting quantifiers

DOI10.2168/LMCS-12(4:8)2016zbMath1445.03038MaRDI QIDQ2974792

Nicole Schweikardt, Frederik Harwath

Publication date: 11 April 2017

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

zbMATH Keywords

finite model theoryfirst-order logic with modulo counting quantifiersGaifman and Hanf localitylower bounds in circuit complexityorder-invariant and arb-invariant formulas

Mathematics Subject Classification ID

Logic with extra quantifiers and operators (03C80) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

Related Items (2)

Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Elements of finite model theory.
• On monadic NP vs monadic co-NP
• On uniformity within \(NC^ 1\)
• Regular tree languages definable in FO and in FO _mod
• Towards a characterization of order-invariant queries over tame graphs
• Locality from Circuit Lower Bounds
• A Short Tutorial on Order-Invariant First-Order Logic
• Notions of locality and their logical characterizations over finite models
• Computational Complexity

This page was built for publication: On the locality of arb-invariant first-order formulas with modulo counting quantifiers