1 citations · 1 across the 1 of their papers we have counts for
4 papers
A Lower Bound on Unambiguous Context Free Grammars via Communication Complexity
Stefan Mengel, Harry Vinall-Smeeth
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 K…
Supercritical Size-Width Tree-Like Resolution Trade-Offs for Graph Isomorphism
Christoph Berkholz, Moritz Lichter, Harry Vinall-Smeeth
We study the refutation complexity of graph isomorphism in the tree-like resolution calculus. Torán and Wörz (TOCL 2023) showed that there is a resolution refutation of narrow widt…
Structured d-DNNF Is Not Closed Under Negation
Harry Vinall-Smeeth
Both structured d-DNNF and SDD can be exponentially more succinct than OBDD. Moreover, SDD is essentially as tractable as OBDD. But this has left two important open questions. Firs…
From Quantifier Depth to Quantifier Number: Separating Structures with k Variables
Harry Vinall-Smeeth
Given two -element structures, and , which can be distinguished by a sentence of -variable first-order logic (), what is the minimum…