First-order logic with counting: at least, \textit{weak} Hanf normal forms always exist and can be computed!

MaRDI QIDQ5144680zbMATH OpenFDO

Authors Nicole Schweikardt, Dietrich Kuske

Publication date 19 January 2021

Full work available at URL https://arxiv.org/abs/1703.01122, http://dl.acm.org/citation.cfm?id=3330068

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Logic with extra quantifiers and operators (03C80) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Hanf normal form for first-order logic with unary counting quantifiers
• Gaifman normal forms for counting extensions of first-order logic
• scientific article; zbMATH DE number 1453077
• Logics with counting and local properties
• The expressive power of fixed-point logic with counting

Cited in

(20)

• Answering FO+MOD queries under updates on bounded degree databases
• Computing thejth solution of a first-order query
• Hanf normal form for first-order logic with unary counting quantifiers
• Gaifman normal forms for counting extensions of first-order logic
• Answering FO+MOD queries under updates on bounded degree databases
• Constant delay enumeration with FPT-preprocessing for conjunctive queries of bounded submodular width
• First-order definable counting-only queries
• Lacon-, Shrub- and Parity-Decompositions: Characterizing Transductions of Bounded Expansion Classes
• INTERLEAVING LOGIC AND COUNTING
• Learning concepts described by weight aggregation logic
• Solving a family of multivariate optimization and decision problems on classes of bounded expansion
• Learning concepts definable in first-order logic with counting
• Model checking disjoint-paths logic on topological-minor-free graph classes
• Are targeted messages more effective?
• Compound logics for modification problems
• The descriptive complexity of graph neural networks
• On the VC dimension of first-order logic with counting and weight aggregation
• Advances in algorithmic meta theorems (invited paper)
• Learning aggregate queries defined by first-order logic with counting
• Solving partial dominating set and related problems using twin-width

This page was built for publication: First-order logic with counting: at least, \textit{weak} Hanf normal forms always exist and can be computed!

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