Cover Image

Datalog-Expressibility for Monadic and Guarded Second-Order Logic

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bodirsky, Manuel, Knäuer, Simon, Rudolph, Sebastian
Format:	Preprint
Published:	2020
Subjects:	Logic in Computer Science Computational Complexity Logic 03C13 Model theory of finite structures
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Hereditary First-Order Logic: the tractable quantifier prefix classes
by: Bodirsky, Manuel, et al.
Published: (2024)

Symmetric Linear Arc Monadic Datalog and Gadget Reductions
by: Bodirsky, Manuel, et al.
Published: (2024)

Network Satisfaction Problems Solved by k-Consistency
by: Bodirsky, Manuel, et al.
Published: (2023)

On the Computational Power of Extensional ESO
by: Bodirsky, Manuel, et al.
Published: (2025)

Local-Order-Invariant Logic on Classes of Bounded Degree
by: Aoki, Derek
Published: (2025)

Forbidden Tournaments and the Orientation Completion Problem
by: Bodirsky, Manuel, et al.
Published: (2023)

Algebraic Semantics of Datalog with Equality
by: Bidlingmaier, Martin E.
Published: (2023)

Monadic Second-Order Logic of Permutations
by: Jelínek, Vít, et al.
Published: (2025)

On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators(Extended Version)
by: Artale, Alessandro, et al.
Published: (2025)

Continuous Craig Interpolation
by: Keisler, H. Jerome
Published: (2024)

The Complexity and Expressive Power of Second-Order Extended Logic
by: Feng, Shiguang, et al.
Published: (2022)

Semi-Algebraic Proof Systems for QBF
by: Beyersdorff, Olaf, et al.
Published: (2025)

The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms
by: Bodirsky, Manuel, et al.
Published: (2025)

Structures preserved by primitive actions of $S_ω$
by: Bodirsky, Manuel, et al.
Published: (2025)

The Power of Negation in Higher-Order Datalog
by: Charalambidis, Angelos, et al.
Published: (2025)

Interpolant Existence is Undecidable for Two-Variable First-Order Logic with Two Equivalence Relations
by: Wolter, Frank, et al.
Published: (2024)

Proof Complexity of Linear Logics
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2026)

From Time to Space: The Impact of Linearity in Higher-Order Datalog
by: Charalambidis, Angelos, et al.
Published: (2026)

Interpolation in Non-Classical Logics
by: Fussner, Wesley
Published: (2025)

The Parameterized Complexity of Learning Monadic Second-Order Logic
by: van Bergerem, Steffen, et al.
Published: (2023)

First-Order Modal Logic via Logical Categories
by: Ghilardi, Silvio, et al.
Published: (2025)

Preservation Theorems Through the Lens of Topology
by: Lopez, Aliaume
Published: (2020)

Preservation theorems on sparse classes revisited
by: Dawar, Anuj, et al.
Published: (2024)

Hard QBFs for Merge Resolution
by: Beyersdorff, Olaf, et al.
Published: (2020)

Predicative Ordinal Recursion on the Constructive Veblen Hierarchy
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2025)

Finite Variable Counting Logics with Restricted Requantification
by: Raßmann, Simon, et al.
Published: (2024)

Courcelle's Theorem Without Logic
by: Filmus, Yuval, et al.
Published: (2025)

A New Ehrenfeucht-Fraïssé Game for Dependence Logic
by: Puljujärvi, Joni, et al.
Published: (2026)

Complexity of the Guarded Two-Variable Fragment with Counting Quantifiers
by: Pratt-Hartmann, Ian
Published: (2006)

Revisiting Interpolation in Relevant Logics
by: Fussner, Wesley, et al.
Published: (2025)

A general approach to asymptotic elimination of aggregation functions and generalized quantifiers
by: Koponen, Vera, et al.
Published: (2023)

On the computability of cofinal Fraïssé limits
by: Ackerman, Nathanael, et al.
Published: (2026)

Implicative models of set theory
by: Maschio, Samuele, et al.
Published: (2023)

Interpolation above S4
by: Santschi, Simon, et al.
Published: (2026)

Graph Homomorphisms and Universal Algebra
by: Bodirsky, Manuel
Published: (2026)

A Reflection Principle for Potential Infinite Models of Type Theory
by: Eberl, Matthias
Published: (2024)

Exploring P versus NP
by: Tang, Jian-Gang
Published: (2022)

First-Order Fischer Servi Logic
by: Christensen, Ahmee
Published: (2024)

What If Turing Had Preceded Gödel?
by: Oberhoff, Sebastian
Published: (2024)

Weighted First Order Model Counting for Two-variable Logic with Axioms on Two Relations
by: Kuang, Qipeng, et al.
Published: (2025)