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

DOI10.1145/2933575.2934571MaRDI QIDQ4635883zbMATH OpenOpenAlexWikidataFDO

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

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)

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

Cited in

(3)

• 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
• Modulo counting on words and trees

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)