Motivated by recent connections to factorised databases, we analyse the efficiency of representations by context free grammars (CFGs). Concretely, we prove a recent conjecture by Kimelfeld, Martens, and Niewerth (ICDT 2025), that for finite languages representations by general CFGs can be doubly-exponentially…
New York, NY: Association for Computing Machinery (ACM), 2025-06-09
Given two n-element structures, A and ℬ, which can be distinguished by a sentence of k-variable first-order logic (ℒk), what is the minimum f(n) such that there is guaranteed to be a sentence Φ ∈ ℒk with at most f(n) quantifiers, such that A ⊨ Φ but ℬ ⊭ Φ? We will present various results related to this…
New York, New York: Association for Computing Machinery, 2024-07-08
The task of computing homomorphisms between two finite relational structures A and B is a well-studied question with numerous applications. Since the set Hom(A, B) of all homomorphisms may be very large having a method of representing it in a succinct way, especially one which enables us to perform efficient…
Saarbrücken/Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023