A Pebbling Comonad for Finite Rank and Variable Logic, and an Application to the Equirank-variable Homomorphism Preservation Theorem | Zendy

Thomas Paine | Zendy

Open Access

A Pebbling Comonad for Finite Rank and Variable Logic, and an Application to the Equirank-variable Homomorphism Preservation Theorem

Author(s) -

Thomas Paine

Publication year - 2020

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2020.09.010

Subject(s) - homomorphism , mathematics , rank (graph theory) , variable (mathematics) , bounded function , quantifier (linguistics) , tree (set theory) , discrete mathematics , quantifier elimination , algebra over a field , combinatorics , pure mathematics , computer science , mathematical analysis , artificial intelligence

In this paper we recast the proof of Rossman's equirank homomorphism preservation theorem using comonadic formulations of bounded quantifier rank and variable count (and dually tree width and tree-depth), and work towards generalisation of it that simultaneously preserves quantifier rank and variable count. Along the way, we give an exposition of the required comonads, showing how their properties arise.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research