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

DOI10.2168/LMCS-12(4:8)2016zbMATH Open1445.03038MaRDI QIDQ2974792FDOQ2974792

Authors: Frederik Harwath, Nicole Schweikardt 

Publication date: 11 April 2017

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

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

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)

Cites Work

• Title not available (Why is that?)
• Computational Complexity
• On uniformity within \(NC^ 1\)
• Elements of finite model theory.
• Regular tree languages definable in FO and in FO _mod
• On monadic NP vs monadic co-NP
• Title not available (Why is that?)
• Notions of locality and their logical characterizations over finite models
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Locality from circuit lower bounds
• A short tutorial on order-invariant first-order logic
• Towards a characterization of order-invariant queries over tame graphs

Cited In (5)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates
• Locality from circuit lower bounds

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)