A pebbling comonad for finite rank and variable logic, and an application to the equirank-variable homomorphism preservation theorem

DOI10.1016/j.entcs.2020.09.010OpenAlexW3094622282WikidataQ113317297 ScholiaQ113317297MaRDI QIDQ2133477

Thomas Paine

Publication date: 29 April 2022

Full work available at URL: https://doi.org/10.1016/j.entcs.2020.09.010

zbMATH Keywords

finite variable logictree-widthtree-depthpebble gamesfinite rank logicpebbling comonad

Mathematics Subject Classification ID

Semantics in the theory of computing (68Q55) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Related Items (2)

Structure and Power: an Emerging Landscape ⋮ Arboreal categories and equi-resource homomorphism preservation theorems

Cites Work

• Unnamed Item
• Unnamed Item
• Relating structure and power: comonadic semantics for computational resources (extended abstract)
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• An application of games to the completeness problem for formalized theories
• Homomorphism preservation theorems
• Finite and infinite model theory - a historical perspective
• Some Aspects of Model Theory and Finite Structures

This page was built for publication: A pebbling comonad for finite rank and variable logic, and an application to the equirank-variable homomorphism preservation theorem