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

DOI10.2168/LMCS-12(4:8)2016MaRDI QIDQ2974792zbMATH OpenFDO

Authors Frederik Harwath, Nicole Schweikardt

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

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

Recommendations

• scientific article
• Locality of order-invariant first-order formulas
• scientific article; zbMATH DE number 1222579
• Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates
• On Presburger arithmetic extended with modulo counting quantifiers
• Decidable first-order modal logics with counting quantifiers
• scientific article; zbMATH DE number 4099258
• scientific article; zbMATH DE number 1989643
• On classes of arithmetical counterparts of modal provability logics
• A local normal form theorem for infinitary logic with unary quantifiers

Cites work

• scientific article; zbMATH DE number 6680147 (Why is no real title available?)
• scientific article; zbMATH DE number 1222579 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 618821 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• A short tutorial on order-invariant first-order logic
• Computational Complexity
• Elements of finite model theory.
• Locality from circuit lower bounds
• Notions of locality and their logical characterizations over finite models
• On monadic NP vs monadic co-NP
• On uniformity within \(NC^ 1\)
• Regular tree languages definable in FO and in FO\(_{\mathrm{mod}}\)
• Towards a characterization of order-invariant queries over tame graphs

Cited in

(5)

• Modulo counting on words and trees
• Gaifman normal forms for counting extensions of first-order logic
• Locality from circuit lower bounds
• Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates
• scientific article; zbMATH DE number 6680147 (Why is no real title available?)

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

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