Hanf normal form for first-order logic with unary counting quantifiers

DOI10.1145/2933575.2934571zbMATH Open1394.03061OpenAlexW2530085392WikidataQ130849073 ScholiaQ130849073MaRDI QIDQ4635883FDOQ4635883

Authors: Lucas Heimberg, Nicole Schweikardt, Dietrich Kuske 

Publication date: 23 April 2018

Published in: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2933575.2934571

Recommendations

• First-order logic with counting: at least, \textit{weak} Hanf normal forms always exist and can be computed!
• Gaifman normal forms for counting extensions of first-order logic
• An optimal construction of Hanf sentences
• A local normal form theorem for infinitary logic with unary quantifiers
• On the expressive power of counting

zbMATH Keywords

model checkingnormal formsextensions of first-order logicmodulo-counting quantifiersHanf localityelementary algorithmsultimately periodic setsstructures of bounded degreeunary counting quantifiers

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) Descriptive complexity and finite models (68Q19)

Cited In (2)

• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: Hanf normal form for first-order logic with unary counting quantifiers

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