Logics with counting and local properties

DOI10.1145/343369.343376MaRDI QIDQ5738897zbMATH OpenOpenAlexFDO

Authors Leonid Libkin

Publication date 13 June 2017

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

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

zbMATH Keywords

countingfirst-order logicinfinitary logiclocality

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Other infinitary logic (03C75)

Recommendations

• scientific article; zbMATH DE number 1453077
• The expressive power of fixed-point logic with counting
• Notions of locality and their logical characterizations over finite models
• On the expressive power of counting
• Logics capturing local properties

Cited in

(23)

• Expressive power of SQL.
• Expressive power of entity-linking frameworks
• Shrinking games and local formulas
• The complexity of first-order and monadic second-order logic revisited
• An existential locality theorem
• Game-based notions of locality over finite models
• L-recursion and a new logic for logarithmic space
• A logical approach to locality in pictures languages
• scientific article; zbMATH DE number 6680147 (Why is no real title available?)
• The Power of Counting Logics on Restricted Classes of Finite Structures
• An optimal construction of Hanf sentences
• scientific article; zbMATH DE number 515737 (Why is no real title available?)
• scientific article; zbMATH DE number 1086488 (Why is no real title available?)
• scientific article; zbMATH DE number 1500519 (Why is no real title available?)
• L-recursion and a new logic for logarithmic space
• Modal Logics with Counting
• First-order logic with counting: at least, \textit{weak} Hanf normal forms always exist and can be computed!
• Pebble weighted automata and weighted logics
• Arithmetic, first-order logic, and counting quantifiers
• Logics capturing local properties
• Logical locality entails frugal distributed computation over graphs (extended abstract)
• On the existential fragments of local first-order logics with data
• On the expressive power of counting

This page was built for publication: Logics with counting and local properties

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